IS2120 Homework 4
Due February 11
Homework 4
1. Consider a symbol set with two symbols, having probabilities p
and q, with p>q. Show that the Huffman Code of the second
extension has an average length of 2 if q>p*p. Otherwise,
the average length is a function of p. What is this function?
2. Consider the probabilty distribution on p.70: 1/2, 1/4, 1/8,
1/16,... (note that the probability of the LAST symbol is the same as
that of the next-to-last). Compare the average lengths with that of a
block code for n=2, 4, 8 (as is done for the Zipf distributuion
in the first three rows of p.71)
3. For the following Markov process, compute the probabilities
for a double transition and give the equilibrium probabilities, p(a),
p(b), p(c):
p(a|a) = 0.8 p(b|a) = 0.1 p(c|a) = 0.1
p(a|b) = 0.1 p(b|b) = 0.8 p(c|b) = 0.1
p(a|c) = 0.1 p(b|c) = 0.1 p(c|c) = 0.8
[HINT: The equilibrium probabiolities should be evident by inspection --
no computation required]
4. Find a dynamic Huffman Code for the following process, and compute
its average length.
p(a|a) = 0.5 p(b|a) = 0.5 p(c|a) = 0.0 p(d|a) = 0.0
p(a|b) = 0.1 p(b|b) = 0.5 p(c|b) = 0.3 p(d|b) = 0.1
p(a|c) = 0.0 p(b|c) = 0.0 p(c|c) = 0.0 p(d|c) = 1.0
p(a|d) = 0.1 p(b|d) = 0.2 p(c|d) = 0.3 p(d|d) = 0.4