Back to the on-screen lesson · Print

Arithmetic coding

Coding a whole message as a subinterval of [0, 1); reaching the entropy without blocking.

Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.

1. What you will learn

By the end of this lesson you will be able to define the entropy rate of a stationary source, prove that its two natural definitions agree, explain why memory can only lower it, and compute it for i.i.d. sources and for stationary Markov chains as the stationary average of the row entropies. You will run arithmetic coding by hand on a short message, find the interval it produces and the number of bits it needs, and explain why its overhead is two bits per message rather than up to one bit per symbol, which is how practical compressors reach the entropy rate without grouping symbols into blocks.

2. Arithmetic coding

Arithmetic coding represents a whole message as a subinterval of $[0, 1)$. Split $[0, 1)$ into pieces proportional to the symbol probabilities, in a fixed order; the first symbol selects its piece; the second symbol splits that piece in the same proportions and selects again; and so on. After $n$ symbols the interval has width $P(x_1) P(x_2) \cdots P(x_n) = P(x^n)$, and any number inside it identifies the message, given $n$. A binary fraction with $\lceil -\log_2 P(x^n) \rceil + 1$ bits is guaranteed to lie inside, so the code length is at most $-\log_2 P(x^n) + 2$ bits: the message's own information plus two bits, however long the message is. Per symbol this tends to the entropy, or the entropy rate when the probabilities are conditional on the past, with no blocking and no waste per symbol, unlike Huffman codes. The probabilities may change as the message proceeds, which is what adaptive compressors and modern context-mixing methods exploit; the decoder reproduces the same splits and reads the symbols back.

3. Narrowing the interval, symbol by symbol

Fix the alphabet order and the cumulative probabilities; here $a = [0, 0.5)$, $b = [0.5, 0.75)$, $c = [0.75, 1)$. Start with $[0, 1)$ and, for each symbol, replace the current interval by the sub-piece the symbol names, in the same proportions. Coding $bac$: $b$ selects $[0.5, 0.75)$ of width $0.25$; inside it, $a$ takes the first half, $[0.5, 0.625)$; inside that, $c$ takes the last quarter, $[0.59375, 0.625)$, of width $2^{-5}$.

The width after $n$ symbols is exactly $P(x_1) P(x_2) \cdots P(x_n) = P(x^n)$: the interval is the probability. Every two-symbol message and its interval:

4. Why it beats a symbol code

Any number inside the final interval identifies the message. An interval of width $w$ always contains a binary fraction with $\lceil -\log_2 w \rceil + 1$ bits, so the code length is at most $$-\log_2 P(x^n) + 2$$ bits — the message's own information plus two bits, no matter how long the message is. Divide by $n$: the overhead per symbol is $2/n$, which vanishes. A Huffman symbol code, by contrast, pays its rounding on every symbol: a coin with $P(\text{heads}) = 0.9$ costs $1$ bit per flip against an entropy of $0.469$, while arithmetic coding of $1000$ flips costs about $469 + 2$ bits, or $0.471$ per flip.

Two more advantages follow from the same design. The probabilities may change at every step — a model that adapts to the text so far costs nothing extra, since only the current proportions matter. And the probabilities need not be dyadic, or even rational: the interval simply narrows by whatever factor the model gives.

5. Solving the practice problems

1. Which interval represents a message: narrow twice. The first symbol picks its piece; the second takes the same fraction of that piece, not of $[0, 1)$.
2. $-\log_2$ of the width for $a$ copies of $x$ ($p = \tfrac{1}{2}$) and $b$ of $y$ ($p = \tfrac{1}{4}$): the width is $2^{-a} 4^{-b}$, so the answer is $a + 2b$.
3. Bits with the rule $\lceil -\log_2 w \rceil + 1$: since $a + 2b$ is already a whole number, the answer is $a + 2b + 1$.
4. Why it approaches the entropy: the rounding is paid once for the whole message, not once per symbol.

Common mistakes

• Taking the second symbol's piece from $[0, 1)$ instead of from the current interval.
• Writing $a + b$ instead of $a + 2b$: a symbol of probability $\tfrac{1}{4}$ contributes two bits.
• Forgetting the $+1$ (or adding $2$) in the bit count: the rule stated in the question is $\lceil -\log_2 w \rceil + 1$.

