Exercises for Cyclic, Hamming, BCH, and Golay codes

For the purpose of this worksheet, a code is a k-dimensional linear subspace C of F_p^N, for some prime p, some integer N (the length ), and some k (where k/N is the information rate ), with a fixed basis. You must have the codes.mpl file to do these exercises. It is available from

http://www.usna.edu/Users/math/wdj/codes.htm If you have MAPLE 7 then download codes_v7.mpl instead.

(find the codes.mpl link and download it).

codes_exercises.mws, wdj, 8-2001

>

You may need to change the path in the read command below for you computer.

read(`c:/maplefiles/codes/codes.mpl`);

Warning, the protected names norm and trace have been redefined and unprotected

Hamming codes

A generator matrix of the p-ary Hamming code of length (p^n-1)/(p-1) is given by the codes command hamming_generator(n,p) . The rows of the generator matrix are the basis vectors of C. For example, the generator matrix for a 3-ary Hamming code of length 4 (n=2) is given by:

> hamming_generator(2,3);

Exercise 1 : (a) Find a generator matrix of the binary Hamming code of length 15.

(b) Find a generator matrix of the 3-ary Hamming code of length 13.

The generator matrix is used by the codes package to compute the list of all codewords using the code_list command. For example, to compute the list of all codewords of the Hamming [7,4,3] code, then sort them according to weight, type:

> G:=hamming_generator(3,2):
C:=code_list(G,2):
C:=sort(C,weight_order);

In particular, the minimum weight of a non-zero codeword is 3. Since C is a linear code, this means that the minimum distance of this code is 3.

Parity check matrices H of a code C are useful for verifying membership in the code: a received vector v is a codeword (ie, it most likely contains no errors) if Hv=0.
Parity check vectors (in standard form) of a binary Hamming code is given by the codes command hamming_check_binary(n) . For example, for the code of length 2^2-1=3, take n=2:

> G:=hamming_generator(2,2):
C:=code_list(G,2);
H:=hamming_check_binary(2);

Exercise 2 : For all 16 codewords c of the Hamming [7,4,3] code C, verify Hc=0. (Hint: You may do this my hand or by using the matrix_times_vector_modp command.)

Parity check matrices for other codes are also possible (see below). The codes command hamming_check(n,p) gives the check matrix for the p-ary Hamming code of length (p^n-1)/(p-1). For example, the parity check matrices (in standard form) of the 5-ary Hamming code of length (5^3-1)/(5-1)=31 is given by:

> H:=hamming_check(3,5);

