1. Using MAPLE, we construct the parity-check matrix and generator matrix of
   • the cyclic code of length n over F_p,
   • the binary Hamming code over F₂ (which is perfect and 1-error-correcting),
   • the ternary (11,6)-Golay (which is perfect, minimum distance 5, and 2-error-correcting), and
   • the binary (23,12)-Golay codes (which is perfect, distance 7, and 3-error-correcting).
   (The parity check matrix of the binary Hamming code is the generator matrix of the 1st order Reed-Muller code, so these codes are included as a consequence. Also, the (12,6)-Golay code and the (24,12)-Golay code are also included.)
2. We give a program which returns all the codewords in a code, provided the prime p and the generator matrix are given. Another program uses this to give the minimum distance between two code words in a code.
3. We give a program which decodes a received word into a codeword using the nearest neighbor algorithm, provided the prime p, the distance d, and the generator matrix are given.
4. We give a decoder for a binary Hamming code.
5. We also give a few string-theoretic procedures which might be useful for decoding.

Reference: F. MacWilliams and N. Sloane, The theory of error-correcting codes , North-Holland, 1977

> restart;

> with(linalg):
with(padic):

Warning, new definition for norm

Warning, new definition for trace

>

> read(`c:/maplev4/bin.win/codes.mpl`);

Hamming codes

Parity check matrices of the binary Hamming code of length 2^2-1=3:

> hamming(2);

> H:=hamming(3);
Parity check matrices of the binary Hamming code of length 2^3-1=7:

A generator matrix of the binary Hamming code of length 3:

> hamming_generator(2);

> G1:=hamming_generator(3);
A generator matrix of the binary Hamming code of length 7:

> C1:=code_list(G1,2):
C1:=sort(C1,weight_order);
We can print out the list of all codewords, sorted according to weight:

> min_distance(G1,2);
The minimum distance of the binary Hamming code of length 3

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

> decode_hamming(v1);
This command only works for binary Hamming codes.

> decode(v1,G1,2,3);
This command works for any linear code (2 is the prime residue, 3 is the distance of the code).

Cyclic codes

One can test if g(x) is the 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+1,7,2);

> min_distance(G,2);

The following generator matrix is the same size as that of the above Hamming code. Do they yield the same code?

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

> C2:=code_list(G2,2):
C2:=sort(C2,weight_order);

> evalb(C1=C2);
This cyclic code generated by x^3+x^2+1 is not the Hamming code of length 7 and distance 3, over F_2, given above.

> min_distance(G,2);

There is some built-in error checking in generator_matrix :

> generator_matrix(x^2+1,7,2);

Error, (in generator_matrix) the polynomial doesn't generate a cyclic code

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);

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

> decode(v1,G,2,2);

> check_matrix(x^3+y^2+1,7,2);
check_matrix(x^3+1,7,2);
check_matrix has some built-in error checking

Error, (in check_matrix) g should be a polynomial in x

Error, (in check_matrix) the polynomial doesn't generate a cyclic code

>

Golay codes

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

> G:=golay12();

> min_distance(G,3);
This is very time-consuming.

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

> H:=golay_check12();

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

> decode(v1,G,3,5);
The decoding:

> v2:=[1, 1, 2, 2, 2, 1, 0, 1, 0, 0, 1, 2];
decode(v2,G,3,5);
Another example, with 2 errors.

>

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

> G:=golay11();

> min_distance(G,3);
This is very time-consuming.

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();

> v1:=[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,v1,2);
v1 is not a codeword in the (23,12)-Golay code. It has only 1 error (in the first position).

> decode(v1,G,2,7);
This is time-consuming to decode than the above Hamming code since the Golay code is larger.

> v2:=[0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0];
matrix_times_vector_modp(H,v2,2);
decode(v2,G,2,7);
This "string" has 3 errors

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

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

> coldim(G);coldim(H);

Some string-theoretic procedures (useful for decoding).

Note: strings in Maple V5 use double quotes: "we" is a string in V5. The double quotes should be removed for use in V4.

First, we read in Book I of Milton's Paradise Lost . The text has been put in a file, all the " marks removed (replaced by ' marks, in order not to conflict with MAPLE's string conventions), and the entire text is surrounded by " marks and that string is called paradiselost . The carriage returns cause MAPLE's read command to print pages of warning statements, so they will be surpressed by setting warnlevel=0.

> interface(warnlevel=0);
read(`c:/maplev4/bin.win/paradise_lost.mpl`):

> whattype(paradiselost);
length(paradiselost);
This text has about 35000 characters.

How many lines (carriage returns) are there? It takes about 20 seconds on my Cyrex 200mz and 30 seconds on an Intel 200mz to find out:

> t0:=time();
L:=Locate("\n",paradiselost):
nops(L);
time()-t0;

How many times does Milton use the word "men", and where?

> L:=Locate("men",paradiselost);
nops(L);

The next calculation is more time-consuming. It will tell us how frequently "a" occurs, "b" occurs, ..., and arrange the result in decreasing order. The time below is for a Cyrex 200 mz computer.

> t0:=time();
L:=statistics(paradiselost);
print(`This computation took `,time()-t0,` seconds`);
print(`Total percentage accounted for: `,add(x[2],x=L));

> seg("qwert",2,3);
Returns the substring indicated. (See also MAPLE's built-in substring command.)

> SearchText(wx,abcdefghijklmnopqrstuvwxyz);
SearchText(Wx,abcdefghijklmnopqrstuvwxyz);
This is a built-in MAPLE command (case sensitive). Self explanatory.

> searchtext(wx,abcdefghijklmnopqrstuvwxyz);
searchtext(Wx,abcdefghijklmnopqrstuvwxyz);
This is a built-in MAPLE command (case insensitive). Self explanatory.

> length(abcdefghijklmnopqrstuvwxyz);
This is a built-in MAPLE command. Self explanatory.

> locate("wx","abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz");
Self explanatory. Case insensitive.

> Locate("wx","abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstUVWXYZabcdefghijklmnopqrstuvwxyz");
Self explanatory. Case sensitive.

>

>