B1.14

Information Theory
Part II, 2003

A binary Huffman code is used for encoding symbols 1,,m1, \ldots, m occurring with probabilities p1pm>0p_{1} \geqslant \ldots \geqslant p_{m}>0 where 1jmpj=1\sum_{1 \leqslant j \leqslant m} p_{j}=1. Let s1s_{1} be the length of a shortest codeword and sms_{m} of a longest codeword. Determine the maximal and minimal values of s1s_{1} and sms_{m}, and find binary trees for which they are attained.