The GIF (Graphics Interchange Format) was created by CompuServe in 1987 and remains one of the most widely supported image formats on the internet despite being nearly four decades old. Understanding its internal structure reveals both its remarkable longevity and its inherent limitations.

GIF uses LZW (Lempel-Ziv-Welch) compression, a dictionary-based lossless algorithm patented by Unisys in 1985. LZW works by building a dictionary of recurring patterns in the data stream. As the encoder processes pixels, it looks for the longest sequence already in the dictionary, outputs the dictionary index for that sequence, and adds the sequence plus the next pixel as a new dictionary entry. This is particularly effective for images with large areas of uniform color or repeating patterns, where long pixel sequences can be represented by short dictionary codes. The LZW patent expired in 2004, removing the licensing concerns that had once driven the creation of PNG as a patent-free alternative.

The most significant limitation of GIF is its 256-color palette constraint. Each frame in a GIF can use at most 256 colors from the full 16.7 million colors available in 24-bit color space. For photographs and complex images, this requires color quantization to select the best 256 colors. The quality of this quantization dramatically affects the visual result. When the source image contains more than 256 distinct colors, some must be merged or replaced, potentially creating visible color banding in gradients and subtle color transitions.

Dithering algorithms address the color limitation by creating the illusion of colors not in the palette through spatial mixing. Floyd-Steinberg dithering, the most common algorithm, distributes the quantization error of each pixel to its unprocessed neighbors. When a pixel that should be orange is mapped to the nearest palette color of red, the error (the orange-minus-red difference) is distributed to adjacent pixels, making them more likely to be mapped to yellow. At normal viewing distance, the eye blends these interleaved red and yellow pixels into the perception of orange. This is analogous to pointillist painting, where small dots of pure color blend optically when viewed from a distance.

Animation in GIF works through sequential frame encoding, where each frame can specify its own delay time, disposal method, and optionally its own local color palette. The disposal method determines what happens to the frame area before the next frame is drawn: it can be left in place, restored to the background color, or restored to the previous frame state. Clever use of disposal methods and transparent pixels enables techniques like delta encoding, where only the pixels that changed between frames are stored, significantly reducing file size for animations where most of the image remains static between frames.