= Solution
Let a memoryless source have probabilities $p_1,\ldots,p_m$, and let a uniquely decodable $D$-ary code have word lengths $\ell_i$ and mean length $L=\sum_i p_i\ell_i$. The <Shannon source coding theorem> states
$$
H_D(p)\leq L,
\qquad
H_D(p)=-\sum_i p_i\log_Dp_i,
$$
and that some <prefix code> satisfies
$$
H_D(p)\leq L<H_D(p)+1.
$$
For the lower bound, the <Kraft inequality> gives $K=\sum_iD^{-\ell_i}\leq1$. Set $q_i=D^{-\ell_i}/K$. The <Gibbs inequality>, or nonnegativity of <relative entropy>, gives
$$
0\leq\sum_i p_i\log_D\frac{p_i}{q_i}
=-H_D(p)+L+\log_DK.
$$
Therefore $L\geq H_D(p)-\log_DK\geq H_D(p)$.
For achievability choose $\ell_i=\lceil-\log_Dp_i\rceil$. Then $\sum_iD^{-\ell_i}\leq\sum_ip_i=1$, so the converse part of the Kraft theorem supplies a prefix code with these lengths, and
$$
L<\sum_i p_i(-\log_Dp_i+1)=H_D(p)+1.
$$
\b[Hence the entropy is the optimal mean code length up to less than one code symbol.]
Back to article page
