Shannon's source coding theorem

Remarks

For part 1, the Kraft–McMillan inequality gives $\sum_x D^{-\abs{C(x)}} \le 1$. Then $L(C) - H_D(X)$ is a relative entropy plus the non-negative number $-\log_D \sum_x D^{-\abs{C(x)}}$, so it is non-negative by Gibbs' inequality. For part 2, the lengths $\ell(x) = \lceil -\log_D p(x) \rceil$ satisfy the Kraft inequality, so a prefix code with these lengths exists, and $\ell(x) < -\log_D p(x) + 1$. Part 3 follows by applying parts 1 and 2 to the block, since its entropy is $k H_D(X)$, which gives $k H_D(X) \le L_k^* < k H_D(X) + 1$.

Equality holds in part 1 if and only if $p(x) = D^{-\abs{C(x)}}$ for every $x$. Example: if $X$ takes the values $a, b, c$ with probabilities $1/2, 1/4, 1/4$, then $H_2(X) = 3/2$, and the binary prefix code $a \mapsto 0$, $b \mapsto 10$, $c \mapsto 11$ has expected length exactly $3/2$. Without unique decodability part 1 fails: the code $a \mapsto 0$, $b \mapsto 1$, $c \mapsto 01$ has expected length $5/4 < 3/2$, but it cannot be decoded without ambiguity.

Going deeper

For a student

Part 1 is the converse and part 2 the achievability; together they fix the optimal compression rate as $H_D(X)$ per symbol. The Huffman code gives an optimal prefix code for each block, so it also achieves the bound of part 3. Shannon also stated a fixed-length version. Blocks of $k$ source symbols can be coded with about $k H_D(X)$ code symbols and an error probability tending to $0$. This fails at any rate below $H_D(X)$ code symbols per source symbol. That version rests on the asymptotic equipartition property. The theorem is the model for the channel coding theorem, which plays the same role for transmission over a noisy channel.