1

Problem sheet 4, 2005, Oct. 26  MT441 Channels

Ex. 1 Find the compact code over {0, 1} for a source that emits words w_{1}, … w_{6} with

P (w_{1}) = \frac{1}{3}, P (w_{2}) = \frac{1}{4}, P (w_{3}) = \frac{1}{6}, P (w_{4}) = P (w_{5}) = P (w_{6}) = \frac{1}{12}

and compare its average length with the upper and lower bounds given by the noiseless coding theorem.

Ex. 2 (easy) A message consisting of N binary digits is transmitted through a binary symmetric channel having error probability p. Show that the expected number of errors is Np.

Ex. 3 A code consists of 4 codewords c_{1} = 1000, c_{2} = 0110, c_{3} = 0001, c_{4} = 1111. Assume that the probabilities that these words occur are

P (c_{1}) = P (c_{2}) = \frac{1}{3}, P (c_{3}) = P (c_{4}) = \frac{1}{6}.

You use a binary symmetric channel with error probability p = \frac{1}{10}. You receive 1001. How should you decode (using the maximum likelihood method)? What is the error probability?

Ex. 4 Calculate the capacity of the binary erasure channel with error probability ε.

ROOM CHANGE: the Monday lecture needs to change the room to AG 24. (Arts building, take entrance close to Maths, then turn left, the room faces the maths department.

To be returned in one week, before the lecture. My web page contains a collection of related material. http://www.ma.rhul.ac.uk/∼elsholtz/WWW/lectures/0506mt441/lecture.html