Problem sheet 4 2004, Feb. 5

MT361 Error correcting codes

{Ex. 1 \atop a)}Sarah and Mike play the following game: Sarah thinks of a number n ∈ {1, 2, …, 1 0000 000}. Mike is allowed to ask questions and Sarah will answer them (truthfully) with yes or no, only. What is the minimum number of questions Mike has to ask that guarantees that he correctly finds the number? Describe the procedure to ask the questions.

b) Now Sarah is allowed to lie, but at most once. What is the minimum number of questions, and what is the algorithm now?

Ex. 2 Let C be the binary linear code with generator matrix [ \begin{matrix}1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \end{matrix} ].

Find a generator matrix for C in standard form. Is this the same code as that in example 5.7 of the lecture? (Or is it equivalent to that code?)

Ex. 3 Construct standard arrays for codes having each of the following generator matrices:

G_{1} = [ \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ] G_{2} = [ \begin{matrix}1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix} ] G_{3} = [ \begin{matrix}1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \end{matrix} ] .

Using the third array decode the received vectors 11111 and 01011. Give two examples of

a) two errors in a code and being corrected and

b) two errors in a codeword and not being corrected.

Ex. 4 If the error probability of a binary symmetric code is p, calculate the probabilities for each of the three codes from the previous exercise that any received vector will be decoded as the codeword which was sent. Evaluate these probabilities for p = 0.01. Now suppose each code is used purely for error detection. Calculate the respective probabilities that the received vector is a codeword different from that sent, and evaluate this for p = 0.01. Comment on the merits of these three codes.

Ex. 5 We have assumed that, for a binary symmetric channel, the symbol error probability p is less than 1/2. Can an error correcting code be used to reduce the number of messages received in error if

a) p = 1/2

b) p > 1/2 ?

Ex. 6 Suppose C is a binary [n, k] code with minimum distance 2t + 1 (or 2t + 2). Given that p is very small, show that an approximate value of P_{err}(C) is

(\binom{n}{t + 1} − α_{t+1}) p^{t+1},

where α_{t+1} is the number of coset leaders of C of weight t + 1.

Ex. 7 Suppose the perfect binary [7, 4] code (see problem sheet 2 and examples in the lectures!) is used for error detection and suppose that p = 0.01. Evaluate the probability that a retransmission needs to be requested and evaluate the probability that an error is undetected in the first step, and evaluate that overall probability an error is undetected, even after retransmission.

Hand in solutions at the beginning of the lecture on Thursday of the next week.