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

Cousins

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

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: golay

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

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.