Sample problems for Coding
Technology
1. Give the generator matrix and the parity check matrix of an RS code capable of
correcting every single error over G(5) (the primitive element is 2)
Solution:
1 1 1 1 1 2 4 3
C(4,2) G ; H
1 2 4 3 1 4 1 4
2. Determine the parameters of an RS code for correcting every triple error (t=3)
in the case q-ary symbols
Solution C(10,4)
3. Indicate the correct statement with a tick (if each correct statement is
indicated 20 p otherwise 0p)
a) RS codes can correct any number of errors
b) The parameter n of an RS code can be chosen arbitrarily
c) The degree of the generator polynom of a C(n,k) linear cyclic code is k.
d) In the case of a cyclic code all codevectors are cyclic shifts of each
other.
e) RS codes are MDS codes.
4. Given a BSC with probability p=0.2 and two error vector e(1) 101010 and
e(2) 001010 belonging to the same group
a) which one might qualify as a group leader
b) what are the associated probabilities of the two vectors
Solution:
e(2) 001010 might qualify as a group leader as it has smaller weights
One has to compute the formula 0.2w(e ) 0.86 w(e ) for both vectorss
1
3) 5. There is a Reed Solomon code over GF(7) correcting every double error.
a) Define the type of the code (n and k parameters) (5p)
b) Give the generator and the parity check matrix of the code using the primitive element 5. (15p)
Solution:
n k
a) n q 1 7 1 6; t 2 k 2
2
1 1 1 1 1 1 1 5 4 6 2 3
b) G 1 5 4 6 2 3
H 1 4 2 1 4 2
1 4 2 1 4 2 1 6 1 6 1 6
1 0 1 1 1
7. Given a binary linear code with the following generator matrix G . The BSC
0 1 1 1 0
will add e 0 1 1 0 0 error vector to the transmitted codeword. What is the detected error
vector at the receiver side ?
Solution:
The codewords c(1) 0,0,0,0,0 ; c(2) 0,1,1,1,0 ; c(3) 1,0,1,1,1 ; c(4) 1,1,0,0,1
Es e, e c1 , e c 2 , e c3 01100 , 00010 , 11011 , 10101
Thus e 00010 is the detected vector havin the smallest weight.
8. Given a binary linear Hamming code with its parity check matrix
1 1 0 1 0 1 0 1 1 1 0 0 0
1 0 1 1 1 0 1 1 1 0 1 0 0
H T
h12 T
h13
1 1 0 0 1 0 1 1 0 1 0 1 0
1 1 1 0 1 1 0 0 1 0 0 0 1
a) what are the parameters of the code (4T p) T
b) what are the missing column veoctorsh12 and h13 in H which guarantees the correction of every
single error ( 4 p)
c) give the generator matrix (4p)
Solution:
2.
a) n=15, k=11
b) The condition for all single error to be corrected is to have difffrent and nonzero
column vector in H, thus
2
1 1 0 1 0 1 0 1 1 1 0 1 0 0 0
1 0 1 1 1 0 1 1 1 0 0 0 1 0 0
H
1 1 0 0 1 0 1 1 0 1 1 0 0 1 0
1 1 1 0 1 1 0 0 1 0 1 0 0 0 1
c) The generator matrix is
1 . . . . 0 1 1 1 1
0 . 1 0 1 1
0 . 0 1 0 1
0 1 1 0 0
0 0 1 1 1
G 0 1 0 0 1
0 0 1 1 0
0 1 1 1 0
0 . 1 1 0 1
0 . 1 0 1 0
0 . . . . 1 0 0 1 1