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

Arithmetic coding

Entropy coding · concept · added 2026-11-15

In Brief:
Arithmetic coding encodes symbols together, so each one needn't use a whole bit. Likely symbols contribute less to the total cost, unlikely symbols more, and the average can fall below one bit per symbol.

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.

4
← 0: nothing coded6: the whole message →
The line from 0 to 1
00.250.50.751
gray: the part for a zeroteal: the part for a nonzero
Interval width
Ideal bits
Bits if stopped here
String if stopped here
Simplified demo: every row is drawn on the same line from 0 to 1. In each row the current interval is divided, the solid part is kept, and the kept part is the interval the next row divides. The last row shows the interval that is left and, under it, the piece of the line that the bits name. The flags are from row 13 of the cat, columns 14 to 19, and the cat is invented. The string is worked out from the interval with exact fractions, afresh for each stopping point. That is not how the coders read for this page produce bits: they work in integers and shift bits out as the interval narrows. The decoder is assumed to know the probability, which part a zero takes and how many flags there are; none of that is counted.

Ideal bits, as a formula:

width = product of probabilities
        of the flags coded
ideal bits = −log2(width)

Measured in the demo:

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

Sources

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