Problem sheet 8 2004, March. 11

MT361 Error correcting codes

Collect any questions you have and forward them to me, (sheet of paper or email to christian.elsholtz@rhul.ac.uk) In the last lessons I will come back to the most relevant questions. A good collection of problems including solutions is at http://www.maths.usyd.edu.au:8000/u/adriann/MATH3007/cd.html

When looking at these problems, or at previous exam papers: if we did not have any related exercise it is not so likely that the problem is relevant. Start your revision with the problems of this course.

Ex. 1 State the Singleton bound and prove it!

{Ex. 2 \atop i)}Prove A_{2}(n, d) ≤ 2A_{2}(n − 1, d). (Consider all codewords with a fixed entry at some position).

ii) Generalize to the q-ary case.

iii) Using i) prove parts iii) and iv) from the proof of Plotkin’s bound, ie. prove for even d: A(2d + 1, d) ≤ 4d and for odd d; A(2d, d) ≤ 4d + 4.

Ex. 3 Construct Hadamard matrices for n = 2^{k}. Also show: if Hadamard matrices of order n_{1} and n_{2} exist, then a Hadamard matrix of order n_{1}n_{2} exists.

Find a Hadamard matrix of size 12. (in case that this is too difficult, the internet knows the answer!)

Use google (or similar) to find out more about the known or conjectured results about Hadamard matrices.

{Ex. 4 \atop i)}Show that a 3-ary (3, M, 2) code has M ≤ 9.

ii) Show that a 3-ary (3, 9, 2)-code exists.

iii) Generalize to q ary (3, M, 2)-codes.

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