Past exam of the mathematics course of the University of Cambridge / 2007 / ii / Paper 1 / 4G (Coding and Cryptography)

A uniquely decodable code is a map whose extension by concatenation to finite strings is injective. Write ${\ell }_j$ for its codeword lengths and assume the target alphabet has size $a\ge 2$. The Kraft–McMillan inequality gives $K={\sum }_j{a}^{-{\ell }_j}\le 1$. The Gibbs inequality says $D(p\Vert q)={\sum }_j{p}_j\log (p_j/q_j)\ge 0$ for probability distributions $p,q$, with the usual convention for zero probabilities.

Set $q_j=a^{-{\ell }_j}/K$. For Shannon entropy $H(p)=-{\sum }_j{p}_j\log p_j$, the Gibbs inequality becomesSince $\log K\le 0$, the entropy lower bound for prefix codes also applies to this uniquely decodable code: