Description
A \([11,6,5]_3\) perfect ternary linear code with connections to various areas of mathematics, e.g., lattices [3] and sporadic simple groups [4]. Adding a parity bit to the code results in the self-dual \([12,6,6]_3\) extended ternary Golay code, whose weight enumerator is the Gleason polynomial \(g_5\) [5; Rem. 4.2.6]. Up to equivalence, both codes are unique for their respective parameters [6]. The dual of the ternary Golay code is a \([11,5,6]_3\) projective two-weight subcode [7; Exam. 19.3.2].
A generator matrix for the ternary Golay code is \begin{align} \left(\begin{array}{ccccccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 2 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 2 & 1 & 0 & 2 \\ 0 & 0 & 0 & 1 & 0 & 0 & 2 & 1 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 & 1 & 0 & 2 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 & 1 & 1 \\ \end{array}\right)~. \tag*{(1)}\end{align}
The permutation automorphism group of the ternary Golay code is the Mathieu group \(\mathcal{M}_{11}\), while the monomial automorphism group of the extended ternary Golay code is the double cover \(2.\mathcal{M}_{12}\); these are closely related to two sporadic simple groups.
Decoding
Decoder for the extended ternary Golay code using the tetracode [8].Realizations
Code used in football pools with at least one good bet [9,10]. In fact, the code was originally constructed by Juhani Virtakallio and published in the Finnish football pool magazine Veikkaaja [1,10,11].Proofs of the quantum mechanical Kochen-Specker theorem [12].Notes
The ternary Golay code is a quadratic-residue code [13; Sec. 2.7].Cousins
- \([23, 12, 7]\) Golay code— The ternary Golay code is the ternary counterpart of the binary Golay code.
- \([24, 12, 8]\) Extended Golay code— The extended ternary Golay code is the ternary counterpart of the extended binary Golay code.
- Self-dual linear code— The extended ternary Golay code is self-dual, i.e., a Type III code in the terminology of [5; Rems. 4.2.6 and 4.3.2].
- Self-dual code over \(\mathbb{Z}_q\)— The extended ternary Golay code is self-dual [5; Rem. 4.2.6].
- Projective geometry code— The extended ternary Golay code admits a projective geometric construction [14; pg. 296].
- Divisible code— The extended ternary Golay code is 3-divisible because ternary self-dual codes are Type III [5; Thm. 4.1.9].
- \(q\)-ary sharp configuration— The dual \([11,5,6]_3\) code of the ternary Golay code is the length-\(11\) ternary Golay-family sharp configuration in [15; Table 12.1]. The extended ternary Golay code is the corresponding sharp configuration at length \(12\).
- Projective two-weight code— The dual of the ternary Golay code is a projective two-weight subcode [16,17][7; Exam. 19.3.2][18; Table 7.1].
- \(\Lambda_{24}\) Leech lattice— A 12-dimensional complex version of the Leech lattice can be obtained from the ternary Golay code [19,20][3; pg. 200].
- Niemeier lattice— The extended ternary Golay code is the glue code for the Niemeier lattice \(A^{12}_2\) [3; Ch. 16, pg. 408].
- Combinatorial design— The supports of the weight-five codewords of the ternary Golay code and the weight-six codewords of the extended ternary Golay code support the Steiner systems \(S(4,5,11)\) and \(S(5,6,12)\), respectively [21,22][3; pg. 89]. The latter blocks are called hexads.
- \([2q+2,q+1]_3\) Pless symmetry code— The Pless symmetry code for \(p=5\) is the extended ternary Golay code.
- \([4,2,3]_3\) Tetracode— Extended ternary Golay codewords can be obtained from tetracodewords [3]. The tetracode can be used to decode the extended ternary Golay code [8].
- \([[11,1,5]]_3\) qutrit Golay code— The qutrit Golay code is a CSS code constructed from the ternary Golay code.
Primary Hierarchy
Parents
The ternary Golay code is perfect [15; Thm. 12.3.3 and Def. 12.3.4].
The ternary Golay code is a quadratic-residue code over \(\mathbb{F}_3\) with residue set \(Q = \{1, 3, 4, 5, 9\} \) and generator polynomial \(x^5 + x^4 - x^3 + x^2 - 1\) [23; Ex. 3.2.10][4; Ch. 16].
The ternary Golay code and several of its extended, shortened, and punctured versions are LP universally optimal codes [24]. The \([11,6,5]_3\) code is universally optimal but not sharp.
\([11,6,5]_3\) Ternary Golay code
References
- [1]
- Veikkaus-Lotto (Veikkaaja) magazine, issues 27, 28, and 33, August-September 1947
- [2]
- M. J. E. Golay, “Notes on digital coding”, Proceedings of the IEEE, 37 (1949) 657
- [3]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [4]
- F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)
- [5]
- S. Bouyuklieva, “Self-dual codes.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [6]
- P. Delsarte and J. M. Goethals, “Unrestricted codes with the golay parameters are unique”, Discrete Mathematics 12, 211 (1975) DOI
- [7]
- A. E. Brouwer, “Two-weight Codes.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [8]
- V. Pless, “Decoding the Golay codes”, IEEE Transactions on Information Theory 32, 561 (1986) DOI
- [9]
- H. Hämäläinen and S. Rankinen, “Upper bounds for football pool problems and mixed covering codes”, Journal of Combinatorial Theory, Series A 56, 84 (1991) DOI
- [10]
- A. Barg, “At the Dawn of the Theory of Codes”, The Mathematical Intelligencer 15, 20 (1993) DOI
- [11]
- T. Thompson, From Error-Correcting Codes Through Sphere Packings to Simple Groups (American Mathematical Society, 1983) DOI
- [12]
- M. Waegell and P. K. Aravind, “Golay codes and quantum contextuality”, Physical Review A 106, (2022) arXiv:2206.04209 DOI
- [13]
- C. Ding, “Cyclic Codes over Finite Fields.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [14]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
- [15]
- P. Boyvalenkov, D. Danev, “Linear programming bounds.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [16]
- N. Tzanakis and J. Wolfskill, “The diophantine equation x2 = 4qa2 + 4q + 1, with an application to coding theory”, Journal of Number Theory 26, 96 (1987) DOI
- [17]
- A. E. Brouwer and H. Van Maldeghem, Strongly Regular Graphs (Cambridge University Press, 2022) DOI
- [18]
- R. A. Games, “The packing problem for projective geometries over GF(3) with dimension greater than five”, Journal of Combinatorial Theory, Series A 35, 126 (1983) DOI
- [19]
- R. A. Wilson, “The complex leech lattice and maximal subgroups of the Suzuki group”, Journal of Algebra 84, 151 (1983) DOI
- [20]
- J. H. Conway and N. J. A. Sloane, “Twenty-three constructions for the Leech lattice”, Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 381, 275 (1982) DOI
- [21]
- L. J. Paige, “A Note on the Mathieu Groups”, Canadian Journal of Mathematics 9, 15 (1957) DOI
- [22]
- M. HUBER, “CODING THEORY AND ALGEBRAIC COMBINATORICS”, Series on Coding Theory and Cryptology 121 (2010) arXiv:0811.1254 DOI
- [23]
- P. R. J. Östergård, “Construction and Classification of Codes.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [24]
- 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
- Vikram Elijah Amin (2023-01-21) — most recent
- Victor V. Albert (2022-01-21)
- Victor V. Albert (2022-08-12)
- Shashank Sule (2022-03-02)
Cite as:
“\([11,6,5]_3\) Ternary Golay code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/ternary_golay