= Solution
For <Shannon-Fano coding>, order the symbols by decreasing probability and recursively split each current list into two contiguous groups with total probabilities as close as possible. Label the two branches $0$ and $1$; the path to a symbol is its <prefix code> word. Here the first split is $\{a\}$ of weight $.4$ against $\{b,c,d\}$ of weight $.6$. The latter splits into $\{b\}$ and $\{c,d\}$, each of weight $.3$. One answer is
$$
\boxed{a:0,\qquad b:10,\qquad c:110,\qquad d:111.}
$$
For <Huffman coding>, repeatedly merge the two least-probable nodes and then read the resulting binary tree from the root. Merge $c,d$ to weight $.3$, merge this node with $b$ to weight $.6$, and merge with $a$. The same displayed <prefix code> results. Its mean length is $.4+2(.3)+3(.2)+3(.1)=\boxed{1.9\text{ bits per symbol}}$. Choices at ties and exchange of binary labels yield other equivalent codes. <Huffman coding> minimizes mean length among binary <prefix codes>; the top-down Shannon-Fano construction does not have that general optimality guarantee.
Back to article page
