[Jump to code hierarchy]

\([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]. The dual of the Golay code is its \([23,11,8]\) even-weight subcode [5,6].

Shortening the Golay code yields shortened Golay codes [7] like the \([22,10,8]\), \([22,11,7]\), and \([22,12,6]\) codes. The quadruply shortened Golay code is optimal [8].

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 [9; Table II] \begin{align} \left(\begin{smallmatrix} 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{smallmatrix}\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 group of several shortened Golay codes is \(\mathcal{M}_{22}\) [7].

Decoding

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

Realizations

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

Notes

See Ref. [14; Sec. 1.13][15; Secs. 2.5 and 2.7] for an introduction to Golay codes.

Cousins

Primary Hierarchy

Parents
The Golay code is perfect [16; Thm. 12.3.3 and Def. 12.3.4].
The Golay code is a binary quadratic residue code with generator polynomial \(r(x)\) over \(\mathbb{F}_2\) with length \(n=23\) [24; Ex. 3.2.10][3; Ch. 16].
The Golay code is equivalent to a BCH code with Bose distance 5 [3; Ch. 20].
The Golay code and several of its extended, shortened, and punctured versions are LP universally optimal codes [25].
\([23, 12, 7]\) Golay code

References

  1. [1]

    M. J. E. Golay, “Notes on digital coding”, Proceedings of the IEEE 37, 657 (1949)

  2. [2]

    J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI

  3. [3]

    F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)

  4. [4]

    P. Delsarte and J. M. Goethals, “Unrestricted codes with the golay parameters are unique”, Discrete Mathematics 12, 211 (1975) DOI

  5. [5]

    W. Feit, “Some remarks on weight functions of spaces over GF(2)”, unpublished (1972)

  6. [6]

    C. L. Mallows and N. J. A. Sloane, “Weight enumerators of self-orthogonal codes”, Discrete Mathematics 9, 391 (1974) DOI

  7. [7]

    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

  8. [8]

    D. C. Gijswijt, H. D. Mittelmann, and A. Schrijver, “Semidefinite code bounds based on quadruple distances”, (2010) arXiv:1005.4959

  9. [9]

    A. R. Calderbank, “The art of signaling: fifty years of coding theory”, IEEE Transactions on Information Theory 44, 2561 (1998) DOI

  10. [10]

    A. J. VITERBI, “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm”, The Foundations of the Digital Wireless World 41 (2009) DOI

  11. [11]

    B. Honary and G. Markarian, “New simple encoder and trellis decoder for Golay codes”, Electronics Letters 29, 2170 (1993) DOI

  12. [12]

    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

  13. [13]

    M. Waegell and P. K. Aravind, “Golay codes and quantum contextuality”, Physical Review A 106, (2022) arXiv:2206.04209 DOI

  14. [14]

    W. C. Huffman, J.-L. Kim, and P. Solé, “Basics of coding theory”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 3-44 DOI

  15. [15]

    C. Ding, “Cyclic Codes over Finite Fields”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 45-60 DOI

  16. [16]

    P. Boyvalenkov, D. Danev, “Linear programming bounds”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 251-266 DOI

  17. [17]

    P. Delsarte, J. M. Goethals, and J. J. Seidel, “Spherical codes and designs”, Geometriae Dedicata 6, 363 (1977) DOI

  18. [18]

    L. J. Paige, “A Note on the Mathieu Groups”, Canadian Journal of Mathematics 9, 15 (1957) DOI

  19. [19]

    M. HUBER, “CODING THEORY AND ALGEBRAIC COMBINATORICS”, Series on Coding Theory and Cryptology 121 (2010) arXiv:0811.1254 DOI

  20. [20]

    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

  21. [21]

    W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI

  22. [22]

    P. Boyvalenkov, P. Dragnev, D. Hardin, E. Saff, and M. Stoyanova, “Universal minima of discrete potentials for sharp spherical codes”, (2023) arXiv:2211.00092

  23. [23]

    N. P. Breuckmann and S. Burton, “Fold-Transversal Clifford Gates for Quantum Codes”, Quantum 8, 1372 (2024) arXiv:2202.06647 DOI

  24. [24]

    P. R. J. Östergård, “Construction and Classification of Codes”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 61-78 DOI

  25. [25]

    H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI

Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

— see instructions

Zoo Code ID: golay

Cite as:
“\([23, 12, 7]\) Golay code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/golay, arXiv:2606.11484
BibTeX:
@incollection{eczoo_golay,
title={\([23, 12, 7]\) Golay code},
booktitle={The Error Correction Zoo},
year={2026},
editor={Albert, Victor V. and Faist, Philippe},
eprint={2606.11484},
doi={10.48550/arXiv.2606.11484},
url={https://errorcorrectionzoo.org/c/golay}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/golay

Cite as:

“\([23, 12, 7]\) Golay code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/golay, arXiv:2606.11484

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