Past exam of the communication Theory course of the University of Oxford / 2009 / 2 / c

Suppose every sum of two distinct probabilities exceeds every third probability. If an optimal code were not a block code, part (b) gives two deepest sibling leaves $x,y$ at depth $L>n$ and a leaf $z$ at depth $\ell <n$. Replace the sibling pair by a leaf labelled $z$, and replace the former $z$ leaf by two children labelled $x,y$. The resulting tree is still a prefix tree, and other word lengths are unchanged. The change in expected length isHere $L-\ell -1\ge 1$. This contradicts optimality. Thus every optimal code is a block code.

Conversely, suppose distinct $x,y,z$ satisfy $p_x+p_y\le p_z$. Starting with the complete length-$n$ code, arrange $x,y$ as a sibling pair, which is possible by permuting the source labels. Its parent at depth $n-1$ does not contain $z$. Label that parent $z$, and split the old $z$ leaf into children $x,y$. This gives lengths $n-1$ for $z$, $n+1$ for $x,y$, and $n$ otherwise, with expected lengthIf the optimal mean length is below $n$, no optimal code can be a block code: any injective binary block code for $2^n$ symbols has length at least $n$. If the optimal mean is $n$, the constructed non-block code itself is optimal. In either case there is an optimal non-block code. This proves the reverse implication, including the equality case, and hence the strict inequality in the criterion is necessary.

This is the optimality of a fixed-length code for a power-of-two alphabet.