Binary Golay code

There are two closely related error-correcting codes known as binary Golay codes. The extended binary Golay code encodes 12 bits of data in a 24-bit word in such a way that any triple-bit error can be corrected and any quadruple-bit error can be detected. The other, the perfect binary Golay code, has codewords of length 23 and is obtained from the extended binary Golay code by deleting one coordinate position (conversely, the extended binary Golay code is obtained from the perfect binary Golay code by adding a parity bit).

How Golay codes are transmitted

It is possible to send standard 8-bit bytes using this standard Golay code via using 8-to-12 modulation. Other bit allocation schemes may be used to allow 8-bit data to share bandwidth with 4-bit telemetry.

Mathematical definition

In mathematical terms, the extended binary Golay code consists of a 12-dimensional subspace W of the space V=F₂²⁴ of 24-bit words such that any two distinct elements of W differ in at least eight coordinates or, equivalently, such that any non-zero element of W has at least eight non-zero coordinates.

• The possible sets of non-zero coordinates as w ranges over W are called code words. In the extended binary Golay code, all code words have Hamming weight 0, 8, 12, 16, or 24.
• Up to relabelling coordinates, W is unique.

The perfect binary Golay code is a perfect code; that is, the balls of radius 3 around code words form a partition of the vector space.

Constructions

1. Lexicographic code: Order the vectors in V lexicographically (i.e., interpret them as unsigned 24-bit binary integers and take the usual ordering). Starting with w₁ = 0, define w₂, w₃, ..., w₁₂ by the rule that w_n 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 w₁, ..., w₁₂.
2. Quadratic residue code: Consider the set N of quadratic non-residues (mod 23). This is an 11-element subset of the cyclic group Z/23Z. Consider the translates t+N of this subset. Augment each translate to a 12-element set S_t by adding an element ∞. Then labelling the basis elements of V by 0, 1, 2, ..., 22, ∞, W can be defined as the span of the words S_t together with the word consisting of all basis vectors. (The perfect code is obtained by leaving out ∞.)
3. As a Cyclic code: The perfect G₂₃ code, can be constructed via factorisation of $x^{23}-1$, it is the code generated by $x^{11}+x^{10}+x^{6}+x^{5}+x^{4}+x^{2}+1/x^{23}-1$
4. The "Miracle Octad Generator" of R. T. Curtis: This uses a 4×6 array of square cells to picture the 759 Hamming-weight-8 code words, or "octads," of the extended binary Golay code. The remaining code words are obtained via symmetric differences of subsets of the 24 cells-- i.e., by binary addition. For details, see geometry of the 4×4 square.

Practical applications of Golay Codes

NASA Deep Space Missions

The Voyager 1 & 2 spacecraft needed to transmit hundreds of color pictures of Jupiter and Saturn in their 1979 and 1980 fly-bys within a constrained telecommunications bandwidth.

• Color image transmission required 3 times the amount of data, so the Golay (24,12,8) code was used.
• This Golay code is only 3-error correcting, but it could be transmitted at a much higher data rate.

ALE HF Data Communications

The new US government standards for Automatic Link Establishment (ALE) in High Frequency (HF) radio systems specifies the use of an extended (24,12) Golay block code for forward error correction (FEC).

• The Extended (24,12) Golay Code specified is a (24,12) block code.
• This code encodes 12 data bits to produce 24-bit code words.
• It is furthermore a systematic code, meaning that the 12 data bits are present in unchanged form in the code word.
• The generator polynomial for this code is
  • g(x) = x¹¹ + x⁹ + x⁷ + x⁶ + x⁵ + x + 1 (a variation of CRC-12?)

The minimum Hamming distance between any two code words (the number of bits by which any pair of code words differs) is 8, giving this code the power to detect up to 7 errors in each code word (and correct none), correct up to 3 while detecting 4, or any intermediate combination.

• These modes may be listed as (0,7), (1,6), (2,5), and (3,4), where the first number indicates the number of errors which may be corrected, and the second the number of errors which will be detected by each mode.

See also

• Mathieu group
• Steiner system
• Marcel J. E. Golay - after whom the code is named.

References

• Curtis, R. T. A new combinatorial approach to M₂₄. Math. Proc. Camb. Phil. Soc. 79 (1976) 25-42.