Paper 1, Section I, G
Part II, 2016
Find the average length of an optimum decipherable binary code for a source that emits five words with probabilities
Show that, if a source emits words (with ), and if are the lengths of the codewords in an optimum encoding over the binary alphabet, then
[You may assume that an optimum encoding can be given by a Huffman encoding.]