Problem sheet 1 2005, Jan. 13th

MT361 Error correcting codes

Ex. 1 Define the minimum distance d(C) of a code. What is d(C) for the codes in examples 1.8, 1.10, 1.11 ?

Ex. 2 Define a ternary symmetric channel with error probability p. Also draw an analogue to the picture we had for the binary case, marking also the probabilities of each symbol change.

Ex. 3 Suppose a binary repetition code of length 5 is used for a binary symmetric channel with (symbol error) crossover probability p. Show that the word error probability is 10p^{3} − 15p^{4} + 6p^{5}. Evaluate this probability if p = 0.1.

Ex. 4 We want to consider the best possible 3-ary (n, M, d) code, where q = 3, n = 3 is the word length, M is the number of codewords, and d = 2 is the minimum distance of the code. What is the largest M one can use?

a) Show that a 3-ary (3, M, 2)-code must have M ≤ 9.

b) Show that a 3-ary (3, 9, 2)-code exists. (Hint: find three codewords starting with 0, and three codewords starting with 1, and three codewords starting with 2).

Ex. 5 Each properly published book gets a unique ISBN number (international standard book number). This is a 10-digit codeword. The first digit stands for the country/language, the next few digits for the publisher. Then some digits for a number assigned by the publisher, the very last digit is a checksum. (A large publisher gets a short publisher identification and can thus use more digits for its own books, a small publisher gets a longer publisher identification. This alone leads to interesting questions but we leave these aside.) For example, the recommended text book by Ray Hill has the number ISBN 0-19-853804-9 ISBN 0-19-853803-0 (for the paperback edition). Here the first 0 stands for english, the 19 for Oxford University Press.

Let x_{1}x_{2} ⋯ x_{10} be the ISBN number (codeword). The check bit x_{10} is chosen such that the whole codeword satisfies ∑_{i=1}^{10} ix_{i} ≡ 0 mod 11.

a) Show that x_{10} = ∑_{i=1}^{9} ix_{i} ≡ 0 mod 11.

Note that the last symbol can be any of 11 eleven values. So, one uses in addition to 0, 1, …, 9 the symbol X = 10. b) Show that this code can be used in the following way: To detect any

single error and to detect a double error created by the transposition of two digits (example 152784 ↔ 158724). Would this also work, if you use a similar code mod 15 instead of mod 11?

c) Can this method be used to correct one single error?

d) Discuss the advantages of this method for the practical use (to order books in a bookshop etc.).

e) What is the minimum distance of any two ISBN numbers?

f) Consider a different code C_{2}, where one uses as before 10 digits but does not use a weighted sum, but ∑_{i=1}^{10} x_{i} ≡ 0 mod 11. What would be the disadvantage, compared with the ISBN code?

Hand in solutions at the beginning of the lecture on Thursday 20th January. I’ve put some books in the restricted loan section of the library. Recommended reading is R. Hill: A First course in coding theory. (001.539 Hil) An electronic version of the problem sheets will be available (probably with some delay): http://www.ma.rhul.ac.uk/∼elsholtz/WWW/lectures/0405mt361/lecture.html