Past exam of the communication Theory course of the University of Oxford / 2008 / 4

A binary prefix code assigns each source symbol a distinct finite binary word, with no assigned word a prefix of another. It is instantaneous because a decoder can identify the symbol as soon as its last digit arrives, without reading digits from the next word. Such a code is optimal when it minimizesamong all binary prefix codes for that source distribution. Symbols of zero probability may be removed from the optimization.

Make a rooted binary tree with an edge labelled zero for the first branch and one for the second branch at each interior node. Put each source symbol at the leaf reached by following the successive digits of its codeword. The prefix property ensures no assigned word ends at an ancestor of another assigned word.

The route of a codeword is its root-to-leaf path; its length is the number of edges on that path, equal to the number of binary digits in the word. For an optimal tree with positive leaf probabilities, every interior node has two children: a node with just one child could be contracted, shortening all words below it and strictly reducing the expected length. The diagram in the earlier Huffman calculation is one such full binary tree.

The redundancy is $R=\bar{\ell }-H(X)$, measured in bits per source symbol. Write $s_v={\sigma }_0(v)+{\sigma }_1(v)$ for the total mass passing through interior node $v$. Counting each codeword's length as one for each interior node its route visits givesThe entropy can be split into the conditional binary decisions along that route. Algebraically each node contributesSumming telescopes: each non-root interior mass appears once positively as a parent and once negatively as a child. The root term is $1{\log }_{2}1=0$ and the remaining leaf terms sum to $-{\sum }_x{p}_x{\log }_2{p}_x=H(X)$. HenceSubtracting this identity from the expected-length identity provesThus redundancy is the sum of the probability-weighted imbalances of the binary branch decisions. Nodes with no mass contribute zero by continuity. The formula holds for every full prefix tree, even without optimality.