1 Problem sheet 9 2006

MT3610/5461 Error correcting codes

Collect any questions you have and forward them to me, (sheet of paper or email). In the last lessons I will come back to the most relevant questions. Start your revision with the problems of this course.

Ex. 1 State the Gilbert-Varshamov bound and prove it!

Ex. 2 State the Singleton bound and prove it!

Ex. 3 (MT5461) Read in Hill’s text book the section Hamming codes as cyclic codes, pages 159-161.

(the following problems are a bit too early:)

Ex. 4 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. 5 Construct 4 MOLS of order q = 5. Show that there cannot be 5 MOLS of order 5.

{Ex. 6 \atop i)}Construct pairs of mutually orthogonal Latin squares for n = 6. Well, they don’t exist, but try a bit to get a feeling that it is not an easy problem to prove that they cannot exist.

ii) Try the same for n = 10. Well, they exist, and were found after a long time of computer search. It is unlikely that you find any, but convince yourself that an exhaustive search would just take a very long time.

iii) Try to find two MOLS of order 10, either by using the internet or by using an appropriate book. iv) Try to find three MOLS of order 10. (This is an open research problem.

If you solve it you will become very famous!) Hand in the solutions to iii). Actually, finding information, when you only know some key words is one of the most important things in your later life. At University you have very privileged access like broadband, access to databases or books.