# 24.12 Exercises

1. Two codewords were sent using the Hamming  code and were received as 0100111 and 0101010. Each one contains at most one error. Correct the errors. Also, determine the 4-bit messages that were multiplied by the matrix  to obtain the codewords.

2. An ISBN number is incorrectly written as 0-13-116093-8. Show that this is not a correct ISBN number. Find two different valid ISBN numbers such that an error in one digit would give this number. This shows that ISBN cannot correct errors.

3. The following is a parity check matrix for a binary  code :



1. Find  and .

2. Find the generator matrix for .

3. List the codewords in .

4. What is the code rate for ?

4. Let  be a binary repetition code.

1. Find a parity check matrix for .

2. List the cosets and coset leaders for .

3. Find the syndrome for each coset.

4. Suppose you receive the message . Use the syndrome decoding method to decode it.

5. Let  be the binary code .

1. Show that  is not linear.

2. What is ? (Since  is not linear, this cannot be found by calculating the minimum weight.)

3. Show that  satisfies the Singleton bound with equality.

6. Show that the weight function (on ) satisfies the triangle inequality: .

7. Show that , where  is the function defined in Section 24.3.

8. Let  be the repetition code of length . Show that  is the parity check code of length . (This is true for arbitrary .)

9. Let  be a linear code and let  and  be cosets of . Show that  if and only if . (Hint: To show , it suffices to show that  for every , and that  for every . To show the opposite implication, use the fact that .)

10. Show that if  is a self-dual  code, then  must be even.

11. Show that  is the generating polynomial for the  repetition code. (This is true for arbitrary .)

12. Let  be a polynomial with coefficients in .

1. Show that  is a factor of  in .

2. The polynomial  is the generating polynomial for a cyclic code  code . Find the generating matrix for .

3. Find a parity check matrix  for .

4. Show that , where



5. Show that the rows of  generate .

6. Show that a permutation of the columns of  gives the generating matrix for the Hamming  code, and therefore these two codes are equivalent.

13. Let  be the cyclic binary code of length  with generating polynomial . Which of the following polynomials correspond to elements of ?



14. Let  be the generating polynomial for a cyclic code  of length , and let . Write . Show that the dual code  is cyclic with generating polynomial . (The factor  is included to make the highest nonzero coefficient be 1.)

1. Let  be a binary repetition code of odd length  (that is,  contains two vectors, one with all 0s and one with all 1s). Show that  is perfect. (Hint: Show that every vector lies in exactly one of the two spheres of radius .)

2. Use (a) to show that if  is odd then . (This can also be proved by applying the binomial theorem to , and then observing that we’re using half of the terms.)

15. Let  and let  denote the number of points in a Hamming sphere of radius . The proof of the Gilbert-Varshamov bound constructs an  code with . However, this code is probably not linear. This exercise will construct a linear  code, where  is the smallest integer satisfying .

1. Show that there exists an  code .

2. Suppose  and that we have constructed an  code  in  (where  is the finite field with  elements). Show that there is a vector  with  for all .

3. Let  be the subspace spanned by  and . Show that  has dimension  and that every element of  can be written in the form  with  and .

4. Let , with , be an element of , as in (c). Show that .

5. Show that  is an  code. Continuing by induction, we obtain the desired code .

6. Here is a technical point. We have actually constructed an  code with . Show that by possibly modifying  in step (b), we may arrange that  for some , so we obtain an  code.

16. Show that the Golay code  is perfect.

17. Let  be a root of the polynomial .

1. Using the fact that  divides , show that .

2. Show that .

3. Suppose that  with . Then , so there exist integers  with . Use this to show that , which is a contradiction. This shows that  is a primitive seventh root of unity.

18. Let  be the binary code of length 7 generated by the polynomial . As in Section 24.8, , where  is a root of . Suppose the message  is received. It has one error. Use the procedure from Section 24.8 to correct the error.

19. Let  be a cyclic code of length  with generating polynomial . Assume  and  (as in the theorem on p. 472).

1. Show that .

2. Write . Let  be a primitive th root of unity. Show that at least one of  is a root of . (You may use the fact that  cannot have more than  roots.)

3. Show that .