Past exam of the information theory course of the University of Oxford / 2021 / 2 / c / Solution

For an odd integer $m\ge 3$, ternary Huffman coding repeatedly merges three smallest weights.

Start with one tree leaf for each source symbol, weighted by its probability. While more than one weighted object remains, choose the three objects with least weights, create their common tree parent with weight equal to their sum, and replace the three by that tree parent. Newly created tree parents participate in subsequent choices. Each merge reduces the number of objects by two; an odd number of objects therefore reaches three and then one, never an unmergeable pair. The final object is the tree root of the code tree.

Label the three outgoing edges at each internal vertex by $0,1,2$ in any order. The digits along the root-to-leaf graph path give each symbol's codeword. Tree leaves cannot be ancestors of other tree leaves, so this is a prefix code. Ties can be resolved arbitrarily. The expected codeword length is measured in trits, and equals the sum of all merge weights, because each merge adds one digit to every codeword below it.

The structural reason for merging three is that the positive-weight, odd-leaf case has a full ternary tree. Its deepest sibling codeword triple can receive the three least weights by exchanging tree leaf labels, and contracting that triple reduces the problem by two symbols. This explains the recursive construction; a separate optimality proof is not required here.