1

Problem sheet 5, 2005, Nov. 2  MT441 Channels

Ex. 1 Plot the real function C : [0, 1] → ℝ with C(p) = 1 + p log_{2} p + (1 − p) log_{2}(1 − p). Evaluate it for p = 0, p = 0.01, p = 0.02, p = 0.05, p = 0.2, p = 0.5, p = 0.99, p = 1 and explain what it has to do with channels.

Ex. 2 For a code with code word length n

• Given any codeword c⃗. Count how many vectors x⃗ ∈ V_{n} = {0, 1}^{n} have Hamming distance d(x⃗, c⃗) = t. Do the same for d(x⃗, c⃗) ≤ t.

• Using maximum likelihood decoding, which is the same as nearest neighbour decoding, i.e. received any word, decode as the nearest codeword. At most how many codewords can there be, if any two codewords have distance at least 3? (generally, if the minimum distance is d, where d is odd)?

Let n = 7, d = 3. How many codewords can there be at most?

• Use a computer. Let n be an integer. Generate M random binary codewords of length n.

Ex. 3 A source emits words with probabilities

p_{1} = \frac{1}{3}, p_{2} = \frac{1}{3}, p_{3} = \frac{1}{4}, p_{4} = \frac{1}{12}.

Study the possible code word lengths in the Huffman code(s) and compare with the word lengths of Shannon encoding.

Ex. 4 A binary symmetric channel with symbol error probability p = 0.05 can transmit 800 binary digits per second. How many bits can it transmit accurately per second? Hint: use the noisy coding theorem.

Ex. 5 A binary symmetric channel which can can physically transmit 800 binary digits per second, can transmit 500 digits per second with arbitrarily small error. What does this tell about the error probability of the channel? Hint: use the noisy coding theorem.

Ex. 6 State in your own words the noisy coding theorem and write a short essay about its meaning (200-300 words).

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