Variable-length codes
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.
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.
Measured on the cat's flags:
- One flag per codeword cost 32 bits for every row, 1,024 for all 1,024 flags.
- Sharing codewords cost less overall. Two flags per codeword cost 854 bits for all 1,024 flags, 0.83 per flag; four cost 757, 0.74 per flag.
- Row 31, all zeros, cost 32, 16 and 8 bits. With four flags per codeword, four zeros are one bit.
- Row 12 cost more than one bit per flag: 37 bits with two flags per codeword and 35 with four. Its groups are ones the code gave long codewords.
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
- With two possible values, a codeword each costs at least one bit. The average falls below one bit per flag only where flags share a codeword.
- A table is fitted to the counts it was built from. No prefix code with one codeword per group codes the cat's flags in fewer bits, and row 12 still cost more than 32. Another picture may have different counts, so the same tables may fit it poorly; this page did not try one.
- Larger groups need larger tables. This demo gives all 16 possible groups of four flags a codeword, including the two that never occur in the cat. Each of those two gets a 9-bit codeword, so the same table could still code them in another message.
- The fractions are still out of reach for one symbol at a time. Arithmetic coding gets them without grouping, and the comparison page sets the two side by side.
Sources
Read 2026-11-14 and 2026-11-15, at the commit linked.
- x264 at commit c24e06c (GitHub mirror): the arithmetic coder on by default, ultrafast, fastdecode, Baseline,
--no-cabac, the count of leading levels of magnitude 1, the levels collected from the last nonzero coefficient back, the joint codeword, the signs written after it, its six tables, the table chosen from the neighbors' counts,x264_mb_predict_non_zero_code, which averages the counts of the blocks to the left and above, the codeword for an empty block,x264_coeff0_token, residual blocks written only for the groups the coded block pattern marks, the coded block pattern written. - Computed for this page, not taken from a source: every set of codeword lengths a prefix code can have was tried for the 4 pairs and the 16 groups of four (2 and 1,639 sets), and none codes the cat's flags in fewer than 854 or 757 bits.
- Not checked: the H.264 specification, including its tables and which profiles allow which coder; that a Huffman code is the best such code for any counts, which is standard theory and was not taken from a source read for this page; how x264 codes the levels themselves and the runs of zeros between them; x265, which has no variable-length coder option in the files searched; libaom and SVT-AV1.