Source Coding Theorem

Entropy is the exact bits-per-symbol floor for lossless compression.

The idea

Theorem (Source coding theorem).

Let a memoryless source emit symbols with probabilities $p_i$, and let $H(X) = -\sum_i p_i \log_2 p_i$ be its entropy in bits. Every uniquely decodable binary code for the source, with codeword lengths $\ell_i$, has expected length $L = \sum_i p_i \ell_i$ satisfying $H(X) \le L,$ and some code achieves $L < H(X) + 1$.

The entropy is therefore the exact floor, in bits per symbol, for lossless compression, and it is attainable to within one bit.

The codes in question are constrained by Kraft's inequality: the lengths of a uniquely decodable code must satisfy $\sum_i 2^{-\ell_i} \le 1$. The figure recalls where that constraint comes from: codewords sit as nodes of the binary code tree, with depth equal to length, and a codeword of length $\ell$ excludes the fraction $2^{-\ell}$ of the tree below it — regions that may not overlap.

The leftover bit is the cost of coding one symbol at a time. Coding blocks of $n$ symbols together spreads the same overhead across all $n$ of them, so the rate per symbol approaches $H(X)$.

Ways to work on it

• Walkthrough. Entropy as the compression floor, achievable to within one bit.
• Practice. Compute a source's entropy — its lossless compression floor.
• Hardest. Beat the per-symbol bound with block coding toward the entropy floor.

Not sure where to start? Take the ten-question placement test.