\([24, 12, 8]\) Extended Golay code[1]
Description
A self-dual \([24, 12, 8]\) code that is obtained from the Golay code by adding a parity check. Equivalently, puncturing any coordinate yields the \([23,12,7]\) Golay code. Up to equivalence, it is unique for its parameters [2], and it is the unique \([24,12,8]\) extremal Type II code [3; Rems. 4.3.10 and 4.3.11].
The automorphism group of the extended Golay code is the Mathieu group \(\mathcal{M}_{24}\), a sporadic simple group [3; Rem. 4.3.11].
Decoding
Majority decoding [4].Decoder using the hexacode [5].The extended Golay code has a trellis representation and can thus be decoded using trellis decoding [6,7].Realizations
Voyager 1 and 2 spacecraft, transmitting hundreds of color pictures of Jupiter and Saturn in their 1979, 1980, and 1981 fly-bys [8].American military standards for automatic link establishment in high frequency radio systems [9].Notes
See Ref. [10; Sec. 1.13][11; Sec. 2.5] for an introduction to Golay codes.Cousins
- Orthogonal array (OA)— The extended Golay code is an orthogonal array of strength 7 [12; Exam. 1].
- Self-dual linear code— The extended Golay code is the unique \([24,12,8]\) code, and in particular the unique self-dual doubly even code with those parameters [2][3; Rem. 4.3.11].
- \([2^m,m+1,2^{m-1}]\) First-order RM code— The first-order RM\((1,4)\) Reed-Muller code is a subcode of the extended Golay code [13; Ch. 5, pg. 146].
- \([8,4,4]\) extended Hamming code— The extended Golay code can be constructed from two suitably chosen extended Hamming \([8,4,4]\) codes using the \(|a+x|b+x|a+b+x|\) construction [14; pg. 588].
- Binary quadratic-residue (QR) code— The extended Golay code is an extended binary quadratic-residue code [14; Ch. 16].
- Icosahedron code— The parity bits of the extended Golay code can be visualized to lie on the vertices of the icosahedron; see [15] for more details. To construct the 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.
- Dodecahedron code— The parity bits of the extended Golay code can be visualized to lie on the vertices of the icosahedron; see [15] for more details. To construct the 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.
- \([23, 12, 7]\) Golay code— The extended Golay code is an extension of the Golay code by a parity-check bit.
- Group-algebra code— The extended Golay code is a group-algebra code for various groups [16–18]; see [20][19; Exam. 16.5.1].
- \(\Lambda_{24}\) Leech lattice— Two copies of the 24-dimensional packing obtained from the extended Golay code can be fitted together without overlap to form the Leech lattice [13; Ch. 5, pg. 145]. Half of the lattice can be obtained using Construction \(B^{\star}\) [21; Exam. 10.7.3].
- Niemeier lattice— The extended Golay code is the glue code for the Niemeier lattice \(A_1^{24}\) [13; Ch. 16, pg. 408].
- Combinatorial design— The supports of the weight-eight codewords of the extended Golay code support the Steiner system \(S(5,8,24)\) [22,23][13; pg. 89][13; Ch. 10, pg. 276]. Its blocks are called octads.
- \((16,256,6)\) Nordstrom-Robinson (NR) code— The NR code can be constructed using the extended Golay code by first selecting a set of codewords satisfying certain conditions and then deleting specific coordinates [14; pg. 73].
- \([6,3,4]_4\) Hexacode— Extended Golay codewords can be obtained from hexacodewords [13]. The hexacode can be used to decode the extended Golay code [5].
- \([11,6,5]_3\) Ternary Golay code— The extended ternary Golay code is the ternary counterpart of the extended binary Golay code.
- Pseudo Golay code— The mod-two reduction (mapping \(0,1,2,3\) to \(0,1,0,1\)) of all pseudo Golay codes yields the extended Golay code; see Ref. [24].
- Extended quaternary Golay code— Codewords of the extended quaternary Golay code with entries 0 and 2 are of the form \(2c\), where \(c\) is a codeword of the extended Golay code. Its mod-two reduction (mapping \(0,1,2,3\) to \(0,1,0,1\)) also yields the extended Golay code [24,25]. The quaternary Golay code can be constructed from the extended Golay code by Hensel lifting to \(\mathbb{Z}_4\) [25,26][13; 3rd Ed., pg. xxxiii].
Primary Hierarchy
Parents
The extended Golay code is nearly perfect.
The extended Golay code is a sharp configuration [27; Table 12.1].
\([2m+2,m+1]\) Karlin codeSelf-dual linear Self-dual additive Linear \(q\)-ary Linear code over \(\mathbb{Z}_q\) ECC
The extended Golay code is equivalent to the Karlin double circulant code for \(m=11\) [14; Ch. 16].
The extended Golay code is a lexicode [28,29][14; pg. 327].
\([24, 12, 8]\) Extended Golay code
References
- [1]
- M. J. E. Golay, “Notes on digital coding”, Proceedings of the IEEE 37, 657 (1949)
- [2]
- P. Delsarte and J. M. Goethals, “Unrestricted codes with the golay parameters are unique”, Discrete Mathematics 12, 211 (1975) DOI
- [3]
- S. Bouyuklieva, “Self-dual codes”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 79-96 DOI
- [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]
- E. C. Stone, “The Voyager 2 encounter with Uranus”, Journal of Geophysical Research: Space Physics 92, 14873 (1987) DOI
- [9]
- 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
- [10]
- 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
- [11]
- C. Ding, “Cyclic Codes over Finite Fields”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 45-60 DOI
- [12]
- P. Delsarte and V. I. Levenshtein, “Association schemes and coding theory”, IEEE Transactions on Information Theory 44, 2477 (1998) DOI
- [13]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [14]
- F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)
- [15]
- J. Baez, “Golay Code”, Visual Insight (2015) URL
- [16]
- I. McLoughlin and T. Hurley, “A Group Ring Construction of the Extended Binary Golay Code”, IEEE Transactions on Information Theory 54, 4381 (2008) DOI
- [17]
- S. T. Dougherty, J. Gildea, R. Taylor, and A. Tylyshchak, “Constructions of Self-Dual and Formally Self-Dual Codes from Group Rings”, (2016) arXiv:1604.07863
- [18]
- F. Bernhardt, P. Landrock, and O. Manz, “The extended golay codes considered as ideals”, Journal of Combinatorial Theory, Series A 55, 235 (1990) DOI
- [19]
- W. Willems, “Codes in Group Algebras”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 363-384 DOI
- [20]
- M. Borello and W. Willems, “On the algebraic structure of quasi group codes”, (2021) arXiv:1912.09167
- [21]
- T. Ericson and V. A. Zinoviev, eds., Codes on Euclidean Spheres (Elsevier, 2001)
- [22]
- L. J. Paige, “A Note on the Mathieu Groups”, Canadian Journal of Mathematics 9, 15 (1957) DOI
- [23]
- M. HUBER, “CODING THEORY AND ALGEBRAIC COMBINATORICS”, Series on Coding Theory and Cryptology 121 (2010) arXiv:0811.1254 DOI
- [24]
- G. W. Moore and R. K. Singh, “Beauty and the Beast Part 2: Apprehending the Missing Supercurrent”, Communications in Mathematical Physics 406, (2025) arXiv:2309.02382 DOI
- [25]
- A. Bonnecaze, P. Sole, and A. R. Calderbank, “Quaternary quadratic residue codes and unimodular lattices”, IEEE Transactions on Information Theory 41, 366 (1995) DOI
- [26]
- A. R. Calderbank and N. J. A. Sloane, “Modular and p-adic cyclic codes”, (2003) arXiv:math/0311319
- [27]
- P. Boyvalenkov, D. Danev, “Linear programming bounds”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 251-266 DOI
- [28]
- M. J. T. Guy, unpublished
- [29]
- J. Conway and N. Sloane, “Lexicographic codes: Error-correcting codes from game theory”, IEEE Transactions on Information Theory 32, 337 (1986) DOI
Page edit log
- Vikram Elijah Amin (2025-01-07) — most recent
Cite as:
“\([24, 12, 8]\) Extended Golay code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2025. https://errorcorrectionzoo.org/c/extended_golay