Mark Ronan's website
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 M24. The Golay code is derived from
the Witt design, which uses 24 symbols. Listing
these symbols horizontally in a given order, one specifies any subset of
these symbols by assigning a 1 to each symbol in the subset, and a 0 to the
others. Each subset then 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
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). Two distinct octads
have exactly 4, 2 or 0 symbols in common—this is an important feature
of the Witt design—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. In the last case, where there are sixteen 1s, and eight 0s, the 0s
lie in the positions of an octad. 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. Then 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 = 212.
The Golay code is a 12-dimensional subspace in a 24-dimensional space over
the field {0,1} of two elements. |
|