GIF LZW Minimum and Maximum Code Sizes Explained

In the Graphics Interchange Format (GIF) specification, image data is compressed using a modified version of the Lempel-Ziv-Welch (LZW) algorithm that utilizes variable-length codes. The minimum initial code size parameter defined in a GIF data stream is 2 bits, which results in an initial reading code length of 3 bits, while the maximum code size allowed during processing is strictly capped at 12 bits. This article explains the technical mechanics behind these boundaries, how the bit lengths scale during compression, and why these limits exist.

The Minimum Code Size

Before compressed image data begins, a GIF image data block contains a 1-byte value known as the LZW Minimum Code Size.

• The Parameter Range: The GIF specification defines that this value must match the color depth of the image, with an enforced lower limit. For images with a color palette of 2 to 4 colors (1 or 2 bits per pixel), the minimum code size parameter must be at least 2. For higher color depths (up to 8 bits per pixel, or 256 colors), the parameter corresponds directly to the bit depth, reaching up to 8.
• Starting Bit Length: The actual bit length used by the decoder to read the first codes is always calculated as LZW Minimum Code Size + 1. Because the smallest permissible minimum code size is 2, the absolute minimum bit length read from the LZW stream is 3 bits.

The extra bit accommodates two mandatory control codes embedded into the dictionary:

1. Clear Code (\(2^{\text{code size}}\)): Reinitializes the dictionary.
2. End of Information (EOI) Code (\(2^{\text{code size}} + 1\)): Marks the end of the raster data.

For a 1-bit monochrome image (2 colors), the minimum code size is set to 2. Codes 0 and 1 represent pixel values, code 4 is the Clear Code, and code 5 is the EOI code. Representing a value of 5 requires at least 3 bits (\(2^3 = 8\) maximum value).

The Maximum Code Size

The maximum code size used by GIF LZW compression is 12 bits.

As the compression algorithm processes pixel sequences, new entries are dynamically added to the string table (dictionary). When the number of entries exceeds the capacity of the current bit length, the code size increases by 1 bit:

• A 3-bit size expands to 4 bits once code 7 is reached.
• A 4-bit size expands to 5 bits at code 15, continuing upward sequentially.

This expansion continues until the code size reaches the hard maximum limit of 12 bits, which corresponds to code 4095 (\(2^{12} - 1\)). The dictionary cannot exceed 4,096 total entries.

Handling the 12-Bit Limit

Once the dictionary is full at 4,096 entries (12 bits), the encoder cannot increase the code size any further. At this stage, the encoder has two options depending on compression efficiency:

1. Continue using 12-bit codes: The encoder stops adding new sequences to the dictionary and emits existing 12-bit codes for recognized patterns.
2. Emit a Clear Code: The encoder outputs the Clear Code to wipe the string table back to its initial state. The bit length immediately resets back to LZW Minimum Code Size + 1, and the dictionary rebuilding process begins again.