= Solution
The <code-distribution correspondence> starts from the <Kraft inequality>. For codeword lengths $L(x)$ put
$$
K=\sum_x2^{-L(x)}\leq1,
\qquad
R(x)=\frac{2^{-L(x)}}K.
$$
Conversely, a probability mass function determines ideal lengths $-\log_2R(x)$, up to integer rounding. For the source law $P_n$,
$$
\begin{aligned}
\mathbb E L(X_1^n)
&=-\sum_xP_n(x)\log_2\{K R(x)\}\\
&=H(P_n)+D(P_n\|R)-\log_2K\\
&\geq H(X_1^n),
\end{aligned}
$$
using nonnegativity of <Kullback-Leibler divergence> and $K\leq1$.
Back to article page
