The Golay Code

The Golay code is a collection of sequences, each having length 24 and composed only of symbols 0 and 1. There are over 16 million such sequences, but the code uses just 4096 of them, and its symmetry group is the Mathieu group M₂₄.

The Golay code is derived from the Witt design, which uses 24 symbols, in the following way. List the 24 symbols horizontally in a given order. Any subset of them can be specified by assigning a 1 to each symbol in the subset, and a 0 to each symbol not in the subset. In this way each subset appears as a sequence of twenty-four 1s and 0s. The Witt design uses some special subsets of size 8, called octads, each of which therefore yields a sequence having eight 1s and sixteen 0s.

Any two sequences of 0s and 1s having the same length — in this case length 24 — can be added in the following way. If they agree in a given position their sum is 0 in that position, and if they disagree it is 1. This is like adding the 1s or 0s in each position according to the rule 0+0=0, 1+1=0, and 0+1=1 (the set {0,1} with this property is called the field of two elements). In the Witt design two distinct octads have exactly 4, 2 or 0 symbols in common, and their sum therefore gives a subset of size 8, 12 or 16. In other words a sequence of 0s and 1s in which the number of 1s is 8, 12 or 16.

Repeated additions give sequences in which the number of 1s is one of: 0, 8, 12, 16 or 24. It turns out that each sequence having eight 1s represents an octad in the Witt design, and each sequence having sixteen 1s represents the complement of an octad (in other words the 0s are in the positions of an octad). There are 759 octads in the Witt design, and hence 759 sequences having exactly eight 1s, and another 759 having sixteen 1s. The number of sequences having exactly twelve 1s is 2576, there is one sequence having twenty-four 1s, and one having no 1s. The total number of sequences for the Golay code is therefore:

1 + 759 + 2576 + 759 + 1 = 4096

Notice that 4096 = 2¹². The Golay code is a 12-dimensional subspace in a 24-dimensional space over the field {0,1} of two elements.