Golay code

From a purely mathematical point of view, the Golay codes are the most interesting codes constructed as yet (1996). The binary Golay code is a -dimensional subspace of with the property that any two vectors (i.e., words) differ in at least positions (they have distance ). In coding terminology, is a binary code, i.e., a -error-correcting code (cf. Error-correcting code). Similarly, the ternary Golay code is a ternary code. It was shown by A. Tietäväinen and J.H. van Lint (see [a3]) that the Golay codes are the only non-trivial -error-correcting perfect codes with over any alphabet for which is a prime power. A perfect -error-correcting code is a subset of such that every vector in the space has distance at most to a unique codeword.

An extension of a code of length is the set of words of length obtained by adjoining an extra coordinate to all the words of in such a way that the sum of the coordinates is . The extended codes and are of interest in group theory because their automorphism groups are the -transitive Mathieu groups and (cf. also Mathieu group).

For design theory (cf. also Design with mutually orthogonal resolutions; Block design), the Golay codes are important for the following reason. The words of weight (i.e., number of non-zero coordinates) in are the blocks of the (unique) Steiner system . Similarly, the words of weight in support the blocks of the (unique) Steiner system .

For each of the codes, several constructions are known. E.g.,

1) Make a list of the numbers written binary as vectors in . Delete each vector that has distance less than to a previous vector that has not been deleted. At the end of this procedure, vectors will remain. They form a linear code, in fact .

2) In the spaces and , consider the codes of length , respectively , generated by the vectors () for which if is a non-zero square and otherwise. One thus obtains the binary and the ternary Golay code.

3) Consider the -circulant matrix with top row . This is the incidence matrix of the unique - -design. Form by bordering this matrix with a column of 's in front and a row of 's on top, with a in the upper left-hand corner (cf. Bordering method). Then adjoin in front of . One obtains a -matrix in which every row has eight 's (except the top row, which has ). The rows of generate .

4) As in 3), form a -circulant with top row and border it on top with a row of 's. To this, adjoin in front to form a -matrix . The rows of generate the ternary Golay code.

For other constructions and more theory of these codes, see the references.

M.J.E. Golay (1902– 1989) was a Swiss physicist who worked in many different fields. He is known for his work on infrared spectroscopy and the invention of the capillary column, but to mathematicians mainly for his discovery of the two Golay codes.

References

[a1]	A.E. Brouwer, "Block designs" R. Graham (ed.) M. Grötschel (ed.) L. Lovász (ed.) , Handbook of Combinatorics , Elsevier (1995) pp. Chapt. 14
[a2]	P.J. Cameron, J.H. van Lint, "Designs, graphs, codes and their links" , Cambridge Univ. Press (1991)
[a3]	J.H. van Lint, "Introduction to coding theory" , Springer (1992)
[a4]	J.H. van Lint, R.M. Wilson, "A course in combinatorics" , Cambridge Univ. Press (1992)
[a5]	F.J. MacWilliams, N.J.A. Sloane, "The theory of error-correcting codes" , North-Holland (1977)