Problem sheet 6 2004, Feb. 19

MT361 Error correcting codes

Ex. 1 (Not to be handed in) Work through pages 74-78 of Raymond Hill’s book. In particular watch out for the advantages of incomplete decoding.

Ex. 2 Show that the decimal code

{(x_{1}, x_{2}, …, x_{10}) ∈ Z_{10}^{10}| ∑_{i=1}^{10} x_{i} ≡ 0(mod10), ∑_{i=1}^{10} ix_{i} ≡ 0(mod10)}

is not a single-error-correcting code. (here Z_{10} denotes the set of integers mod 10.

Ex. 3 (see problem sheet 5) 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.

c) Use syndrome decoding to decode the received vectors 2121, 1201 and 2222.

Ex. 4 Suppose a certain binary channel accepts word of length 7 and that the only kind of error vector ever observed is one of the eight vectors

0000000, 0000001, 0000011, 0000111, 0001111, 0011111, 0111111, 111111.

Design a binary linear [7, k]-code which will correct all such errors with as large a rate as possible.

Ex. 5 To determine the minimum distance of a general code one needs \binom{M}{2} comparisons. Show that for a linear code the minimum distance is given by the minimum weight of any non-zero codeword. (Compare ex 7. on sheet 2). Further show that C has distance d if and only if any d − 1 rows of a parity check matrix H are linearly independent but there exist d rows which are dependent.

Ex. 6 Let C be the code generated by

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

A new code C_{2} is formed by adding a parity check.

a) Write down the generator matrix for C_{2} in standard form.

b) Determine the parameters [n, k, d] and M.

c) Write down its parity check matrix for C_{2}.

d) Show that C_{2} can be used to simultaneously correct one error and detect two errors.

e) Make a lookup table to enable syndrome decoding to use it in the way suggested in d.

f) Decode the received vectors 0110110, 1111010 and 1110111. Do not write down the standard array or the codewords.

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