Golay code

Golay code[1]

Description

A \([23, 12, 7]\) perfect binary linear code with connections to various areas of mathematics, e.g., lattices [2] and sporadic simple groups [3]. Adding a parity bit to the code results in the \([24, 12, 8]\) extended Golay code. Up to equivalence, both codes are unique for their respective parameters.

To construct the Golay code, one can use the great dodecahedron to generate codewords by placing message bits on the faces and calculating the parity bits that live on the 12 vertices of the inner icosahedron.

Decoding

Majority decoding for the extended Golay code [4].Decoder for the extended Golay code using the hexacode [5].Both Golay codes have a trellis representation and can thus be decoded using trellis decoding [6][7].Bounded-distance decoder requiring at most 121 real operations [8].

Realizations

Used in the Voyager 1 and 2 spacecraft [9].Radio communications [10].

Notes

The automorphism group of the Golay code is the Mathieu group \(\mathcal{M}_{23}\), and the automorphism group of the extended Golay code is the Mathieu group \(\mathcal{M}_{24}\), two of the sporadic simple groups.

Parents

Perfect code — The Golay code is perfect.
Binary quadratic-residue (QR) code — The Golay code is a binary quadratic residue code with generator polynomial \(r(x)\) over \(GF(2)\) with length \(n=23\) ([3], Ch. 16).
Binary BCH code — The Golay code is equivalent to a BCH code with Bose distance 5 ([3], Ch. 20).

Cousins

Nearly perfect code — The extended Golay code is nearly perfect.
Dual linear code — The extended Golay code is self-dual.
Hexacode — Extended Golay codewords can be obtained from hexacodewords [2]. The hexacode can be used to decode the extended Golay code [5]. There is also a connection between automoprhisms of the even Golay code and the holomorph of the hexacode [11].
Ternary Golay Code

References

[1]: M. J. E. Golay, Notes on digital coding, Proc. IEEE, 37 (1949) 657.
[2]: J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999). DOI
[3]: F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[4]: J.-M. Goethals, “On the Golay perfect binary code”, Journal of Combinatorial Theory, Series A 11, 178 (1971). DOI
[5]: V. Pless, “Decoding the Golay codes”, IEEE Transactions on Information Theory 32, 561 (1986). DOI
[6]: A. J. VITERBI, “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm”, The Foundations of the Digital Wireless World 41 (2009). DOI
[7]: B. Honary and G. Markarian, “New simple encoder and trellis decoder for Golay codes”, Electronics Letters 29, 2170 (1993). DOI
[8]: A. Vardy, “Even more efficient bounded-distance decoding of the hexacode, the Golay code, and the Leech lattice”, IEEE Transactions on Information Theory 41, 1495 (1995). DOI
[9]: E. C. Stone, “The Voyager 2 encounter with Uranus”, Journal of Geophysical Research: Space Physics 92, 14873 (1987). DOI
[10]: E. E. Johnson. An Efficient Golay Codec For MIL-STD-188-141A and FED-STD-1045. Department of Electrical and Computer Engineering, New Mexico State University, 1991.
[11]: J. A. Harvey and G. W. Moore, “Moonshine, superconformal symmetry, and quantum error correction”, Journal of High Energy Physics 2020, (2020). DOI; 2003.13700

Page edit log

Victor V. Albert (2022-08-10) — most recent
Noah Berthusen (2022-03-02)

Cite as:

“Golay code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/golay

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/cyclic/golay.yml.