tjaz

2. (Number of Typical Sequences) Design an algorithm for calculating PX(A(X)) and the number

jA(X)j of typical binary sequences x = (x1; : : : xn) with probability PX0(0) = p, a given , and

the length of the sequences n.

Optional: (Programming needed) What are the number of -typical sequences and PX(A(X)) for

p = 1/3 , = 0:046 and n = 1000.

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.

b) Prove that for any binary HUFFMAN code, if the most probable message symbol has probability

p1 < 1/3 , then that symbol must be assigned a codeword of length 2.

1

jA(X)j of typical binary sequences x = (x1; : : : xn) with probability PX0(0) = p, a given , and

the length of the sequences n.

Optional: (Programming needed) What are the number of -typical sequences and PX(A(X)) for

p = 1/3 , = 0:046 and n = 1000.

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.

b) Prove that for any binary HUFFMAN code, if the most probable message symbol has probability

p1 < 1/3 , then that symbol must be assigned a codeword of length 2.

1