What if we stopped giving every symbol its own separate codeword and instead let the whole message carve out one tiny numerical interval?
That is the central idea behind arithmetic coding.
Rather than saying “A gets these bits, B gets those bits,” arithmetic coding repeatedly divides a number line according to probabilities. Each observed symbol selects one subinterval. The next symbol subdivides that interval again. After the entire message, any number inside the surviving interval identifies the sequence.
The smaller the final interval, the more bits are needed to specify a number inside it. Highly probable sequences leave wider intervals and therefore need fewer bits. Surprising sequences leave narrower ones and need more.
Quick Read
- Arithmetic coding converts a sequence of probabilities into a nested interval.
- More probable symbols consume less interval width and therefore less description length on average.
- The code is not forced to assign an integer number of bits to each individual symbol.
- This lets arithmetic coding approach fractional-bit average costs over long sequences.
- The probability model and the coder are separate jobs: good coding cannot rescue bad probabilities.
- Practical implementations renormalise intervals and use finite-precision integer arithmetic.
- Range coding is a closely related practical formulation of the same core idea.
The One-Sentence Answer
Arithmetic coding represents a whole sequence by repeatedly narrowing an interval according to symbol probabilities, so common events reduce the interval modestly while rare events reduce it sharply, producing a code length close to the information implied by the model.
Start With the Interval From 0 to 1
Imagine a source with two symbols:
- A has probability 0.75;
- B has probability 0.25.
Start with the interval [0,1). Divide it according to the probabilities:
A → [0.00, 0.75) B → [0.75, 1.00)
If the first symbol is A, the surviving interval becomes [0,0.75). If the next symbol is B, subdivide that interval again in the same 75/25 proportions and select the B portion.
Repeat until the message ends.
The Message Becomes a Point We Only Need to Specify Precisely Enough
At the end, we do not literally need to transmit an infinitely precise real number.
We need enough bits to identify a binary fraction that lies inside the final interval and nowhere inconsistent with the decoding process.
The decoder starts with the same [0,1) range, the same probability model and the transmitted coded value. It sees which symbol interval contains that value, emits the symbol, rescales to the chosen subinterval, and repeats.
Encoding and decoding walk the same nested geometry in opposite directions.
Why This Beats One-Codeword-Per-Symbol Thinking
Suppose a symbol ideally deserves 0.3 bits on average under a probability model. A conventional prefix code cannot literally assign 0.3 bits to one occurrence. Individual codewords have integer lengths.
Arithmetic coding avoids this local restriction because it encodes the sequence as a whole.
Over many symbols, fractional average costs become possible.
This is one reason arithmetic coding can operate very close to the entropy implied by a good probability model.
Probability Multiplies; Code Length Adds
If the model assigns probabilities p₁, p₂, p₃ and so on to the symbols that actually occur, the final interval width is proportional to their product:
width ≈ p₁ × p₂ × p₃ × ...
Taking minus logarithms turns that multiplication into addition:
code length ≈ -log₂ p₁ - log₂ p₂ - log₂ p₃ ...
This is the same informational pricing rule that appears throughout our Prediction and Regret articles.
Probability is the model’s belief. Code length is the bill.
The Model Matters More Than the Interval Trick
Arithmetic coding does not discover that A is common. It does not find repeated phrases. It does not infer grammar by itself.
It receives probabilities from a model.
If those probabilities are excellent, arithmetic coding converts them efficiently into bits. If the model is poor, the coder faithfully encodes poor beliefs and the output grows.
This separation is useful:
model → probabilities → arithmetic/range coder → bits
Prediction and coding are partners, not synonyms.
Adaptive Arithmetic Coding
The probability model can change as the message arrives.
Suppose the encoder begins with neutral counts, then updates frequencies after every decoded symbol. The decoder can perform the same updates because it reconstructs the same sequence in the same order.
No separate full frequency table needs to be transmitted if both sides share the update rule and starting state.
This is universal coding meeting arithmetic coding.
Finite Precision: Computers Do Not Store Perfect Real Numbers
The textbook picture uses real intervals such as [0.123456…,0.123987…). Real machines use finite integers.
Practical arithmetic coders maintain integer lower and upper bounds. As the interval narrows, common leading bits become fixed and can be emitted. The remaining interval is renormalised so computation continues without needing unlimited precision.
This implementation detail is not incidental. Good arithmetic coding is a careful numerical protocol ensuring encoder and decoder make identical rounding decisions.
Renormalisation Lets an Infinite Process Run in Finite Registers
When both ends of the current interval lie in the same half of the coding range, the leading bit is determined. The encoder can emit it and rescale the remaining interval.
Other cases require handling intervals straddling middle regions so that precision is not lost.
Different arithmetic-coding implementations organise these cases differently, but the principle is consistent: release bits as soon as they become irrevocably known.
Range Coding
Range coding is a practical relative of arithmetic coding. Rather than speaking in terms of arbitrary-precision real intervals, it keeps a finite integer range and updates that range according to symbol frequencies.
Conceptually, both are performing the same job: map cumulative probabilities into nested numeric subranges and emit enough digits to distinguish the chosen path.
The terminology and engineering differ; the underlying information geometry is close.
Arithmetic Coding Loves Unequal Probabilities
If all symbols are equally likely, there is less statistical advantage to exploit.
If one outcome is overwhelmingly likely, arithmetic coding can represent long runs of expected events extremely economically because each event only trims a small fraction from the interval.
Rare events are expensive because they select tiny subintervals.
The geometry mirrors surprise.
A Rare Event Does Not Break the Code
Suppose an event has probability 0.001. It receives a tiny portion of the interval, but it remains perfectly encodable as long as the model assigns nonzero probability and the finite-precision implementation handles the frequency representation correctly.
The event simply costs roughly ten bits of surprise because -log₂(0.001) is around that scale.
Compression does not punish rarity morally. It prices rarity informationally.
Zero Probability Is Dangerous
If the model assigns probability zero to an event that actually occurs, its interval has zero width. The coder has nowhere to put the event.
Practical adaptive models therefore need escapes, smoothing or guaranteed nonzero counts for possible symbols.
This is another reminder that confidence should never exceed evidence without a recovery path.
Why Arithmetic Coding Was Historically Important
Arithmetic coding became important because it provided a practical route to entropy coding with very fine probability resolution, especially when symbol distributions were highly skewed or adaptive.
It appears in influential image, video and document-compression systems and in research compressors where strong probabilistic modelling is central.
Its conceptual elegance is enduring: probabilities become lengths directly.
Why It Is Not Everywhere
Arithmetic coding can involve serial dependencies, careful state management and computational overhead. Historically, patent concerns also influenced adoption in some periods and applications.
Other coders—Huffman coding, range coders, ANS variants and specialised table-based schemes—can offer different trade-offs among speed, hardware simplicity, parallelism and coding efficiency.
There is no universal entropy coder for every engineering context.
Arithmetic Coding and Context Mixing
Context-mixing compressors can produce extraordinarily detailed next-bit probabilities. Arithmetic coding is a natural partner because it can translate those probabilities into near-corresponding code lengths without forcing each event into a crude fixed codeword.
One side asks, “How likely is this?”
The other asks, “How many bits should that likelihood cost?”
A Map Analogy
Imagine the interval [0,1) as a country. Every symbol divides the current territory into regions proportional to probability.
The actual message chooses one region, then a district inside that region, then a street, then a building, then a room.
At the end, we transmit enough of the address to identify the room.
Highly likely choices receive large regions and require fewer address digits. Rare choices receive tiny regions and require more.
Human Communication Has a Similar Logic
If I ask, “What colour is the sky on a clear day?” you can often answer “blue” with little explanatory effort because the outcome is highly expected.
If the sky is unexpectedly green, much more explanation is demanded.
Again, human language is not arithmetic coding. But the analogy illustrates the informational principle: predictable events need less distinguishing information than surprising ones.
Education: Do Not Memorise the Interval—Understand the Contract
Students encountering arithmetic coding can get lost in decimal arithmetic and miss the larger point.
- The model divides probability mass.
- The observed symbol chooses a subinterval.
- Repeated choices create nested intervals.
- The final interval identifies the whole sequence.
- Its width determines how much precision—and therefore roughly how many bits—is needed.
Once this contract is clear, implementation details have somewhere to attach.
Primary School: Divide the Number Line
Draw a strip. Give red 3/4 of it and blue 1/4. If red occurs, keep only the red section and divide it again. Repeat with a short sequence.
The child can physically see the interval narrowing.
Secondary School: Probability Becomes Length
Use simple fractions such as 1/2, 1/4 and 1/8. Show that repeatedly choosing smaller probability regions creates exponentially narrower intervals and therefore requires more binary digits to specify.
This connects logarithms, probability and information naturally.
JC and Beyond: Arithmetic Coding and Entropy
At higher levels, arithmetic coding offers a constructive bridge from source probabilities to near-entropy code lengths. Under appropriate modelling and implementation, cumulative coding cost tracks negative log-likelihood closely.
This is why information theory, statistics and compression meet so cleanly here: the same logarithmic quantity measures surprise, predictive loss and ideal coding length.
An Arithmetic-Coding Checklist
- Where do the probabilities come from?
- Are all possible events assigned nonzero probability?
- Do encoder and decoder use identical cumulative frequencies?
- How is finite precision handled?
- When are stable leading bits emitted?
- How does the model adapt?
- What speed and serial-dependency costs matter?
- Would another entropy coder better suit the hardware or workload?
The Deeper Point
Arithmetic coding removes a mental constraint we rarely notice: the idea that every symbol needs its own little packet of bits.
It lets the entire sequence share one numerical description.
The message becomes a path through probability space, and the final interval is the footprint of that path.
Predictability makes the interval shrink slowly. Surprise makes it shrink quickly. Bits are simply the precision needed to say where we ended up.
Explore the How Compression Works.