ELEC 619A
Selected Topics in Digital Communications: Information Theory

Assignments

1. The sum of the faces of two normal dice (six sided) when thrown is 7. How much information does this fact supply us with?
   Note: Outcomes such as (6,1) and (1,6) are to be considered as being different.
2. Of a group of students, 25% are not suitable for the University of Victoria. As the result of a selection, however, only 75% of these unsuitable students are rejected. 50% of all students are rejected.
   1. How much information does one receive if a student, who knows that he is not suitable for UVic, hears the results of the selection?
   2. Answer the previous question if the selection is determined by tossing a coin.
   3. Compare the above results and give an explanation for the difference.
3. Course Notes Problem 1.2
4. Course Notes Problem 1.3
5. Course Notes Problem 1.5
6. A picture is composed of 20 rows and 20 columns of dots, each dot having three possible degrees of darkness. Calculate the information in the picture:
   1. assuming the shades are equally probable
   2. assuming the probabilities are 1/8, 1/4 and 5/8
7. The World Series is a seven-game series that terminates as soon as either team wins 4 games. Let X be the random variable that represents the outcome of a World Series between teams A and B. Possible values of X are AAAA, BABABAB, and BBBAAAA. Let Y be the number of games played, which ranges from 4 to 7. Assuming A and B are equally matched and that the games are independent, calculate H(X), H(Y), H(Y|X) and H(X|Y).
8. Given a discrete random variable X with values x₁, ..., x_M, define a random variable Y by Y = g(X), where g is an arbitrary function. Show that H(Y) &le H(X). Under what conditions on the function g will there be equality?
9. A simple language consists of three symbols, &alpha, &beta, &gamma, grouped into words of one, two or three symbols. The only single symbol word is &alpha . Two-symbol words either begin or end with &alpha, and three-symbol words always have &alpha as the middle symbol (and nowhere else). All words are equiprobable. Find the average amount of information per symbol.

1. Course Notes Problem 2.1
2. Course Notes Problem 2.2
3. Course Notes Problem 2.3
4. A source S has eight symbols with probabilities P1 to P8, respectively. Assume the Pi are ordered such that P1 > P2 > P3 = P4 = P5 >= P6 >= P7 > P8. Construct a binary Huffman code for this source.
5. An information source has 3 symbols y1 to y3 with respective probabilities of .1, .1, and .8. Design a ternary fixed length source compaction code for this source which has a low probability of error.
6. An information source has 8 different symbols u1 to u8 with respective probabilities of 1/4, 1/4, 1/8, 1/8, 1/8, 1/16, 1/32 and 1/32. This source must be coded using three symbols a,b and c.
   1. Determine the code and the efficiency of the code using the methods of Fano, Huffman and Tunstall.
   2. Determine a best possible prefix code and the efficiency of the code for the case when the symbol b may never be followed by another b.
7. A source has symbols x1, x2, x3 and x4 with probabilities 0.5, 0.3, 0.15 and 0.05, respectively. This source is encoded into an arithmetic code with the intervals assigned so that the larger probabilities are on the left. Find as many of the first bits as possible of the codeword corresponding to x2 x1 x1 x4 x3 x1 x3 ... Compare the efficiency of this code with that of the corresponding Huffman code.
8. A source has symbols x1, x2 and x3 with probabilities 0.8, 0.02 and 0.18, respectively. Decode the arithmetic code sequence .110001 for these probabilities. Assume the symbols are arranged in numeric order (x1,x2,x3) in the range [0,1).
9. A source S = {a,b,c,d} emits the following string of symbols
   bccacbddccccccccccdcaccdca
   Using the Lempel-Ziv algorithm, encode this sequence and find the code dictionary and the transmitted sequence.

1. A DMC has transition probability matrix
   
   | .985 .005 |
   | .010 .010 |
   | .005 .985 |
   
   Determine the capacity of this channel.
2. Course Notes Problem 3.2
3. Course Notes Problem 3.3, but use N=6.
4. Course Notes Problem 3.5
5. Consider the Z channel
   1. Determine H(Y)
   2. Determine I(X;Y)
   3. Derive the channel capacity C

Aaron Gulliver
2008-11-24