Q 5. Consider the binary code C = {a, b, c, d} where

a = 0 0 0 0 0 0 0 0     b = 1 0 1 1 0 1 0 1

c = 0 1 1 0 1 1 1 1     d = 1 1 0 1 1 0 1 

(a) Is C linear? Why or why not?

(b) Calculate the distance between each pair of codewords in C.

(c) How may errors can C always detect? 

(d) How many errors can C always correct? Is this optimal according to the Disjoint Spheres Lemma?

(e) Write down your student number. Now turn it into a binary word w of length 8 by replacing the even digits with 0 and the odd digits with 1. Can w be decoded with C using the nearest neighbour principle? What is the result?

(f) Now consider the code D = {a, b, d, d + b}. Show that D is linear.

(g) If 0, v and w are three distinct codewords, will {0, v, w, v + w} always be a linear code? Explain why or why not.

(h) Now we will construct the check matrix H for D. We know the length of D is 8 and that |D| = 4 = 22 , so the dimension of D is 2. We can assume that the matrix is in ‘reduced row echelon form’ and looks like this:

Since H is the check matrix for D, this means H · w0 = 0 0 for each w ∈ D (recall that w0 just means w considered as a column). This information will allow us to determine the unknown binary entries x1, . . . , x6, y1, . . . , y6. For example, H · b 0 = 0 0 is a system of six equations involving the unknowns. The first equation (corresponding to the first row of H) is 1 + y1 = 0 which already tells us that y1 = 1. Your task is to determine the other 11 unknown entries of H.