Entropy Coding and Decoding

Entropy coding turns the quantized coefficients of each block into the final bitstream. This note covers the coding stages, the decoder and a worked example.

Entropy Coding

1. Code the DC coefficient as the difference from the DC coefficient of the previous tile. Neighbouring tiles have similar means, so the differences are small.
2. Read the 63 AC coefficients in zig-zag order, from low to high frequency. The long tail of zeros collects at the end of the sequence.
3. Run-length encode the sequence as pairs of the number of preceding zeros and the next nonzero value. A special end-of-block symbol replaces the trailing zeros.
4. Huffman code the pairs.

The result of every tile is concatenated into 1 bitstream.

Zig-Zag Scan

The scan visits the 64 positions along anti-diagonals, alternating direction, starting at the DC position.

For an implementation, the scan is a lookup table. Entry $k$ is the row-major position (v * 8 + u) of the coefficient visited $k$-th.

ZIGZAG = [
     0,  1,  8, 16,  9,  2,  3, 10,
    17, 24, 32, 25, 18, 11,  4,  5,
    12, 19, 26, 33, 40, 48, 41, 34,
    27, 20, 13,  6,  7, 14, 21, 28,
    35, 42, 49, 56, 57, 50, 43, 36,
    29, 22, 15, 23, 30, 37, 44, 51,
    58, 59, 52, 45, 38, 31, 39, 46,
    53, 60, 61, 54, 47, 55, 62, 63,
]

Scanning a block is zz[k] = block_flat[ZIGZAG[k]]. Unscanning is block_flat[ZIGZAG[k]] = zz[k].

Anti-diagonals have constant $u + v$, so they have roughly constant spatial frequency. Coefficients along the scan therefore decay in expected magnitude, which groups the zeros into 1 long run at the end.

DC Coefficients

The DC coefficients of successive blocks of the same component are coded by differential pulse code modulation, a form of delta coding:

• The predictor starts at 0 for the first block
• Each component keeps its own predictor
• Quantization comes before prediction, so the differences are of quantized values

Magnitude Categories

A nonzero integer $a$ is described by its category $s$ and $s$ extra bits.

Category $s$ covers the values $\pm[2^{s-1}, 2^s - 1]$. Category 0 holds only the value 0.

The extra bits identify the value inside its category.

• For $a > 0$, the extra bits are the $s$ low bits of the binary form of $a$
• For $a < 0$, the extra bits are the $s$ low bits of $a - 1$, which equals the one’s complement of $|a|$ in $s$ bits

Examples:

• $a = 5$ has $s = 3$ and extra bits 101
• $a = -5$ has $s = 3$ and extra bits 010
• $a = -3$ has $s = 2$ and extra bits 00

A leading extra bit of 1 always marks a positive value and 0 a negative value.

Baseline limits are $s \le 11$ for DC differences and $s \le 10$ for AC coefficients.

The DC difference is coded as the Huffman code of its category $s$, followed by the $s$ extra bits.

AC Coefficients

Each nonzero AC coefficient is coded as a symbol byte followed by extra bits.

The Huffman code of RS is followed by the $s$ extra bits of the coefficient.

Two special symbols exist.

• EOB (0x00)
  End of block. Every remaining coefficient is 0. Omitted when coefficient 63 is nonzero.
• ZRL (0xF0)
  Zero run length. Stands for 16 zeros with no nonzero value. Used repeatedly when a run exceeds 15.

A run of 20 zeros followed by the value 3 is coded as ZRL, then $R = 4$, $s = 2$.

Huffman Tables

A table is defined in the file by two lists.

• BITS
  16 counts. Entry $l$ is the number of codes of length $l$.
• HUFFVAL
  The symbols in order of increasing code length.

The decoder rebuilds the codes canonically.

1. Set code = 0.
2. For each length $l = 1, \dots, 16$, assign code to each of the BITS[l] symbols of that length in order, incrementing code after each.
3. After finishing length $l$, shift code left by 1.

Constraints:

• Code lengths are at most 16 bits
• The all-ones code of any length is never assigned

Baseline allows 2 DC tables and 2 AC tables. Typically 1 pair serves luminance and 1 pair serves chrominance. Each component is assigned 1 DC table and 1 AC table.

Annex K gives typical luminance tables. Selected codes:

Short codes go to the symbols that occur most often, namely small values after short zero runs.

Encoders may instead compute optimal tables from the image’s own symbol statistics, which saves roughly 5 to 10 percent of the file size.

Standard Huffman Tables

The complete Annex K definitions, which BITS and HUFFVAL fully determine. Each AC table holds the 160 symbols $R \cdot 16 + s$ for $R \in [0, 15]$ and $s \in [1, 10]$, plus EOB (0x00) and ZRL (0xF0). The DC tables hold the categories 0 to 11.

