tjaz

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.

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.