Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 3 / 3G / Solution

Order the prescribed lengths as $l_1\le \cdots \le l_N$. Construct a prefix code on the binary tree. At depth $l_i$, previously assigned codewords exclude ${\sum }_{j<i}{2}^{l_i-l_j}$ of the $2^{l_i}$ vertices. The Kraft inequality impliesso an available vertex can be assigned to the next symbol. None of the assigned words is a prefix of another. Reading each word up to the next assigned vertex gives unique decoding, so this constructs the required uniquely decodable code.

For completeness the same length inequality is necessary even for a uniquely decodable code which is not a prefix code. Write $K={\sum }_a{2}^{-l(a)}$ and $L={\max }_{a}l(a)$. For $r$ successive symbols, distinct symbol strings have distinct concatenated codewords. At total length $j$ there are at most $2^j$ such strings. ThereforeTaking $r$th roots and letting $r\to \infty$ gives $K\le 1$. This is the McMillan inequality.

Set $q(a)=2^{-l(a)}/K$. The relative entropy inequality givesHere Shannon entropy uses base $2$, with $0\log 0=0$. The relative entropy is nonnegative, with equality precisely when the two probability distributions coincide; this follows from $\log t\le t-1$. Consequently equality holds exactly whenIn particular all alphabet symbols must have positive probability for equality with finite prescribed lengths.