Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 2 / 12H (Coding & Cryptography)

Shannon noiseless coding theorem says the minimum expected binary prefix-code length $L$ satisfies $H(X)\le L<H(X)+1$. Kraft and Gibbs give $H\le L$ for every prefix code. Taking lengths ${\ell }_i=\lceil -{\log }_2{p}_i\rceil$ satisfies Kraft because $\sum 2^{-{\ell }_i}\le 1$, and gives $L<\sum p_i(-{\log }_2{p}_i+1)=H+1$.

Equiprobability gives $H={\log }_{2}m$.

For $m=2^b$, assign every outcome one of the $b$-bit words. This complete fixed-length prefix code has expected length $b$ and meets the information entropy lower bound.

If two lengths differed by at least two, replacing two deepest sibling leaves by their parent and splitting a shallower leaf lowers total length, contradicting optimality. Thus lengths are $b=\lfloor {\log }_{2}m\rfloor$ and $b+1$. Kraft equality gives $n_b=2^{b+1}-m$ and $n_{b+1}=2m-2^{b+1}$, hence