Exercise 3 : (a) Find a parity check matrix of the binary Hamming code of length 2⁴-1=15. Verify Hc=0 for three or four codewords c. (Don't use code_list to get the codewords, rather use three or four row vectors of the generator matrix for C.)
(b) Find a parity check matrix of the 3-ary Hamming code of length (3^3-1)/(3-1)=13. Verify Hc=0 for three or four codewords c. (Don't use code_list to get the codewords, rather use three or four row vectors of the generator matrix for C.)

Decoding binary Hamming codes can be done using the command decode_hamming_binary . First, we check if the received vector v=(1,1,1,0,0,0,0) is correct by checking Hv=0. Then we decode the received vector.

> v:=[1,1,1,0,0,0,0];
H:=hamming_check_binary(3):
matrix_times_vector_modp(H,v,2);
This received word v has an error since H*v is non-zero.

> decode_hamming_binary(v);
This command only works for binary Hamming codes.

Exercise 4 : (a) Let v=(1,1,1,1,0,0,0). Check if it is a codeword in the [7,4,3] code and if not decode it.

(b) Let v=(1,1,1,1,0,0,0,0,0,0,0,0,0,0,0). Check if it is a codeword in the length 15 Hamming code and if not decode it.

Binary Reed-Muller codes

The command RM_generator(n) gives the generator matrix of the binary 1st order Reed-Muller code of length 2^n. For example, the generator matrix of the binary 1st order Reed-Muller code of length 8 is given by:

> G:=RM_generator(3);

The list of its codewords is given by the code_list command. From this, we see that the minimum distance is 4.

> C:=code_list(G,2):
C:=sort(C,weight_order);

Exercise 5 : Find the generator matrix for the RM code of length 16 and its minimum distance.

>

Cyclic codes

One can test if g(x) is a generating polynomial of a cyclic code of length n over F_p using iscyclic(g(x),n,p)

> iscyclic(x+1,7,2);
iscyclic(x^2+1,7,2);
iscyclic(x^3+x+1,7,2);

Enter the generator polynomial of cyclic code and generator_matrix will return the corresponding generator matrix.

> G:=generator_matrix(x^3+x^2+1,7,2);

Enter the generator polynomial of cyclic code and check_matrix will return the corresponding parity check matrix.

> H:=check_matrix(x^3+x^2+1,7,2);

> v:=[1,1,1,1,0,0,0];
matrix_times_vector_modp(H,v,2);
The word v is not in the cyclic code generated by x^3+x^2+1 since H*v1 is non-zero

Exercise 6 : (a) Check if x^2+1 is a generating polynomial of a cyclic code of length 4 over F_2. If so, find a basis for this code, as a vector space over F_2, and construct a parity check matrix.

(b) Use Gaussian elimination to put the above generator matrix (G:=generator_matrix(x^3+x^2+1,7,2)) in standard form. Try to find similarities between this matrix and the matrix obtained in the section on Hamming codes (G:=hamming_generator(3,2)).

Golay codes

The generator matrix for the ternary (12,6) code:

> G:=golay12();

The parity check matrix for the ternary (12,6) code:

> H:=golay_check12();

> v:=[1,2,2,2,2,1,0,1,0,0,1,2];
matrix_times_vector_modp(H,v,3);
v1 is not a codeword in the (12,6)-Golay code. It has only 1 error (in the first position).

The generator matrix for the perfect ternary (11,6) code:

> G:=golay11();

The parity check matrix for the ternary (11,6) code:

> H:=golay_check11();

The generator matrix for the perfect binary (23,12) code:

> G:=golay23();

The parity check matrix for the perfect binary (23,12) code:

> H:=golay_check23();

> v:=[0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1];
matrix_times_vector_modp(H,v,2);
v is not a codeword in the (23,12)-Golay code. It has only 1 error (in the first position).

> G:=golay24();
The generator matrix for the (24,12)-Golay code

> H:=golay_check24();
The parity check matrix for the (24,12)-Golay code.

Exercise 7 : (a) Check if v:=[0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0] is a codeword of the (24,12)-Golay code.

(b) Check if v:=[2,2,2,2,2,1,0,1,0,0,1] is a codeword of the (11,6)-Golay code.

BCH codes

We shall construct by hand some BCH codes. A BCH code is a cyclic code which included the binary Hamming codes as a special case.

To construct a (binary, narrow) BCH code, you must have a primitive element alpha of degree k over F=GF(2). You must know the minimal polynomials of a sequence of powers of alpha: alpha, alpha^2, ..., alpha^(2t). Take the lcm of these. This new polynomial is the generating polynomial of the BCH code. It has minimum distance 2t+1.

> with(PolynomialTools);
#with(numtheory):

>

> f:=x^4+x+1;
alias(beta=RootOf(f)):
Factor(f) mod 2;
Factor(f,beta) mod 2;
Roots(f,beta) mod 2;
for i from 1 to 19 do
pp[i]:=unapply(MinimalPolynomial(beta^i,4),_X):
print(beta^i,pp[i](x));
od:

> GenPoly:=x->Lcm(seq(pp[j](x),j=1..4)) mod 2:
GenPoly(x);
Quo(x^(15)-1,GenPoly(x),x) mod 2;
iscyclic(GenPoly(x),15,2);

In other words, GenPoly(x) is indeed the generating polynomial for some cyclic code over F_2. We use the generator_matrix(g(x),n,p) command to construct the generator matrix of the corresponding BCH code. the check_matrix(g(x),n,p) command to constructs the check matrix. The min_distance command, which will be explained in the next section, is used to verify that this code really is 2-error-correcting as claimed.

> G:=generator_matrix(GenPoly(x),15,2);
H:=check_matrix(GenPoly(x),15,2);
min_distance(G,2);
This code is 2-error correcting.

Exercise 8 : Construct a 3 error-correcting code. (Hint: Modify the GenPoly line above)

>

Functions on codes

The minimum distance of a p-ary code with generator matrix G is given by the command min_distance(G,p) . For example, the minimum distance of the binary Hamming code of length 7 is obtained by typing:

> G:=hamming_generator(3,2):
min_distance(G,2);

The minimum distance of the BCH code constructed above was shown to be 5 in the previous section.

Exercise 9 : Find the minimum distance of the 3-ary Hamming code of length (3^2-1)/(3-1)=4.

Related both to the minimum distance and to the problem of ordering the codewords according to weight is the weight enumerator function (in vector form or in polynomial form). The codes commands weight_enumerator_vector(G,p) and weight_enumerator_polynomial compute these, where G is the generator matrix for a code over F_p. For example, the weight enumerator vector for the binary (p=2) Hamming code of length 7 is obtained by typing:

> G:=hamming_generator(3,2):
weight_enumerator_vector(G,2);
There are 7 code words of weight 3, 7 code words of weight 4, and no code words of weights 1,2, 5 or 6. In particular, the minimum distance is 3.

> weight_enumeration_polynomial(G,2,x,y);
This is the weight enumerator polynomial of the binary (p=2) Hamming (7,4,3)-code. It's coefficients form the weight enumerator vector above.

Exercise 10 : Find the weight enumerator polynomial (or vector) of the 3-ary Golay code of length 11.

>

The nearest neighbor algorithm is implemented in the decode(v,G,p,d) procedure, where G is a generator matrix, p is a prime, d is the distance, and v is the received vector. It is very slow for large codes. For binary Hamming codes, a faster algorithm has been implemented (see the above section on Hamming codes).

> G:=golay12();
v:=[1, 2, 2, 2, 2, 1, 0, 1, 0, 0, 1, 2];
decode(v,G,3,5);

Exercise 11 : If v:=[2,2,2,2,2,1,0,1,0,0,1] is not a codeword of the (11,6)-Golay code, decode it.