How GIF LZW Code Size Expands to 12 Bits

The Graphics Interchange Format (GIF) employs a modified version of the Lempel-Ziv-Welch (LZW) compression algorithm that dynamically expands its code size to accommodate an ever-growing dictionary of color patterns. This article explains the exact mechanics behind this expansion, beginning with the initial bit-width defined by the image palette, detailing the condition that triggers each incremental bit increase, and exploring the behavior of the encoder and decoder when reaching the protocol's strict 12-bit ceiling.

Initial Bit-Width and Reserved Codes

Every LZW data stream in a GIF file begins with a single byte defining the LZW Minimum Code Size. This value typically corresponds to the color depth of the image (or 2 for images with a 1-bit palette).

The initial reading code size is always set to:

\[\text{Initial Code Size} = \text{LZW Minimum Code Size} + 1\]

Before encoding image data, the dictionary initializes entries for every possible single-pixel color index (from \(0\) to \(2^{\text{Minimum Code Size}} - 1\)). Two special control codes are then appended:

• Clear Code (CC): \(2^{\text{Minimum Code Size}}\)
• End of Information (EOI): \(2^{\text{Minimum Code Size}} + 1\)

The next available code assigned to a newly discovered pixel sequence is therefore \(\text{EOI} + 1\). Because the initial dictionary contains more entries than can be represented by the minimum code size alone, the extra bit in the initial code size ensures that all initial palette indices, the Clear Code, and the EOI code fit within the active bit-width.

The Trigger for Dynamic Expansion

As the encoder scans pixels and creates new dictionary strings, each entry is assigned the next sequential integer code. Because LZW codes are packed into the bitstream using variable bit-widths, the reader and writer must stay synchronized on how many bits represent each incoming code.

A bit-width expansion occurs when the dictionary grows to a size that can no longer be addressed by the current bit-width:

1. A bit-width of \(N\) bits can represent integer values from \(0\) up to \(2^N - 1\).
2. When the next dictionary index to be added equals \(2^N\) (or when code \(2^N - 1\) is assigned, depending on whether the implementation increments the size before or after the threshold code is emitted), the current bit capacity is exhausted.
3. Both the encoder and decoder automatically increment the active code size by 1:

\[\text{Active Code Size} = N + 1\]

For example, if the initial code size is 3 bits, it can represent values from 0 to 7. When the dictionary reaches code 7 and assigns code 8, 3 bits are insufficient. The code size dynamically increases to 4 bits, allowing codes up to 15.

Reaching the 12-Bit Maximum

The GIF standard imposes a hard limit of 12 bits for any LZW code. A 12-bit code space accommodates a maximum of 4,096 entries (codes 0 through 4095).

When the code size reaches 12 bits and the dictionary fills entry 4095:

• The code size can no longer increase.
• The encoder may continue outputting existing patterns using fixed 12-bit codes without adding new strings to the dictionary.
• Alternatively, the encoder can output the reserved Clear Code.

Resetting via the Clear Code

When an encoder emits a Clear Code:

1. The entire dictionary is wiped clean, retaining only the basic color indices, the Clear Code, and the EOI code.
2. The active code size immediately resets back to \(\text{LZW Minimum Code Size} + 1\).
3. New sequence construction begins anew, and the dynamic expansion cycle restarts from the base bit-width.