encoding.info
You are hereSourcePredictionTransformEntropy codingFiltersFramesDecisionsRate controlPerceptionQualityBitstreamSettingsEncoder map
Page 2 of 6 in Entropy coding

Variable-length codes

Entropy coding · concept · added 2026-11-15

In Brief:
A variable-length code gives frequent symbols short codewords and rare ones long codewords, each a whole number of bits. To average below one bit per symbol, several symbols have to share a codeword.

A variable-length code gives each symbol a codeword made of a whole number of bits: short for the symbols that occur often, longer for the rest. When a symbol has two possible values and each value has a codeword of its own, neither codeword can be shorter than one bit, so that code cannot spend the fraction of a bit that a likely symbol is worth. Letting several symbols share one codeword can bring the average below one bit per symbol.

Codewords with no separators

This page codes flags: symbols with two possible values, zero or nonzero. There is one flag per pixel of the cat: zero if the pixel matches its predictor, nonzero otherwise. The predictor is the pixel to its left, or the pixel above at the start of a row; the first pixel of all uses mid-gray, 128. The code below gives a codeword to each pair of flags.

0 1 0 0 1 1 0 0
gray: a zero flagteal: a nonzero flag
Conceptual illustration, using this page's code for pairs of flags: 0 for two zeros, 10 for two nonzeros, 110 for a zero then a nonzero, 111 for a nonzero then a zero. Eight bits carry ten flags.

A decoder reads bits until they match a codeword, writes out that codeword's flags, and starts again. This code needs no separators, because none of its codewords is the beginning of another. A code with that property is called a prefix code.

Code one row of flags

Row picks one of the 32 rows of flags. Flags per codeword sets how many flags share a codeword. The code is built by counting: every row is taken that many flags at a time, and the groups that occur most often get the shortest codewords. With one flag per codeword there are only two codewords, of one bit each, and nothing is saved.

Only the flags are coded: whether each pixel matches its predictor. A nonzero flag does not say how different the pixel is, so these bits alone cannot rebuild the picture.

15
← 1: top of the picture32: bottom →
The row's flags, in groups
Its codewords, in order
The cat's flags, with the row outlined
The code: group, count in the cat, codeword
Outlined entries occur in the selected row.
Zeros in the row
Row's flag bits
Bits per flag
All flag bits
Simplified demo: the code is a Huffman code, built by joining the two rarest groups again and again. It is fitted to this one picture, which flatters it. The decoder is assumed to know the table and the number of flags, and nothing is counted for telling it either. The bits carry the flags only, not the sizes or signs of the differences. The flags are this course's, not H.264 syntax, and the cat is invented. All flag bits is the sum over all 32 rows. These are counts for this picture, not a bitrate.

Measured on the cat's flags:

The variable-length coder in x264

x264's is context-adaptive variable-length coding (CAVLC). --no-cabac selects it, and so do the ultrafast preset, the fastdecode tuning and the Baseline profile. Its tables are constants in the source, not counted from the video.

Its residual coder shares codewords too, by coding values jointly. One codeword, x264_coeff_token, carries two counts for a block of levels, the quantized transform coefficients: how many are nonzero, and how many consecutive levels at the start of the coding order, at most three, are 1 or −1. That order starts from the last nonzero coefficient. The signs of those levels, the other levels and the runs of zeros follow separately. The codeword comes from one of six tables, and for most blocks the choice follows how many nonzero levels the neighboring blocks had. That choice is the context-adaptive part.

Where a residual block has such a token, an empty block has one too, x264_coeff0_token, of 1 to 6 bits depending on the table. The coded block pattern leaves out whole groups of residual blocks.

Trade-offs

Sources

Read 2026-11-14 and 2026-11-15, at the commit linked.