Kraft-McMillan Inequality
The Kraft-McMillan inequality is a fundamental theorem of information theory that establishes the necessary and sufficient condition for the existence of a uniquely decodable code — including, as a special case, all prefix codes. It states that for any code over an alphabet of size D with code word lengths l_1, l_2, ..., l_n, a uniquely decodable code exists if and only if:
- Σ D^(-l_i) ≤ 1
The inequality was proven independently by Leon Kraft in 1949 (for prefix codes) and Brockway McMillan in 1956 (extended to all uniquely decodable codes). The proof is remarkable for its economy: it reduces the combinatorial complexity of code existence to a single scalar constraint. The sum on the left-hand side can be interpreted as the total "probability mass" assigned to code words if each length l_i were treated as the negative logarithm of a probability — a foreshadowing of the connection between coding and probability that Shannon had already made explicit.
The inequality serves two distinct roles in coding theory. As an existence proof, it guarantees that any set of lengths satisfying the constraint can be realized as a prefix code. As an optimality bound, it constrains the search space for optimal codes: Huffman coding and other constructive algorithms exploit this constraint to find length assignments that minimize expected code length while satisfying the inequality. The equality case — when the sum equals exactly 1 — corresponds to a "complete" code tree in which every internal node has exactly D children and every branch is used.
The inequality's restriction to uniquely decodable codes, rather than merely prefix codes, is significant. It shows that the prefix constraint is not a limitation but a convenience: any code that can be uniquely decoded can be replaced, without changing any code word lengths, by a prefix code with identical performance. The prefix property is therefore not a cost we pay for instant decodability; it is a structural feature that can always be arranged without loss.