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 $ {\mathcal G} _ {23 } $ is a $ 12 $- dimensional subspace of $ \mathbf F _ {2} ^ {23 } $ with the property that any two vectors (i.e., words) differ in at least $ 7 $ positions (they have distance $ d = 7 $). In coding terminology, $ {\mathcal G} _ {23 } $ is a $ [ 23,12,7 ] $ binary code, i.e., a $ 3 $- error-correcting code (cf. Error-correcting code). Similarly, the ternary Golay code $ {\mathcal G} _ {11 } $ is a $ [ 11,6,5 ] $ 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 $ e $- error-correcting perfect codes with $ e > 1 $ over any alphabet $ Q $ for which $ | Q | $ is a prime power. A perfect $ e $- error-correcting code is a subset of $ Q ^ {n} $ such that every vector in the space has distance at most $ e $ to a unique codeword.

An extension of a code $ C $ of length $ n $ is the set of words of length $ n + 1 $ obtained by adjoining an extra coordinate to all the words of $ C $ in such a way that the sum of the $ n + 1 $ coordinates is $ 0 $. The extended codes $ {\mathcal G} _ {24 } $ and $ {\mathcal G} _ {12 } $ are of interest in group theory because their automorphism groups are the $ 5 $- transitive Mathieu groups $ M _ {24 } $ and $ M _ {12 } $( 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) $ 8 $ in $ {\mathcal G} _ {24 } $ are the blocks of the (unique) Steiner system $ S ( 5,8,24 ) $. Similarly, the words of weight $ 6 $ in $ {\mathcal G} _ {12 } $ support the blocks of the (unique) Steiner system $ S ( 5,6,12 ) $.

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

1) Make a list of the numbers $ 0,1 \dots 2 ^ {24 } - 1 $ written binary as vectors in $ \mathbf F _ {2} ^ {24 } $. Delete each vector that has distance less than $ 8 $ to a previous vector that has not been deleted. At the end of this procedure, $ 4096 $ vectors will remain. They form a linear code, in fact $ {\mathcal G} _ {24 } $.

2) In the spaces $ \mathbf F _ {2} ^ {23 } $ and $ \mathbf F _ {3} ^ {11 } $, consider the codes of length $ n = 23 $, respectively $ n = 11 $, generated by the vectors $ {\vec{c} } _ {i} $( $ 1 \leq i \leq n $) for which $ c _ {i,j } = 1 $ if $ j - i $ is a non-zero square and $ 0 $ otherwise. One thus obtains the binary and the ternary Golay code.

3) Consider the $ ( 11 \times 11 ) $-[[ circulant matrix]] with top row $ ( 01000111011 ) $. This is the incidence matrix of the unique $ 2 $- $ ( 11,6,3 ) $- design. Form $ P $ by bordering this matrix with a column of $ 1 $' s in front and a row of $ 1 $' s on top, with a $ 0 $ in the upper left-hand corner (cf. Bordering method). Then adjoin $ I _ {12 } $ in front of $ P $. One obtains a $ ( 12 \times 24 ) $- matrix $ G $ in which every row has eight $ 1 $' s (except the top row, which has $ 12 $). The rows of $ G $ generate $ {\mathcal G} _ {24 } $.

4) As in 3), form a $ ( 5 \times 5 ) $- circulant with top row $ ( 0,1, - 1, - 1,1 ) $ and border it on top with a row of $ 1 $' s. To this, adjoin $ I _ {6} $ in front to form a $ ( 6 \times 11 ) $- matrix $ G $. The rows of $ G $ generate the $ [ 11,6,5 ] $ 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)