6. Coding $bac$

1. $a = [0, 0.5)$, $b = [0.5, 0.75)$, $c = [0.75, 1)$. After $b$: $[0.5, 0.75)$. After $a$: left half, $[0.5, 0.625)$.

   Zoom twice.

2. After $c$: last quarter of that, $[0.59375, 0.625)$, width $2^{-5} = P(b) P(a) P(c)$. The binary fraction $0.10011 = 0.59375$ lies inside: five bits, plus one for safety, for a message of $5$ bits of information.

   Width is the product of the probabilities.

7. Where Huffman loses and arithmetic coding does not

1. A coin with $P(\text{heads}) = 0.9$: $H = 0.469$, but any symbol code spends $1$ bit per flip.

2. Arithmetic coding of $1000$ flips spends about $-\log_2 P(x^{1000}) + 2 \approx 469 + 2$ bits: $0.471$ per flip, essentially the entropy.

   Two bits of overhead for the whole message.

8. The interval for $cc$

1. First $c$: the last quarter of $[0, 1)$, that is $[0.75, 1)$, of width $0.25$.

2. Second $c$: the last quarter of that, $0.75 + 0.75 \cdot 0.25 = 0.9375$ to $1$.

   The proportions repeat inside every interval.

3. $[0.9375, 1)$, width $0.0625 = P(c)^2$.

9. Bits for a $12$-symbol message

1. $8$ copies of $x$ ($p = \tfrac{1}{2}$) and $4$ of $y$ ($p = \tfrac{1}{4}$).

2. Width $= 2^{-8} \cdot 4^{-4} = 2^{-16}$, so $-\log_2 w = 16$.

   $8 \cdot 1 + 4 \cdot 2 = 16$ bits of information in the message.

3. $\lceil 16 \rceil + 1 = 17$ bits: one bit of overhead spread over twelve symbols.

10. Your turn: the interval for $cc$

1. After $c$: $[0.75, 1)$; then the last quarter of that.

2. Your turn: work this step out. Its working is at the end of the packet.

   $[0.9375, 1)$, width $\tfrac{1}{16} = P(c)^2$.

11. Guided practice

An arithmetic coder uses $a = [0, 0.5)$, $b = [0.5, 0.75)$, $c = [0.75, 1)$. Which interval $[\text{lo}, \text{hi})$ represents the message $cc$?

lo = _lo, hi = _hi

12. Guided practice

Symbols $x$ and $y$ have probabilities $\tfrac{1}{2}$ and $\tfrac{1}{4}$. After arithmetic-coding a message with $1$ copies of $x$ and $2$ copies of $y$, what is $-\log_2$ of the interval width?

Computed value: _answer

13. Practice

The same message, $3$ copies of $x$ (probability $\tfrac{1}{2}$) and $1$ copies of $y$ (probability $\tfrac{1}{4}$), is arithmetic-coded with the rule 'use $\lceil -\log_2 \text{width} \rceil + 1$ bits'. How many bits does it take?

Computed value: _answer

14. Practice

An arithmetic coder uses $a = [0, 0.5)$, $b = [0.5, 0.75)$, $c = [0.75, 1)$. Which interval $[\text{lo}, \text{hi})$ represents the message $ba$?

lo = _lo, hi = _hi

15. Somewhere new

Why does arithmetic coding approach the entropy where a Huffman symbol code may not?

• It rounds once per message instead of once per symbol, so the overhead is about two bits in total
• It uses shorter codewords for every symbol
• It can go below the entropy for long messages
• It only works for dyadic probabilities

16. Lesson test

Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.

17. Test question

Symbols $x$ and $y$ have probabilities $\tfrac{1}{2}$ and $\tfrac{1}{4}$. After arithmetic-coding a message with $2$ copies of $x$ and $5$ copies of $y$, what is $-\log_2$ of the interval width?

Computed value: _answer

18. What you can do now

You can find the entropy rate of a source with memory and code a message to within two bits of its information. This closes source coding; the next unit turns to noisy channels.

Working for the steps left to you

10. Your turn: the interval for $cc$, step 2