Entropy Coding from Scratch — From Huffman to Arithmetic Coding

"Information content becomes code length" — that one line is all of compression. From Shannon's bound to building a Huffman code by hand, the integer-bit ceiling, the arithmetic coders and ANS that break it, and what is actually running inside JPEG, PNG, H.264 and zstd. Ending with how to diagnose a compression ratio that has stopped improving.

Why Morse code was already right

In Morse, the letter E — the most common in English — is a single dot, while the rare Q is dash-dash-dot-dash. The inventors of 1837 knew no information theory, but they had the principle by instinct: frequent things get short codes.

In 1948 Shannon gave that instinct an exact form, and went further than "should be shorter": he pinned down how short it can possibly get. Entropy coding is the family of techniques for approaching that bound. It is the last stage inside JPEG, inside PNG, inside gzip, inside H.264 — always there, always last.

The central idea: information content is code length

In the information theory article we defined the information content of an event $x$ as $-\log_2 p(x)$ — the "surprise", larger for rarer events. Coding theory gives that quantity a physical meaning.

What this says, plainly, is that a symbol occurring with probability $p$ should be given $-\log_2 p$ bits. A symbol at $1/2$ gets one bit, at $1/4$ two bits, at $1/256$ eight bits. An abstract quantity called surprise turns directly into a concrete count of bits. That is the most beautiful thing in this field.

Under the ideal assignment, the average code length per symbol is the expectation of the information content — the entropy itself.

Put in words: walk over every symbol the source can emit, multiply how often it turns up ($p(x)$) by how many bits it deserves ($-\log_2 p(x)$), and add all of those up. $H(p)$ is that weighted average — the bill you pay per symbol once every symbol has been priced correctly.

Shannon's source coding theorem then guarantees that this is an unbreakable floor: no uniquely decodable code has an average length below $H(p)$, and simultaneously, anything below $H(p) + 1$ bits is always achievable. Both the ceiling and the floor of compression come from this single quantity.

Prefix codes and the Kraft inequality

Code lengths cannot be chosen freely. To decode without separators, no codeword may be a prefix of another — a prefix code. Use both 0 and 01 and you cannot commit after reading 0.

That constraint collapses into a single inequality on the lengths $\ell_i$:

This is the Kraft inequality. Read it as: short codewords are expensive. A one-bit codeword consumes $1/2$ of the budget, a two-bit one $1/4$, and the total may not exceed 1. "Frequent symbols get short codes" becomes an optimisation problem precisely because they are competing for a finite budget.

Building a Huffman code by hand

The procedure for the optimal prefix code is startlingly short: take the two least probable items, merge them, and put the sum back. Repeat until one item remains.

Try it on five symbols: $p(A)=0.40$, $p(B)=0.20$, $p(C)=0.20$, $p(D)=0.10$, $p(E)=0.10$.

1. The two smallest, $D$ and $E$ (0.10 each), merge into $DE = 0.20$
2. Now $A\,0.40,\ B\,0.20,\ C\,0.20,\ DE\,0.20$. Take $B$ and $C$ as the two smallest, giving $BC = 0.40$
3. Now $A\,0.40,\ BC\,0.40,\ DE\,0.20$. The two smallest, $DE$ and $A$, merge into $ADE = 0.60$
4. Merge $ADE$ and $BC$ at the root

Label the branches 0 and 1 and you get $A=00$, $B=10$, $C=11$, $D=010$, $E=011$ — none a prefix of another. The average code length is

$$0.4(2) + 0.2(2) + 0.2(2) + 0.1(3) + 0.1(3) = 2.20 \ \text{bits}$$

Read in words, each term is "how often that symbol appears × how long its codeword is": $A$ turns up 40% of the time and costs 2 bits, $D$ turns up 10% of the time and costs 3. The total is what one average symbol costs you.

That is measured against an entropy of $H = 2.12$ bits. Fixed-length coding of five symbols needs 3 bits, so we have gone 3.00 → 2.20 bits, sitting 0.08 above the theoretical floor. Huffman coding is provably optimal among codes that assign an integer number of bits per symbol, which means that 0.08 is not sloppiness — it is structural leakage.