Lossless coding begins with a purely combinatorial constraint: codeword lengths cannot be arbitrary if unique decoding is required.
Prefix code
Definition. A binary code \(c:\mathcal X\to\{0,1\}^*\) is prefix-free if no codeword is a prefix of another. Its length function is \(\ell(x)=|c(x)|\).
Kraft-McMillan inequality
Theorem. A set of integer lengths \(\{\ell(x):x\in\mathcal X\}\) is realized by a binary prefix code only if \[ \sum_{x\in\mathcal X}2^{-\ell(x)}\le1. \] Conversely, every integer length sequence satisfying this inequality can be realized by a prefix code.
Proof by binary trees
Proof. A prefix code corresponds to leaves in the infinite binary tree. A leaf at depth \(\ell\) occupies fraction \(2^{-\ell}\) of the boundary. Prefix-freeness makes these boundary cylinders disjoint, giving the inequality. The converse constructs leaves greedily in lexicographic order whenever the remaining Kraft mass permits it.
Expected length lower bound
Corollary. For any prefix code for \(X\), \[ \mathbb E\ell(X)\ge H_2(X), \] where \(H_2\) is entropy in bits. The proof compares \(P(x)\) to the distribution proportional to \(2^{-\ell(x)}\) and uses nonnegativity of relative entropy.
Uniquely decodable and prefix codes
Definition. A \(D\)-ary code maps each source symbol \(x\) to a finite string over an alphabet of size \(D\). It is prefix-free if no codeword is a prefix of another. It is uniquely decodable if every concatenation of codewords has a unique parsing.
Every prefix code is instantaneously decodable and hence uniquely decodable. The converse is false, but both classes obey the same length constraint.
Kraft inequality
Theorem. If codeword lengths \(\ell_1,\ldots,\ell_m\) come from a \(D\)-ary prefix code, then \[ \sum_{i=1}^mD^{-\ell_i}\le1. \] Conversely, every finite integer length sequence satisfying this inequality is realized by a prefix code.
Proof. Represent strings as nodes in a full \(D\)-ary tree. A codeword at depth \(\ell_i\) owns a subtree containing \(D^{L-\ell_i}\) leaves at common depth \(L\ge\max_i\ell_i\). Prefix-freeness makes these leaf sets disjoint, so \(\sum_iD^{L-\ell_i}\le D^L\), proving necessity. For sufficiency, order lengths increasingly and assign each codeword the lexicographically first available tree node at its depth. The Kraft sum guarantees that earlier subtrees never exhaust all nodes at the next required depth.
McMillan inequality
Theorem. The same Kraft inequality holds for every uniquely decodable \(D\)-ary code.
Proof. Let \(K=\sum_iD^{-\ell_i}\). For concatenations of \(n\) codewords, \[ K^n=\sum_{i_1,\ldots,i_n}D^{-(\ell_{i_1}+\cdots+\ell_{i_n})}. \] Unique decodability implies that at any total length \(r\), at most \(D^r\) concatenations occur. Since total lengths range from \(n\ell_{\min}\) to \(n\ell_{\max}\), \[ K^n\le n(\ell_{\max}-\ell_{\min})+1. \] Taking \(n\)th roots and letting \(n\to\infty\) yields \(K\le1\).
Shannon lengths
Proposition. For source law \(P\), choose \[ \ell(x)=\left\lceil-\log_D P(x)\right\rceil. \] These lengths satisfy Kraft and have expected length \[ H_D(X)\le\mathbb E\ell(X)<H_D(X)+1, \] where \(H_D\) uses logarithm base \(D\).
Proof. \(D^{-\ell(x)}\le P(x)\), so Kraft holds. Also \(-\log_DP(x)\le\ell(x)<-\log_DP(x)+1\); average.
Entropy lower bound on expected length
Theorem. Every uniquely decodable \(D\)-ary code satisfies \[ \mathbb E\ell(X)\ge H_D(X). \]
Proof. Let \(K=\sum_xD^{-\ell(x)}\le1\) and define \(q(x)=D^{-\ell(x)}/K\). Then \[ D(P\|q)= -H_D(P)+\mathbb E\ell(X)+\log_DK\ge0. \] Hence \(\mathbb E\ell\ge H_D(P)-\log_DK\ge H_D(P)\).
Huffman coding
Theorem. Huffman's algorithm repeatedly merges the two least probable symbols and produces a binary prefix code with minimum expected length among all binary prefix codes.
Proof outline. In an optimal full binary tree, the two least probable symbols can be placed as siblings at maximum depth by an exchange argument: swapping a less probable symbol downward cannot increase expected length. Merge these siblings into one meta-symbol with their combined probability. Any optimal code for the reduced alphabet, expanded by one bit for the siblings, is optimal for the original alphabet. Induct.
Dyadic distributions and exact equality
Corollary. Expected length equals entropy exactly when \(P(x)=D^{-\ell(x)}\) for integer lengths satisfying Kraft with equality. Such distributions are \(D\)-adic.
Block coding reduces integer overhead
Proposition. Applying Shannon coding to iid blocks \(X^n\) gives \[ H_D(X)\le\frac1n\mathbb E\ell(X^n) <H_D(X)+\frac1n. \]
Integer code lengths impose less than one symbol of overhead per block, so their per-source-symbol cost vanishes as block length grows.