DC_LUM_BITS = [0, 1, 5, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
DC_LUM_VALS = list(range(12))

DC_CHR_BITS = [0, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0]
DC_CHR_VALS = list(range(12))

AC_LUM_BITS = [0, 2, 1, 3, 3, 2, 4, 3, 5, 5, 4, 4, 0, 0, 1, 125]
AC_LUM_VALS = bytes.fromhex(
    "01 02 03 00 04 11 05 12 21 31 41 06 13 51 61 07"
    "22 71 14 32 81 91 a1 08 23 42 b1 c1 15 52 d1 f0"
    "24 33 62 72 82 09 0a 16 17 18 19 1a 25 26 27 28"
    "29 2a 34 35 36 37 38 39 3a 43 44 45 46 47 48 49"
    "4a 53 54 55 56 57 58 59 5a 63 64 65 66 67 68 69"
    "6a 73 74 75 76 77 78 79 7a 83 84 85 86 87 88 89"
    "8a 92 93 94 95 96 97 98 99 9a a2 a3 a4 a5 a6 a7"
    "a8 a9 aa b2 b3 b4 b5 b6 b7 b8 b9 ba c2 c3 c4 c5"
    "c6 c7 c8 c9 ca d2 d3 d4 d5 d6 d7 d8 d9 da e1 e2"
    "e3 e4 e5 e6 e7 e8 e9 ea f1 f2 f3 f4 f5 f6 f7 f8"
    "f9 fa"
)

AC_CHR_BITS = [0, 2, 1, 2, 4, 4, 3, 4, 7, 5, 4, 4, 0, 1, 2, 119]
AC_CHR_VALS = bytes.fromhex(
    "00 01 02 03 11 04 05 21 31 06 12 41 51 07 61 71"
    "13 22 32 81 08 14 42 91 a1 b1 c1 09 23 33 52 f0"
    "15 62 72 d1 0a 16 24 34 e1 25 f1 17 18 19 1a 26"
    "27 28 29 2a 35 36 37 38 39 3a 43 44 45 46 47 48"
    "49 4a 53 54 55 56 57 58 59 5a 63 64 65 66 67 68"
    "69 6a 73 74 75 76 77 78 79 7a 82 83 84 85 86 87"
    "88 89 8a 92 93 94 95 96 97 98 99 9a a2 a3 a4 a5"
    "a6 a7 a8 a9 aa b2 b3 b4 b5 b6 b7 b8 b9 ba c2 c3"
    "c4 c5 c6 c7 c8 c9 ca d2 d3 d4 d5 d6 d7 d8 d9 da"
    "e2 e3 e4 e5 e6 e7 e8 e9 ea f2 f3 f4 f5 f6 f7 f8"
    "f9 fa"
)

• Luminance tables serve the Y component and chrominance tables serve Cb and Cr
• The BITS lists sum to 12 for DC tables and to 162 for AC tables

Byte Stuffing and Restart Markers

• Byte stuffing
  Every 0xFF byte inside entropy-coded data is followed by a 0x00 byte. A marker is a 0xFF byte followed by a nonzero byte. Since the all-ones Huffman code is never assigned, a code cannot be mistaken for a marker.
• Padding
  The final partial byte of a scan is filled with 1 bits.
• Restart intervals
  An optional interval of $N$ MCUs makes the encoder byte-align the stream, emit a restart marker RST0 to RST7 (cycling) and reset all DC predictors to 0.

Restart intervals limit the damage from a bit error to 1 interval, since decoding can resynchronise at the next marker. They also allow parallel decoding.

Decoding

1. Parse headers and build the Huffman and quantization tables.
2. For each MCU, Huffman decode the DC difference and add it to the component’s predictor.
3. Huffman decode AC symbols until EOB or 63 coefficients, expanding each run of zeros.
4. Place the 64 values back from zig-zag order into an 8x8 array.
5. Multiply by the quantization table.
6. Apply the inverse DCT.
7. Add 128 and clamp to $[0, 255]$.
8. Upsample the chroma planes to full resolution.
9. Convert YCrCb to RGB.

For one block, steps 5 to 7 combine into:

The inverse DCT output is rounded, so decoders from different vendors can differ by at most a small amount per pixel. The standard bounds this difference through accuracy tests.

Worked Example

Subsampling Calculation

A $4 \times 4$ region of $C_b$ values under 4:2:0 has 4 groups of $2 \times 2$ pixels.

Subsample the region to 4:2:0, restore it and find the error.

First Block of an Image

The test image is a $512 \times 768$ photo of a lighthouse, encoded at quality 50. The first block is the top-left $Y$ block of the first MCU. Encode it into JPEG symbols, starting from the pixel $(0, 0)$ with $(R, G, B) = (75, 93, 94)$.

11110|01101  11110101|01  011|10  111010|0  010