Problem sheet 1 2006

MT3610/5461 Error correcting codes

Ex. 1 Prove that the distance d(x⃗, y⃗) between words x⃗, y⃗ ∈ (F_{q})^{n} satisfies the triangle inequality.

Ex. 2 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. 3 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. 4 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. 5 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).

Hand in solutions in one week. 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/0506mt361/lecture.html