= Solution
The displayed <prefix code> has <expected codeword length> $3/2$ ternary digits per source symbol. Instead assign
$$
\boxed{c(1)=0,\qquad c(2)=1,\qquad c(3)=20,\qquad c(4)=21.}
$$
This is a <ternary prefix code>: the first two <codewords> end at distinct <tree children> of the <tree root>, and the other two start with $2$ and end at distinct <tree children> below it. No <codeword> is a prefix of another. Its <expected codeword length> is
$$
\frac12\cdot1+\frac14\cdot1+\frac18\cdot2+\frac18\cdot2=\frac54<\frac32.
$$
The reduction is \b[$1/4$ <trit> per source symbol], which already disproves optimality of the displayed code. The <ternary Huffman coding> construction below will produce this same improved <code tree>.
\Image[/past-exam-of-the-information-theory-course-of-the-university-of-oxford/2021-ternary-prefix-tree.png]
{title=An original ternary prefix tree with expected length 1.25 ternary digits per source symbol}
Back to article page
