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

Why some symbols cost less than a bit

Entropy coding · concept · added 2026-11-14

You'll want firstFour kinds of redundancy
In Brief:
An entropy coder spends few bits on likely values and many on unlikely ones. The ideal price of a value with probability p is minus log2 of p bits, so any value that is more likely than not is worth less than one bit.

An entropy coder is the last stage of the loop: it turns the levels and the prediction information into bits, and the decoder gets every value back exactly. It saves bits by spending few on values that are likely and many on values that are not. The ideal price of a value that occurs with probability p is −log2(p) bits, so the ideal price of any value that is more likely than not is less than one bit.

Source
Differences
Zero or not
The cat from Four kinds of redundancy, each pixel's difference from the pixel to its left (mid-gray is zero), and one flag per pixel: gray where the difference is zero, teal where it is not. of the 1,024 flags are zero. The flags say only where a difference is zero: rebuilding the cat would also take the signed values of the nonzero differences, and this page counts only the flags. The cat is invented. The first pixel of a row is compared with the pixel above it, and the first pixel of all with mid-gray.

The price of a symbol

A symbol is one value handed to the entropy coder. On this page it is one flag: is this difference zero or not? An outcome that is given probability p has an ideal cost of

ideal cost = −log2(probability) bits

At probability 1/2 that is 1 bit, at 1/4 it is 2 bits, and at 0.9 it is 0.15 bits. A real code need not spend that many bits on that particular outcome: with the codewords 0 and 1, a flag costs one bit whether it was the 90% outcome or the 10% one. Weighting the ideal costs by how often each outcome occurs gives the entropy. For symbols that do not depend on each other, that is the lower limit on a lossless code's average bits per symbol.

Change how often zero occurs

The slider sets the share of flags that are zero. The field shows 100 flags with that share, and the plot marks each kind of flag's ideal cost on the curve −log2(p). A code that gives every flag its own codeword spends at least one whole bit on each; the last readout is that baseline. All four readouts are in bits per flag. The slider starts at 69%, the cat's share rounded to a whole percent.

69%
← 50%: even odds99%: almost always zero →
100 flags
Ideal cost of each kind
a zeroa nonzerodashed line: 1 bit
Ideal cost, zero
Ideal cost, nonzero
Average per flag
One codeword each
1.00
Simplified demo: the readouts evaluate the formula above; nothing is coded. The field's flags are placed by a fixed shuffle, not taken from the cat. The costs assume independent flags and a decoder that already knows the share of zeros. They are ideal averages, not a bitrate. At 50% the two dots coincide.

By the formula:

The unlikely symbol pays for the likely one's discount. The average still falls, because the expensive symbol is rare.

The price list in x264

x264 keeps these prices in a table, x264_cabac_entropy, in units of 1/256 bit: one pair of entries, likely value and unlikely value, for each of the 64 probability states of its arithmetic coder. At even odds both entries are 256, one bit. In the strongest state a probability estimate can adapt to, the likely value is priced at 7, which is 0.027 bits, and the unlikely one at 1,449, which is 5.66 bits. The entries are estimates rounded to 1/256 bit.

The table is used to estimate bits before coding. The bits themselves come from the coder, which Arithmetic coding covers; the page after it compares it with variable-length codes.

What to carry forward

Sources

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