24.12 Exercises – Introduction to Cryptography with Coding Theory, 3rd Edition

24.12 Exercises

  1. Two codewords were sent using the Hamming [7, 4] 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 G 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 [n, k] code C:

    111001001001001.

    1. Find n and k.

    2. Find the generator matrix for C.

    3. List the codewords in C.

    4. What is the code rate for C?

  4. Let C={(0, 0, 0), (1, 1, 1)} be a binary repetition code.

    1. Find a parity check matrix for C.

    2. List the cosets and coset leaders for C.

    3. Find the syndrome for each coset.

    4. Suppose you receive the message (1, 1, 0). Use the syndrome decoding method to decode it.

  5. Let C be the binary code {(0, 0, 1), (1, 1, 1), (1, 0, 0), (0, 1, 0)}.

    1. Show that C is not linear.

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

    3. Show that C satisfies the Singleton bound with equality.

  6. Show that the weight function (on Fn) satisfies the triangle inequality: wt(u+v)wt(u)+wt(v).

  7. Show that Aq(n, n)=q, where Aq(n, d) is the function defined in Section 24.3.

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

  9. Let C be a linear code and let u+C and v+C be cosets of C. Show that u+C=v+C if and only if uvC. (Hint: To show u+C=v+C, it suffices to show that u+cv+C for every cC, and that v+cu+C for every cC. To show the opposite implication, use the fact that uu+C.)

  10. Show that if C is a self-dual [n, k, d] code, then n must be even.

  11. Show that g(X)=1+X+X2++Xn1 is the generating polynomial for the [n, 1] repetition code. (This is true for arbitrary F.)

  12. Let g(X)=1+X+X3 be a polynomial with coefficients in Z2.

    1. Show that g(X) is a factor of X71 in Z2[X].

    2. The polynomial g(X) is the generating polynomial for a cyclic code [7, 4] code C. Find the generating matrix for C.

    3. Find a parity check matrix H for C.

    4. Show that GHT=0, where

      G=1101000011010000110100111001.

    5. Show that the rows of G generate C.

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

  13. Let C be the cyclic binary code of length 4 with generating polynomial g(X)=X2+1. Which of the following polynomials correspond to elements of C?

    f1(X)=1+X+X3, f2(X)=1+X+X2+X3, f3(X)=X2+X3

  14. Let g(X) be the generating polynomial for a cyclic code C of length n, and let g(X)h(X)=Xn1. Write h(X)=b0+b1X++X. Show that the dual code C is cyclic with generating polynomial h˜r(X)=(1/b0)(1+b1X++b1X1+b0X). (The factor 1/b0 is included to make the highest nonzero coefficient be 1.)

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

    2. Use (a) to show that if n is odd then j=0(n1)/2nj=2n1. (This can also be proved by applying the binomial theorem to (1+1)n, and then observing that we’re using half of the terms.)

  15. Let 2dn and let Vq(n, d1) denote the number of points in a Hamming sphere of radius d1. The proof of the Gilbert-Varshamov bound constructs an (n, M, d) code with Mqn/Vq(n, d1). However, this code is probably not linear. This exercise will construct a linear [n, k, d] code, where k is the smallest integer satisfying qkqn1/Vq(n, d1).

    1. Show that there exists an [n, 1, d] code C1.

    2. Suppose qj1<qn/Vq(n, d1) and that we have constructed an [n, j1, d] code Cj1 in Fn (where F is the finite field with q elements). Show that there is a vector v with d(v, c)d for all cCj1.

    3. Let Cj be the subspace spanned by v and Cj1. Show that Cj has dimension j and that every element of Cj can be written in the form av+c with aF and cCj1.

    4. Let av+c, with a0, be an element of Cj, as in (c). Show that wt(av+c)=wt(v+a1c)=d(v, a1c)d.

    5. Show that Cj is an [n, j, d] code. Continuing by induction, we obtain the desired code Ck.

    6. Here is a technical point. We have actually constructed an [n, k, e] code with ed. Show that by possibly modifying v in step (b), we may arrange that d(v, c)=d for some cCj1, so we obtain an [n, k, d] code.

  16. Show that the Golay code G23 is perfect.

  17. Let α be a root of the polynomial X3+X+1Z2[X].

    1. Using the fact that X3+X+1 divides X71, show that α7=1.

    2. Show that α1.

    3. Suppose that αj=1 with 1j<7. Then gcd(j, 7)=1, so there exist integers a, b with ja+7b=1. Use this to show that α1=1, which is a contradiction. This shows that α is a primitive seventh root of unity.

  18. Let C be the binary code of length 7 generated by the polynomial g(X)=1+X2+X3+X4. As in Section 24.8, g(1)=g(α)=0, where α is a root of X3+X+1. Suppose the message (1, 0, 1, 1, 0, 1, 1) is received. It has one error. Use the procedure from Section 24.8 to correct the error.

  19. Let CFn be a cyclic code of length n with generating polynomial g(X). Assume 0CFn and p|n (as in the theorem on p. 472).

    1. Show that deg(g)1.

    2. Write Xn1=g(X)h(X). Let α be a primitive nth root of unity. Show that at least one of 1, α, α2, , αn1 is a root of g(X). (You may use the fact that h(X) cannot have more than deg(h) roots.)

    3. Show that d(C)2.