= Solution
The <Shannon entropy>[entropy] is
$$
\boxed{H(S)=\frac{13}{4}-\frac{3\log_23+5\log_25}{16}}.
$$
To construct a <Huffman code>, work with <integer> weights $2,2,3,4,5$. Merge the two twos to make four. Of the remaining weights $3,4,4,5$, merge three with the original four to make seven, and merge the new four with five to make nine. Finally merge seven with nine. Resolving the tie in this way gives, for example,
$$
c(x_1)=110,\quad c(x_2)=111,\quad c(x_3)=00,\quad c(x_4)=01,\quad c(x_5)=10.
$$
This is a <prefix code> and <Huffman coding>[Huffman's optimality theorem] makes it optimal. Its expected length is
$$
\boxed{\bar\ell=3(1/8+1/8)+2(3/16+1/4+5/16)=9/4}.
$$
Different choices at a tied merge can give different optimal codewords with the same expected length.
\Image[/past-exam-of-the-communication-theory-course-of-the-university-of-oxford/2008-huffman-tree.png]
{title=An optimal five-symbol Huffman tree}
{description=Edge labels give the binary digits, leaf labels give the source symbols and their probabilities, and interior labels give total descendant probability.}
Back to article page
