1.I.4J

Coding and Cryptography
Part II, 2005

Briefly describe the methods of Shannon-Fano and Huffman for economical coding. Illustrate both methods by finding decipherable binary codings in the case where messages μ1,,μ5\mu_{1}, \ldots, \mu_{5} are emitted with probabilities 0.45,0.25,0.2,0.05,0.050.45,0.25,0.2,0.05,0.05. Compute the expected word length in each case.