Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 1 / 3H (Coding & Cryptography)

Let a memoryless source have probabilities $p_1,\dots ,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 statesand that some prefix code satisfies

For the lower bound, the Kraft inequality gives $K={\sum }_i{D}^{-{\ell }_i}\le 1$. Set $q_i=D^{-{\ell }_i}/K$. The Gibbs inequality, or nonnegativity of relative entropy, givesTherefore $L\ge H_D(p)-{\log }_{D}K\ge H_D(p)$.

For achievability choose ${\ell }_i=\lceil -{\log }_D{p}_i\rceil$. Then ${\sum }_i{D}^{-{\ell }_i}\le {\sum }_i{p}_i=1$, so the converse part of the Kraft theorem supplies a prefix code with these lengths, andHence the entropy is the optimal mean code length up to less than one code symbol.