Ternary Golay code

Ternary Golay code[1]

Description

A \([11,6,5]_3\) perfect ternary 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 \([12,6,6]_3\) extended ternary Golay code. Up to equivalence, both codes are unique for their respective parameters [4]. The dual of the ternary Golay code is a \([11,5,6]_3\) projective two-weight subcode.

A generator matrix for the ternary Golay code is \begin{align} \left(\begin{array}{ccccccccccc} 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 2 & 2 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 2 & 1 & 0 & 2 \\ 0 & 0 & 1 & 0 & 0 & 1 & 2 & 1 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 & 0 & 1 & 2 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 2 & 2 & 1 & 1 \\ \end{array}\right)~. \tag*{(1)}\end{align}

The automorphism group of the ternary Golay code is the Mathieu group \(\mathcal{M}_{11}\), and the automorphism group of the extended ternary Golay code is the double cover of the Mathieu group \(\mathcal{M}_{12}\), two of the sporadic simple groups.

Decoding

Decoder for the extended ternary Golay code using the tetracode [5].

Realizations

Code used in football pools with at least one good bet [6,7]. In fact, the code was originally constructed by Juhani Virtakallio and published in the Finnish football pool magazine Veikkaaja [7,8].Proofs of the quantum mechanical Kochen-Specker theorem [9].

Parents

\(q\)-ary quadratic-residue (QR) code — The ternary Golay code is a quadratic residue code over \(GF(3)\) with residue set \(Q = \{1, 3, 4, 5, 9\} \) and generator polynomial \(x^5 + x^4 - x^3 + x^2 - 1\) ([3], Ch. 16).
Perfect code — The ternary Golay code is perfect.
\(q\)-ary sharp configuration — The ternary Golay code and one of its shortened versions are \(q\)-ary sharp configurations [10; Table 12.1].
Small-distance block code

Cousins

Golay code
Self-dual linear code — The extended ternary Golay code is self-dual.
Projective geometry code — The extended ternary Golay code admits a projective geometric construction ([11], pg. 296).
Divisible code — Extended ternary Golay code is 3-divisible ([11], pg. 296).
Universally optimal \(q\)-ary code — The ternary Golay code and several of its extended, shortened, and punctured versions are LP universally optimal codes [12].
Projective two-weight code — The dual of the ternary Golay code is a projective two-weight subcode [14,15][13; Ex. 19.3.2][16; Table 7.1].
Combinatorial design — The supports of the weight-five (weight-six) codewords of the (extended) ternary Golay code support the Steiner system \(S(4,5,11)\) (\(S(5,6,12)\)) [17,18][2; pg. 89]. Its blocks are called hexads.
Pless symmetry code — The Pless symmetry code for \(p=5\) is the extended ternary Golay code.
Tetracode — Extended ternary Golay codewords can be obtained from tetracodewords [2]. The tetracode can be used to decode the extended ternary Golay code [5].
\([[11,1,5]]_3\) qutrit Golay code — The qutrit Golay code is a CSS code constructed from the ternary 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]: V. Pless, “Decoding the Golay codes”, IEEE Transactions on Information Theory 32, 561 (1986) DOI
[6]: 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
[7]: A. Barg, “At the Dawn of the Theory of Codes”, The Mathematical Intelligencer 15, 20 (1993) DOI
[8]: T. Thompson, From Error-Correcting Codes Through Sphere Packings to Simple Groups (American Mathematical Society, 1983) DOI
[9]: M. Waegell and P. K. Aravind, “Golay codes and quantum contextuality”, Physical Review A 106, (2022) arXiv:2206.04209 DOI
[10]: P. Boyvalenkov, D. Danev, "Linear programming bounds." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[11]: J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
[12]: H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
[13]: A. E. Brouwer, "Two-weight Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[14]: 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
[15]: A. E. Brouwer and H. Van Maldeghem, Strongly Regular Graphs (Cambridge University Press, 2022) DOI
[16]: 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
[17]: L. J. Paige, “A Note on the Mathieu Groups”, Canadian Journal of Mathematics 9, 15 (1957) DOI
[18]: M. HUBER, “CODING THEORY AND ALGEBRAIC COMBINATORICS”, Selected Topics in Information and Coding Theory 121 (2010) arXiv:0811.1254 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:

“Ternary Golay code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/ternary_golay

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/easy/ternary_golay.yml.