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

Extended Golay code used in the Voyager 1 and 2 spacecraft, transmitting hundreds of color pictures of Jupiter and Saturn in their 1979, 1980, and 1981 fly-bys [9].Extended Golay code used in American military standards for automatic link establishment in high frequency radio systems [10].Proofs of the quantum mechanical Kochen-Specker theorem [11].

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 binary 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).
\(q\)-ary sharp configuration — The Golay code and two of its shortened versions are \(q\)-ary sharp configurations [12; Table 12.1].

Cousins

Nearly perfect code — The extended Golay code is nearly perfect.
Self-dual linear code — The extended Golay code is self-dual.
Group-algebra code — The extended Golay code is a group-algebra code for various groups [13–15][16; Ex. 16.5.1].
Universally optimal \(q\)-ary code — The Golay code and several of its extended, shortened, and punctured versions are LP universally optimal codes [17].
\(\Lambda_{24}\) Leech lattice code — The \(\Lambda_{24}\) Leech lattice can be obtained by lifting the Golay code to \(\mathbb{Z}_4\) [18], appending a parity check, and applying construction \(A_4\) [19] (see also [2]). Half of the lattice can be obtained in a different construction [20; Ex. 10.7.3].
Combinatorial design code — The supports of the weight-seven (weight-eight) codewords of the (extended) Golay code support the Steiner system \(S(4,7,23)\) (\(S(5,6,12)\)) [21; pg. 89]. Its blocks are called octads.
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 [22].
Ternary Golay code
Icosahedron code — The parity bits of the extended Golay code can be visualized to lie on the vertices of the icosahedron; see post by J. Baez for more details.

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]: M. Waegell and P. K. Aravind, “Golay codes and quantum contextuality”, Physical Review A 106, (2022) arXiv:2206.04209 DOI
[12]: P. Boyvalenkov, D. Danev, "Linear programming bounds." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[13]: I. McLoughlin and T. Hurley, “A Group Ring Construction of the Extended Binary Golay Code”, IEEE Transactions on Information Theory 54, 4381 (2008) DOI
[14]: S. T. Dougherty et al., “Group rings, G-codes and constructions of self-dual and formally self-dual codes”, Designs, Codes and Cryptography 86, 2115 (2017) DOI
[15]: F. Bernhardt, P. Landrock, and O. Manz, “The extended golay codes considered as ideals”, Journal of Combinatorial Theory, Series A 55, 235 (1990) DOI
[16]: W. Willems, "Codes in Group Algebras." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[17]: H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
[18]: A. R. Hammons et al., “The Z/sub 4/-linearity of Kerdock, Preparata, Goethals, and related codes”, IEEE Transactions on Information Theory 40, 301 (1994) DOI
[19]: A. Bonnecaze and P. Solé, “Quaternary constructions of formally self-dual binary codes and unimodular lattices”, Algebraic Coding 194 (1994) DOI
[20]: T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
[21]: 10.1007/978-1-4757-6568-7
[22]: J. A. Harvey and G. W. Moore, “Moonshine, superconformal symmetry, and quantum error correction”, Journal of High Energy Physics 2020, (2020) arXiv:2003.13700 DOI

Page edit log

Vikram Elijah Amin (2023-01-21) — most recent
Victor V. Albert (2022-01-21)
Victor V. Albert (2022-08-10)
Noah Berthusen (2022-03-02)

Cite as:

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

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