Problem sheet 5 2004, Feb. 12

MT361 Error correcting codes

Note: Question 1b from the last sheet is a real challenge. Some students are seriously working on it. If you work on it, better work with 1 million (rather than 10 million as on the original sheet). For a) (in the case of 1 million) the answer is 20 bits = 20 questions. Try b) again. Try to seee the connection to error correcting. Try to improve your results. Do not waste any questions, optimize your questions. Try to give good lower and upper bounds on the number of questions that are as close as possible.

Ex. 1 Prove lemma 7.4: Suppose C is an [n, k]-code having generator matrix G. Then a vector v⃗ ∈ V (n, q) belongs to C^{⊥} ⇔ v⃗G^{⊤} = 0, where G^{⊤} denotes the transpose of G.

Ex. 2 Evaluate the dual codes C_{1}^{⊥} and C_{2}^{⊥} for C_{1} = {000, 111} and C_{2} = {00000, 11111}.

Ex. 3 Prove that if E_{n} is the binary even weight code of length n, then E_{n}^{⊥} is the repetition code of lengt n.

Ex. 4 Let C be the ternary linear code with generator matrix

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

a) Find a generator matrix for C in standard form

b) Find a parity check matrix for C in standard form.

This problem sheet is perhaps easier again. Any problem from last sheet you didn’t do so far, please do now!

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