= Solution
The <Shannon entropy>, in bits, is
$$
H(A)=-\sum_ap_a\log_2p_a=\log_2 5-\frac15\approx\boxed{2.121928}.
$$
For a prescribed alphabet distribution and code alphabet, an <optimal code> is a <uniquely decodable code> minimizing expected codeword length. <Huffman coding> produces an optimal binary <prefix code>, and its minimum is also the minimum among binary <uniquely decodable codes>.
Two optimal binary <prefix codes>, listing words in the order $a,b,c,d,e$, are
$$
(00,01,10,110,111),\qquad(0,10,110,1110,1111).
$$
Their length vectors are $(2,2,2,3,3)$ and $(1,2,3,4,4)$, and both have \b[expected length $2.2$ bits]. To verify optimality rather than just equal length, run <Huffman coding>. First combine $d,e$ into a node of weight $0.2$. Among the resulting three weight-$0.2$ nodes, combining $b,c$ and then combining the remaining weight-$0.2$ node with one weight-$0.4$ node gives the first length vector. Instead combine $c$ with the $d,e$ node, then combine that weight-$0.4$ node with $b$, and finally with $a$; this gives the second. Each step combines two smallest current weights, so both constructions are <Huffman coding> trees. Ties therefore allow \b[different optimal length profiles].
Back to article page
