Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 37 ยท Huffman and Arithmetic Coding

Arithmetic Coding

Arithmetic coding represents a whole message as one number inside a shrinking interval. Implement an exact encoder and decoder with Fractions and see why it gets within 2 bits of the entropy.

Huffman coding gives every symbol its own codeword, so it must spend a whole number of bits per symbol. Arithmetic coding drops that restriction. It encodes the entire message as a single number in the interval [0, 1), and the more probable the message, the wider its interval, and the fewer bits are needed to name a number inside it. The result: a total length within 2 bits of the ideal -log2 P(message), no matter how long the message is.

The idea: nested intervals

Split [0, 1) into sub-intervals, one per symbol, with widths equal to the probabilities. To encode a message, pick the interval of the first symbol, split that into sub-intervals in the same proportions, pick the second symbol's piece, and continue. After the last symbol, the interval has width equal to the product of all the probabilities, P(message). Any number inside it identifies the message.

flowchart LR
    A["[0, 1)"] -->|"symbol a: [0, 0.5)"| B["[0, 0.5)"]
    B -->|"symbol b: 0.5..0.75 of it"| C["[0.25, 0.375)"]
    C -->|"symbol a: first half"| D["[0.25, 0.3125)"]

Probabilities a = 1/2, b = 1/4, c = 1/4. Encoding "aba" narrows the interval step by step.

Intervals for a short message

We use Python's exact Fraction type so there is no rounding at all. First the narrowing process alone.

Python Narrow the interval symbol by symbol

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After abac the width is 1/2 * 1/4 * 1/2 * 1/4 = 1/64, so naming a number inside needs about log2(64) = 6 bits.

Choosing the bits

The final interval is [low, low + width). We need a binary cell [m / 2^k, (m+1) / 2^k) that lies entirely inside it (that also makes the code prefix-free). The shortest such k is at least -log2 width and at most ceil(-log2 width) + 1. The codeword is just the k bits of m.

To decode, the receiver knows the probabilities and the message length. It computes the value m / 2^k, finds which symbol's sub-interval contains it, narrows the interval exactly as the encoder did, and repeats.

Python Exact arithmetic encoder and decoder

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each code length is within 1 to 2 bits of the ideal -log2 P(message), and every message decodes back correctly. The shortest message aaaaaaaa costs just 8 bits... but notice its ideal cost is also 8, because a has probability 1/2.

The 2-bit guarantee

The code length satisfies

TEXT
-log2 P(msg)  <=  length  <  -log2 P(msg) + 2

Dividing by the message length n, the per-symbol cost is within 2/n bits of the entropy of the model: the overhead does not grow with n, while Huffman can waste up to a fraction of a bit on every symbol. For skewed sources this is the difference between near-optimal and many times optimal.

Python Arithmetic coding vs. Huffman on a skewed source

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For n = 1000 the arithmetic bound is under a third of the 1000 bits Huffman needs, near 0.31 bits per symbol (the entropy is 0.286).

Why not just use this?

Exact fractions are fine for teaching, but their numerators and denominators grow with every symbol. Real coders keep the interval in fixed-size integers (typically 32 bits) and output bits as soon as the leading bits of low and high agree, shifting the interval back up (renormalization). This is the subject of the next lesson. The mathematics stays the same; only the arithmetic is approximated, at a cost of a tiny fraction of a percent.

Decoders need to know where the message ends. Either send the length n first, or add a special end-of-message symbol with its own small probability. Without one, extra zero bits can decode as more symbols.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does an arithmetic coder produce for a whole message?

    Each symbol shrinks the interval in proportion to its probability; any number in the final interval identifies the message.
  2. 2. The final interval of a message has width equal to

    Every symbol multiplies the width by its probability.
  3. 3. How close is the arithmetic code length to -log2 P(message)?

    Length is between -log2 P and -log2 P + 2, so the overhead is a constant, not per symbol.
  4. 4. Why does a real arithmetic coder renormalize with integers?

    Output leading bits as soon as they are settled and rescale the interval to stay in a fixed word size.

Summary

  • Arithmetic coding maps a message to a sub-interval of [0, 1) whose width is P(message).
  • Any binary fraction in the interval is a valid code; about -log2 P + 2 bits suffice.
  • Decoding replays the narrowing using the same probabilities; the decoder must know the message length or an end symbol.
  • The total overhead is constant, so arithmetic coding beats Huffman on skewed sources and handles changing probabilities naturally.
  • Real implementations use fixed-width integers and renormalization.

Next: Arithmetic Coding with Integers and Adaptive Models