1

Problem sheet 6, 2005, Nov. 9  MT441 Channels

Ex. 1 Give an example to show that equality can hold in Fano’s inequality.

Ex. 2 Two binary vectors are chosen at random. What is the probability that their Hamming distance is at least k?

Ex. 3 (For programming) Let V_{n} denote the set of binary words of length n. Choose k codewords w_{1}, …, w_{k} at random. Let D_{k} denote their minimum distance, i.e. the minimum distance between any pairs of two distinct codewords. Estimate the expected value by a computer simulation. (Example: for k = 3, 4, and 1 ≤ n ≤ 20 do a few thousands random tests.)

Ex. 4 Given a channel with matrix

(\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{6} & \frac{1}{6} \\ \frac{1}{6} & \frac{1}{6} & \frac{1}{3} & \frac{1}{3} \end{matrix})

Show that the capacity is given by C = log 2^{\frac{5}{3}} − log 3.

Ex. 5 A memoryless source of entropy 15 bits per sourceword is connected to a binary symmetric channel of symbol error probability p = 0.1, which can pass 1000 binary digits per second through the receiver. At which rate can the source words be emitted if they are to be communicated accurately through the channel?

Ex. 6 A source S is such that, for each n, the probability distribution of X_{n} depends on X_{n−1} in the following way:

P (X_{n} | X_{n−1}, X_{n−2}, , …, X_{1}) = P (X_{n} | X_{n−1})
P (X_{n} = 0 | X_{n−1} = 0) = P (X_{n} = 1 | X_{n−1} = 1) = p
P (X_{n} = 1 | X_{n−1} = 0) = P (X_{n} = 0 | X_{n−1} = 1) = q,

where 0 ≤ p ≤ 1 and q = 1 − p. Show that H(S) exists and find it.

Ex. 7 A source behaves as follows: it emits, each with probability \frac{1}{2}, either an infinite string of zeros or a purely random string of zeros and ones. Does S have an entropy?

Ex. 8 Consider a source S whose output (X_{n} : n = 1, 2, …) is as follows: X_{2k} = 1 for all k and (X_{1}, X_{3}, X_{5}, …) is a purely random source. Show that H(S) exists, but that lim_{n→∞} H(X_{n} | X_{1}, …, X_{n}) does not.

Ex. 9 Consider the sources of the three problems above. Are they stationary or not?

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