3. (HUFFMAN and SHANNON-FANO Code) Consider the random variable X = fx1; :::; x7g with
P(x1) = 0:49, P(x2) = 0:26, P(x3) = 0:12, P(x4) = 0:04, P(x5) = 0:04, P(x6) = 0:03,
P(x7) = 0:02.
a) Construct a binary HUFFMAN code for X.
b) Construct a binary SHANNON-FANO code for X.
c) Compute the expected code length for the codes.
d) Construct a ternary HUFFMAN code for X.

4. (Optimal Codeword Length) Although the codeword lengths w(x) of an optimal variable length code
are complicated functions of the message probabilities pi = PX(xi), it can be said that less probable
symbols are encoded into longer codewords. Suppose that the message probabilities are given in
decreasing order p1 > p2 


 pn.
a) Prove that for any binary HUFFMAN code, if the most probable message symbol has probability
p1 > 2/5 , then that symbol must be assigned a codeword of length 1.