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 self-dual \([24, 12, 8]\) extended Golay code. Up to equivalence, both codes are unique for their respective parameters [4]. Shortening the Golay code yields the \([22,10,8]\), \([22,11,7]\), and \([22,12,6]\) shortened Golay codes [5]. The dual of the Golay code is its \([23,11,8]\) even-weight subcode [6,7].

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. Its generator matrix is [8; Table II] \begin{align} \left(\begin{array}{ccccccccccccccccccccccc} 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right)~. \tag*{(1)}\end{align}

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. The automorphism of several shortened Golay codes is \(\mathcal{M}_{22}\) [5].

Decoding

Majority decoding for the extended Golay code [9].Decoder for the extended Golay code using the hexacode [10].Both Golay codes have a trellis representation and can thus be decoded using trellis decoding [11,12].Bounded-distance decoder requiring at most 121 real operations [13].

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 [14].Extended Golay code used in American military standards for automatic link establishment in high frequency radio systems [15].Proofs of the quantum mechanical Kochen-Specker theorem [16].

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 [17; Table 12.1].

Cousins

Nearly perfect code — The extended Golay code is nearly perfect.
Dual linear code — The dual of the Golay code is its \([23,11,8]\) even-weight subcode [6,7].
Self-dual linear code — The extended Golay code is the unique code at its parameters and happens to be self-dual [4][18; Remark 4.3.11].
Group-algebra code — The extended Golay code is a group-algebra code for various groups [19–21]; see [22; 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 [23].
Spherical design — The dual of the Golay code forms a spherical three-design under the antipodal mapping [24; Exam. 9.3].
Lexicographic code — The extended Golay code is a lexicode [25,26][3; pg. 327].
\(\Lambda_{24}\) Leech lattice code — The \(\Lambda_{24}\) Leech lattice can be obtained by lifting the Golay code to \(\mathbb{Z}_4\) [27], appending a parity check, and applying construction \(A_4\) [28] (see also [2]). Half of the lattice can be obtained in a different construction [29; Ex. 10.7.3].
Combinatorial design — 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)\)) [30,31][2; pg. 89]. Its blocks are called octads.
Nordstrom-Robinson (NR) code — The NR code can be constructed using the extended Golay code by first selecting a set of Golay codewords satisfying certain conditions and then deleteing specific coordinates [3; pg. 73].
Hexacode — Extended Golay codewords can be obtained from hexacodewords [2]. The hexacode can be used to decode the extended Golay code [10]. There is also a connection between automoprhisms of the even Golay code and the holomorph of the hexacode [32].
Ternary Golay code
Orthogonal array (OA) — The extended Golay code is an orthogonal array of strength 7 [33; Exam. 1]
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.
Quantum Golay code — The qubit Golay code is a CSS code constructed with the Golay code.
\([[30,8,3]]\) Bring code — The automorphism group of the parity-check matrix of the Golay code is the same as a certai automorphism group of the Bring code [34].

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]: P. Delsarte and J. M. Goethals, “Unrestricted codes with the golay parameters are unique”, Discrete Mathematics 12, 211 (1975) DOI
[5]: J. H. Conway and N. J. A. Sloane, “Orbit and coset analysis of the Golay and related codes”, IEEE Transactions on Information Theory 36, 1038 (1990) DOI
[6]: W. Feit. Some remarks on weight functions of spaces over GF(2), unpublished (1972)
[7]: C. L. Mallows and N. J. A. Sloane, “Weight enumerators of self-orthogonal codes”, Discrete Mathematics 9, 391 (1974) DOI
[8]: A. R. Calderbank, “The art of signaling: fifty years of coding theory”, IEEE Transactions on Information Theory 44, 2561 (1998) DOI
[9]: J.-M. Goethals, “On the Golay perfect binary code”, Journal of Combinatorial Theory, Series A 11, 178 (1971) DOI
[10]: V. Pless, “Decoding the Golay codes”, IEEE Transactions on Information Theory 32, 561 (1986) DOI
[11]: A. J. VITERBI, “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm”, The Foundations of the Digital Wireless World 41 (2009) DOI
[12]: B. Honary and G. Markarian, “New simple encoder and trellis decoder for Golay codes”, Electronics Letters 29, 2170 (1993) DOI
[13]: 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
[14]: E. C. Stone, “The Voyager 2 encounter with Uranus”, Journal of Geophysical Research: Space Physics 92, 14873 (1987) DOI
[15]: 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.
[16]: M. Waegell and P. K. Aravind, “Golay codes and quantum contextuality”, Physical Review A 106, (2022) arXiv:2206.04209 DOI
[17]: P. Boyvalenkov, D. Danev, "Linear programming bounds." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[18]: E. M. Rains and N. J. A. Sloane, “Self-dual codes,” in Handbook of Coding Theory, eds. V. S. Pless and W. C. Huffman. Amsterdam: Elsevier, 1998, pp. 177–294.
[19]: I. McLoughlin and T. Hurley, “A Group Ring Construction of the Extended Binary Golay Code”, IEEE Transactions on Information Theory 54, 4381 (2008) DOI
[20]: 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
[21]: F. Bernhardt, P. Landrock, and O. Manz, “The extended golay codes considered as ideals”, Journal of Combinatorial Theory, Series A 55, 235 (1990) DOI
[22]: W. Willems, "Codes in Group Algebras." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[23]: H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
[24]: P. Delsarte, J. M. Goethals, and J. J. Seidel, “Spherical codes and designs”, Geometriae Dedicata 6, 363 (1977) DOI
[25]: M. J. T. Guy, unpublished.
[26]: J. Conway and N. Sloane, “Lexicographic codes: Error-correcting codes from game theory”, IEEE Transactions on Information Theory 32, 337 (1986) DOI
[27]: 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
[28]: A. Bonnecaze and P. Solé, “Quaternary constructions of formally self-dual binary codes and unimodular lattices”, Algebraic Coding 194 (1994) DOI
[29]: T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
[30]: L. J. Paige, “A Note on the Mathieu Groups”, Canadian Journal of Mathematics 9, 15 (1957) DOI
[31]: M. HUBER, “CODING THEORY AND ALGEBRAIC COMBINATORICS”, Selected Topics in Information and Coding Theory 121 (2010) arXiv:0811.1254 DOI
[32]: 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
[33]: P. Delsarte and V. I. Levenshtein, “Association schemes and coding theory”, IEEE Transactions on Information Theory 44, 2477 (1998) DOI
[34]: N. P. Breuckmann and S. Burton, “Fold-Transversal Clifford Gates for Quantum Codes”, Quantum 8, 1372 (2024) arXiv:2202.06647 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/edit/main/codes/classical/bits/cyclic/golay.yml.