JPEG Encoding of Zero-Value AC Coefficients

In JPEG compression, the vast majority of quantized high-frequency AC coefficients result in zeros, making their efficient representation critical for achieving high compression ratios. JPEG encodes these consecutive sequences of zero-value AC coefficients using a combination of zigzag scanning, Run-Length Encoding (RLE), and Huffman entropy coding. By grouping zeros into run-length counts paired with subsequent non-zero values, and utilizing special markers such as the Zero Run Length (ZRL) code and the End of Block (EOB) marker, the format eliminates the need to store individual zero values in the final bitstream.

The Zigzag Scan Order

Before encoding zeros, the 8×8 block of quantized Discrete Cosine Transform (DCT) coefficients must be serialized. Because high-frequency components—which are most likely to be quantized to zero—reside toward the bottom-right of the matrix, JPEG traverses the 64 coefficients in a zigzag sequence. This orders the values from lowest frequency to highest frequency, concentrating the non-zero coefficients at the start of the sequence and grouping the remaining zeros into long, contiguous runs toward the end.

Run-Length Encoding (RLE)

JPEG does not encode individual zeros directly. Instead, it uses Run-Length Encoding (RLE) to record only the count of consecutive zero coefficients that precede each non-zero coefficient.

Each non-zero AC coefficient is represented as a two-part data structure:

1. A composite symbol byte: Divided into two 4-bit nibbles:
   • Run-length (upper 4 bits): The number of consecutive zero coefficients preceding this non-zero coefficient (a value from 0 to 15).
   • Size/Category (lower 4 bits): The number of bits required to encode the amplitude of the following non-zero coefficient.
2. The amplitude bits: The actual binary value of the non-zero coefficient appended immediately after the symbol.

For example, if an AC coefficient with a value of 5 (which requires 3 bits) is preceded by 4 zeros, it is represented as (4, 3) followed by the binary representation of 5.

Handling Long Runs: The ZRL Marker

Because the run-length field is restricted to 4 bits, it can only represent a run of up to 15 zeros directly. When a sequence of zeros exceeds 15 without a non-zero value, JPEG uses a special code known as the Zero Run Length (ZRL) code.

• The ZRL symbol is defined as (15, 0) or hexadecimal 0xF0.
• It explicitly represents a sequence of 16 consecutive zero-value coefficients with no non-zero value following.
• If 35 consecutive zeros occur before a non-zero value, the encoder emits two consecutive ZRL symbols (accounting for 32 zeros), followed by a standard run-length symbol indicating 3 zeros before the non-zero coefficient.

Trailing Zeros: The End of Block (EOB) Marker

Most 8×8 blocks terminate with a long tail of zero-value coefficients extending to the 64th position. To prevent wastefully encoding repeated ZRL codes to the end of the block, JPEG utilizes the End of Block (EOB) marker.

• The EOB symbol is defined as (0, 0) or hexadecimal 0x00.
• Once the final non-zero coefficient in an 8×8 block is encoded, an EOB marker is written, signaling that all remaining coefficients in the block are zero.
• If a block contains non-zero coefficients up to the 64th position, the EOB marker is omitted.

Final Huffman Entropy Coding

The composite symbols—including standard (run, size) pairs, the ZRL marker (15, 0), and the EOB marker (0, 0)—are subsequently mapped to variable-length Huffman codes. Frequently occurring patterns, such as an immediate EOB or small zero runs, are assigned the shortest bit sequences, producing a compact binary stream that effectively collapses long sequences of zeros into just a few bits.