CS 6604, Assignment 1 - Due February 11, 2008

Please show your work

1. Given a source with a 15-symbol alphabet with the following probabilities:

   .2, .1, .1, .1, .1, .1, .08, .06, .04, .04, .02, .02, .02, .01, .01

   a) Compute the source entropy

   b) Compute a Shannon-Fano code for this alphabet

   c) Compute a Huffman code for this alphabet

   d) Compare the average code lengths for codes b) and c) with entropy

2. Suppose we are given random variables X and Y. The information learned about X by revealing Y is
   I(X|Y) = H(X) - H(X|Y) = - sum_i,j p(x_i,y_j) log₂ p(x_i) + sum_i,j p(x_i,y_j) log₂ p(x_i|y_j)

   Now, suppose a single unbiased die is tossed once. If the face of the die is 1, 2, 3, or 4, an unbiased coin is tossed once. If the face of the die is 5 or 6, the coin is tossed twice. Find the amount of information conveyed about the face of the die by the number of heads obtained.

3. Given the Markov source with transition matrix T = {{1/2, 1/2, 0}, {0, 1/3, 2/3}, {0, 1/2, 1/2}}, determine the entropy of the source with this model.

4. Given the Markov source with transition matrix T = {{1/3, 2/3, 0}, {1/4, 1/4, 1/2}, {0, 1/2, 1/2}}, determine the steady state probabilities.

5. Determine the Golomb codes for integers from 1 to 10 for m=2 and m=3. Given the integer sequence, <1,3,6,7,10,13,17,23,24,27,33,35,37,41,45>, determine the number of bits required to code the gaps using Golomb codes with m=2 and m=3.