Arithmetic coding
An arithmetic coder gives no symbol a codeword of its own. It represents the whole message by a number inside an interval. Every symbol narrows the interval, a little if the symbol was likely and a lot if it was not, and the bits written only have to point into the interval that is left. That is how a likely symbol comes to cost a fraction of a bit, which the whole codewords of a variable-length code cannot do for one symbol.
Code the flags one at a time
A flag here is a symbol with two possible values, zero or nonzero. The message is six of the cat's flags: zero, zero, nonzero, zero, nonzero, zero.
The coder holds an interval of the line from 0 to 1, at first all of it. For each flag it divides the interval by the probabilities, gray for a zero and teal for a nonzero, and keeps the part for the flag that occurred. Modeled chance of zero sets the division: it changes the probability assumed for the flags, not the flags.
Flags coded sets where the message stops. At each position the demo shows the shortest string of bits that names a piece of the line lying wholly inside the interval, worked out afresh as if the message ended there. A string shown at an earlier position can change: this is not a trace of bits that a streaming encoder has already written. Ideal bits is the message's cost under the assumed probability.
Ideal bits, as a formula:
width = product of probabilities
of the flags coded
ideal bits = −log2(width)
Measured in the demo:
- At 90%, two zeros take one bit between them. They leave a width of 0.9 × 0.9 = 0.81, which still contains the lower half of the line, named by 0.
- A nonzero at 90% costs far more. Stopping after the first nonzero takes five bits, 11000, which does not begin with that 0, and after the second, eight.
- At 70%, stopping after three flags or after four takes the same four bits, 0110. After zero, zero, nonzero, zero the width is 0.1029, which is 3.28 ideal bits. The fourth flag narrowed the interval without lengthening the string.
- At 50% the string is the flags. Every flag halves the interval, and the six flags take the six bits 001010.
Reading the flags back
Set the demo to four flags at 70%. Four bits divide the line into 16 equal pieces. 0110 is binary for 6, so it names piece 6, counting from zero: from 6/16 up to, but not including, 7/16, which is 0.375 to 0.4375. That whole piece lies inside the interval that is left. Take its middle, 0.40625. The decoder uses the same probability and the same rule that a zero takes the lower part. It divides the line as the encoder did and sees which part holds that point: below 0.7, so a zero; below 0.49, a zero; above 0.343, a nonzero; below 0.4459, a zero. It stops because it knows the message has four flags.
The arithmetic coder in x264
x264's is context-adaptive binary arithmetic coding (CABAC), on by default. It codes two-valued decisions with integer intervals and tables, where the demo multiplies fractions. Some decisions, a coefficient's sign for one, take a separate bypass path that treats the two values as equally likely. Unlike this demo, it passes bits to its output as it works through the message.
The routines, in x264, x265 and libaom
x264 codes only two-valued decisions; other values, such as the intra macroblock type, are written as a series of them. Its interval is a pair of integers, a low end and a range that starts at 510. For each decision, x264_cabac_encode_decision_c looks up the unlikely value's share of the range in a table, x264_cabac_range_lps, and keeps one part. cabac_encode_renorm then shifts the range and the low end left and passes the bits that are finished to the output.
The bypass routine is x264_cabac_encode_bypass_c, which uses no probability estimate. The code that writes a decision picks the routine; a decision coded with an estimate does not change routines when its estimate nears even odds.
x265's Entropy::encodeBin is a table-driven coder of the same kind. libaom's od_ec_encode_cdf_q15 codes a symbol with up to 16 possible values in one step, and splits its range with an integer multiplication and shifts, not the demo's exact fractions.
What to carry forward
- The cost is for the message, not for each symbol. The final string needs a whole number of bits. With this demo's way of choosing a piece, its length is less than two bits above the ideal cost, not counting the shared model and the message length.
- The division can be different for every symbol. The demo's never changes. Context modeling is about choosing it.
- Bits generally cannot be divided among the symbols. At 70% four flags share 0110. At 50%, where every flag halves the interval, the bits are the flags.
- How the two kinds of coder compare on a longer message is on the next page.
Sources
Read 2026-11-14 and 2026-11-15, at the commits linked.
- x264 at commit c24e06c (GitHub mirror): the default,
cabac_mb_type_intra, the starting range,x264_cabac_encode_decision_c, the table lookup,x264_cabac_range_lps,cabac_encode_renorm,cabac_putbyte, which passes finished bytes to the output,x264_cabac_encode_bypass_c, a coefficient's sign written through it. - x265 at commit 4191822 (GitHub mirror):
Entropy::encodeBin, its range table lookup. - libaom at commit 1b7f9ef (GitHub mirror):
od_ec_encode_cdf_q15and its limit of 16 symbols, the multiplication. - Computed for this page, not taken from a source: every string the demo shows was decoded back by a separate program; for the page's message the string was at most 1.47 bits above the ideal cost (six flags at 70%); all 64 six-flag messages were coded at the three probabilities and every stopping point, and the string was at most 1.92 bits above the ideal cost (the message five zeros then a nonzero, at 90%); under 2 bits holds for any interval, because an interval at least two pieces wide contains a whole piece, and it is a property of this construction, not of an encoder's finished stream.
- Not checked: the H.264, HEVC and AV1 specifications; which decisions each encoder sends through its bypass routine, beyond the one linked; how each encoder turns its other many-valued symbols into two-valued decisions; how any of these coders ends a stream, beyond what the estimating page leaves out; SVT-AV1.