\([23, 12, 7]\) Golay code

\([23, 12, 7]\) 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]. Up to equivalence, it is unique for its 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}\), a sporadic simple group. The automorphism of several shortened Golay codes is \(\mathcal{M}_{22}\) [5].

Decoding

The Golay code has a trellis representation and can thus be decoded using trellis decoding [9,10].Bounded-distance decoder requiring at most 121 real operations [11].

Realizations

Proofs of the quantum mechanical Kochen-Specker theorem [12].

Cousins

Dual linear code— The dual of the Golay code is its \([23,11,8]\) even-weight subcode [6,7].
Universally optimal \(q\)-ary code— The Golay code and several of its extended, shortened, and punctured versions are LP universally optimal codes [13].
Spherical design— The dual of the Golay code forms a spherical 3-design under the antipodal mapping [14; Exam. 9.3].
\(\Lambda_{24}\) Leech lattice— The Leech lattice can be obtained by lifting the Golay code to \(\mathbb{Z}_4\) [15], appending a parity check, and applying Construction \(A_4\) [16] (see also [2,17]). Half of the lattice can be obtained in a different construction [18; Exam. 10.7.3].
Combinatorial design— The supports of the weight-seven codewords of the Golay code support the Steiner system \(S(4,7,23)\) [19,20][2; pg. 89]. Its blocks are called octads.
\([24, 12, 8]\) Extended Golay code— The extended Golay code is an extension of the Golay code by a parity-check bit.
\([6,3,4]_4\) Hexacode— There a connection between automorphisms of the even Golay code and the holomorph of the hexacode [21]. The hexacoed is often referred to as the Golay code over \(GF(4)\) [22].
\([11,6,5]_3\) Ternary Golay code
\([[23, 1, 7]]\) 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 certain automorphism group of the Bring code [23].

Member of code lists

Primary Hierarchy

Classical Domain

Binary Kingdom

Binary codeECC

Nearly perfect codeECC

Perfect binary codePerfect OA \(t\)-design ECC

Parents

Perfect binary code

The Golay code is perfect.

Binary quadratic-residue (QR) codeQR Linear \(q\)-ary Linear code over \(\mathbb{Z}_q\) Cyclic Constacyclic Skew-cyclic ECC

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 codeLinear \(q\)-ary Linear code over \(\mathbb{Z}_q\) Cyclic Constacyclic Skew-cyclic ECC

The Golay code is equivalent to a BCH code with Bose distance 5 ([3], Ch. 20).

\(q\)-ary sharp configurationOA Sharp configuration \(t\)-design Universally optimal ECC

The Golay code and two of its shortened versions are \(q\)-ary sharp configurations [24; Table 12.1].

\([23, 12, 7]\) 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]: 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]: A. J. VITERBI, “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm”, The Foundations of the Digital Wireless World 41 (2009) DOI
[10]: B. Honary and G. Markarian, “New simple encoder and trellis decoder for Golay codes”, Electronics Letters 29, 2170 (1993) DOI
[11]: 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
[12]: M. Waegell and P. K. Aravind, “Golay codes and quantum contextuality”, Physical Review A 106, (2022) arXiv:2206.04209 DOI
[13]: H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
[14]: P. Delsarte, J. M. Goethals, and J. J. Seidel, “Spherical codes and designs”, Geometriae Dedicata 6, 363 (1977) DOI
[15]: A. R. Hammons, P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P. Sole, “The Z/sub 4/-linearity of Kerdock, Preparata, Goethals, and related codes”, IEEE Transactions on Information Theory 40, 301 (1994) DOI
[16]: A. Bonnecaze and P. Solé, “Quaternary constructions of formally self-dual binary codes and unimodular lattices”, Lecture Notes in Computer Science 194 (1994) DOI
[17]: “Twenty-three constructions for the Leech lattice”, Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 381, 275 (1982) DOI
[18]: T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
[19]: L. J. Paige, “A Note on the Mathieu Groups”, Canadian Journal of Mathematics 9, 15 (1957) DOI
[20]: M. HUBER, “CODING THEORY AND ALGEBRAIC COMBINATORICS”, Series on Coding Theory and Cryptology 121 (2010) arXiv:0811.1254 DOI
[21]: 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
[22]: W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[23]: N. P. Breuckmann and S. Burton, “Fold-Transversal Clifford Gates for Quantum Codes”, Quantum 8, 1372 (2024) arXiv:2202.06647 DOI
[24]: P. Boyvalenkov, D. Danev, "Linear programming bounds." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) 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:

“\([23, 12, 7]\) 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.