Kraft–McMillan inequality

Remarks

Part 1 is due to McMillan and part 2 to Kraft. Since every prefix code is uniquely decodable, the inequality, the existence of a prefix code and the existence of a uniquely decodable code with the given lengths are all equivalent.

For part 2, sort the lengths so that $\ell_1 \le \dots \le \ell_n$ and pick codewords one by one as leaves of the complete $D$-ary tree. The inequality guarantees that a free node of depth $\ell_i$ remains at each step. For part 1, let $S = \sum_i D^{-\ell_i}$ and $\ell = \max_i \ell_i$. Expanding $S^k$ groups the terms by the total length $m$ of $k$ codewords, and unique decodability allows at most $D^m$ such sequences for each $m$. So $S^k \le k \ell$ for every $k$, which forces $S \le 1$.

Example: the binary variable-length code $\set{0, 10, 110, 111}$ is a prefix code, and $2^{-1} + 2^{-2} + 2^{-3} + 2^{-3} = 1$. Without unique decodability part 1 fails: the code $\set{0, 1, 01}$ has $2^{-1} + 2^{-1} + 2^{-2} = 5/4 > 1$, and the string $01$ can be read as one codeword or as two.

Going deeper

For a student

The inequality turns questions about codes into questions about numbers. For example, the minimum expected length of a uniquely decodable code is found by minimizing $\sum_i p_i \ell_i$ subject to $\sum_i D^{-\ell_i} \le 1$. This leads to the lower bound by the entropy in Shannon's source coding theorem. Part 1 also shows that nothing is lost by restricting to prefix codes, which can be decoded symbol by symbol.