Kraft Inequality & Prefix Codes

Which codeword lengths a prefix code can realize, and the entropy bound.

The idea

Theorem (Kraft inequality).

A binary prefix code with codeword lengths $l_1, \ldots, l_m$ exists if and only if $\sum_{i=1}^{m} 2^{-l_i} \le 1.$

A prefix code assigns each source symbol a binary codeword so that no codeword is a prefix of any other. Codewords can then be sent back to back with no separators: a decoder reading left to right recognizes each codeword the moment it is complete.

The inequality says that a codeword of length $l$ spends $2^{-l}$ of a unit budget, and that the lengths alone decide whether a prefix code exists; the particular strings chosen never enter. The figure arranges the binary strings as the nodes of a binary tree, with depth equal to length, and places a code's words at its nodes.

Ways to work on it

• Walkthrough. The Kraft inequality and why prefix-code lengths must fit the unit budget.
• Practice. Decide whether a set of codeword lengths is achievable.
• Hardest. Fill an unknown length via Kraft, then meet the entropy bound.

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