Paper 1, Section I, G

Coding and Cryptography
Part II, 2016

Find the average length of an optimum decipherable binary code for a source that emits five words with probabilities

0.25,0.15,0.15,0.2,0.250.25,0.15,0.15,0.2,0.25

Show that, if a source emits NN words (with N2N \geqslant 2 ), and if l1,,lNl_{1}, \ldots, l_{N} are the lengths of the codewords in an optimum encoding over the binary alphabet, then

l1++lN12(N2+N2).l_{1}+\cdots+l_{N} \leqslant \frac{1}{2}\left(N^{2}+N-2\right) .

[You may assume that an optimum encoding can be given by a Huffman encoding.]