In mathematics and electronics engineering, a binary Golay code is a type of linear error-correcting code used in digital communications. The binary Golay code, along with the ternary Golay code, has a particularly deep and interesting connection to the theory of finite sporadic groups in mathematics. These codes are named in honor of Marcel J. E. Golay whose 1949 paper introducing them has been called, by E. R. Berlekamp, the "best single published page" in coding theory. There are two closely related binary Golay codes. The extended binary Golay code, G24 encodes 12 bits of data in a 24-bit word in such a way that any 3-bit errors can be corrected or any 7-bit errors can be detected. The other, the perfect binary Golay code, G23, has codewords of length 23 and is obtained from the extended binary Golay code by deleting one coordinate position. In standard coding notation the codes have parameters and , corresponding to the length of the codewords, the dimension of the code, and the minimum Hamming distance between two codewords, respectively.
Mathematical definition
In mathematical terms, the extended binary Golay code G24 consists of a 12-dimensional linear subspaceW of the space of 24-bit words such that any two distinct elements of W differ in at least 8 coordinates. W is called a linear code because it is a vector space. In all, W comprises elements.
The elements of W are called code words. They can also be described as subsets of a set of 24 elements, where addition is defined as taking the symmetric difference of the subsets.
In the extended binary Golay code, all code words have Hamming weights of 0, 8, 12, 16, or 24. Code words of weight 8 are called octads and code words of weight 12 are called dodecads.
Octads of the code G24 are elements of the S Steiner system. There are octads and 759 complements thereof. It follows that there are dodecads.
Two octads intersect in 0, 2, or 4 coordinates in the binary vector representation. An octad and a dodecad intersect at 2, 4, or 6 coordinates.
Up to relabeling coordinates, W is unique.
The binary Golay code, G23 is a perfect code. That is, the spheres of radius three around code words form a partition of the vector space. G23 is a 12-dimensional subspace of the space F223. The automorphism group of the perfect binary Golay code, G23, is the Mathieu group. The automorphism group of the extended binary Golay code is the Mathieu group, of order. is transitive on octads and on dodecads. The other Mathieu groups occur as stabilizers of one or several elements of W.
Constructions
Lexicographic code: Order the vectors in V lexicographically. Starting with w0 = 0, define w1, w2,..., w12 by the rule that wn is the smallest integer which differs from all linear combinations of previous elements in at least eight coordinates. Then W can be defined as the span of w1,..., w12.
Mathieu group: Witt in 1938 published a construction of the largest Mathieu group that can be used to construct the extended binary Golay code.
Quadratic residue code: Consider the set N of quadratic non-residues. This is an 11-element subset of the cyclic groupZ/23Z. Consider the translates t+N of this subset. Augment each translate to a 12-element set St by adding an element ∞. Then labeling the basis elements of V by 0, 1, 2,..., 22, ∞, W can be defined as the span of the words St together with the word consisting of all basis vectors.
As a Cyclic code: The perfect G23 code can be constructed via the factorization of over the binary field GF:
Turyn's construction of 1967, "A Simple Construction of the Binary Golay Code," that starts from the Hamming code of length 8 and does not use the quadratic residues mod 23.
From the Steiner System S, consisting of 759 subsets of a 24-set. If one interprets the support of each subset as a 0-1-codeword of length 24, these are the "octads" in the binary Golay code. The entire Golay code can be obtained by repeatedly taking the symmetric differences of subsets, i.e. binary addition. An easier way to write down the Steiner system resp. the octads is the Miracle Octad Generator of R. T. Curtis, that uses a particular 1:1-correspondence between the 35 partitions of an 8-set into two 4-sets and the 35 partitions of the finite vector space into 4 planes. Nowadays often the compact approach of Conway's hexacode, that uses a 4×6 array of square cells, is used.
Winning positions in the mathematical game of Mogul: a position in Mogul is a row of 24 coins. Each turn consists of flipping from one to seven coins such that the leftmost of the flipped coins goes from head to tail. The losing positions are those with no legal move. If heads are interpreted as 1 and tails as 0 then moving to a codeword from the extended binary Golay code guarantees it will be possible to force a win.
It is convenient to use the "Miracle Octad Generator" format, with co-ordinates in an array of 4 rows, 6 columns. Addition is taking the symmetric difference. All 6 columns have the same parity, which equals that of the top row. A partition of the 6 columns into 3 pairs of adjacent ones constitutes a trio. This is a partition into 3 octad sets. A subgroup, the projective special linear group PSL x S3 of a trio subgroup of M24 is useful for generating a basis. PSL permutes the octads internally, in parallel. S3 permutes the 3 octads bodily. The basis begins with octad T: and 5 similar octads. The sum N of all 6 of these code words consists of all 1's. Adding N to a code word produces its complement. Griess uses the labeling: PSL is naturally the linear fractional group generated by and. The 7-cycle acts on T to give a subspace including also the basis elements and The resulting 7-dimensional subspace has a 3-dimensional quotient space upon ignoring the latter 2 octads. There are 4 other code words of similar structure that complete the basis of 12 code words for this representation of W. W has a subspace of dimension 4, symmetric under PSL x S3, spanned by N and 3 dodecads formed of subsets,, and.
Error correction was vital to data transmission in the Voyager 1 and 2 spacecraft particularly because memory constraints dictated offloading data virtually instantly leaving no second chances. Hundreds of color pictures of Jupiter and Saturn in their 1979, 1980, and 1981 fly-bys would be transmitted within a constrained telecommunications bandwidth. Hence Golay encoding was utilised. Color image transmission required three times the amount of data as black and white images, so the Hadamard code that was used to transmit the black and white images was switched to the Golay code. This Golay code is only triple-error correcting, but it could be transmitted at a much higher data rate than the Hadamard code that was used during the Mariner mission.
