Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Ternary Golay code
open-in-new
<h2 id="properties">Properties</h2> <h3>Ternary Golay code</h3> <p>The ternary Golay code consists of 36 = 729 codewords. Its <a href="/facts/Parity_check_matrix/39NSQ0TF">parity check matrix</a> is </p> [ 2 2 2 1 1 0 1 0 0 0 0 2 2 1 2 0 1 0 1 0 0 0 2 1 2 0 2 1 0 0 1 0 0 2 1 0 2 1 2 0 0 0 1 0 2 0 1 1 2 2 0 0 0 0 1 ] . {\displaystyle \left[{\begin{array}{cccccc|ccccc}2&2&2&1&1&0&1&0&0&0&0\\2&2&1&2&0&1&0&1&0&0&0\\2&1&2&0&2&1&0&0&1&0&0\\2&1&0&2&1&2&0&0&0&1&0\\2&0&1&1&2&2&0&0&0&0&1\end{array}}\right].} <p>Any two different codewords differ in at least 5 positions. Every ternary word of length 11 has a <a href="/facts/Hamming_distance/MgdtbYPo">Hamming distance</a> of at most 2 from exactly one codeword. The code can also be constructed as the <a href="/facts/Quadratic_residue_code/NP5uLx7o">quadratic residue code</a> of length 11 over the <a href="/facts/Finite_field/UkMGJo3m">finite field</a> F3 (<i>i.e.,</i> the Galois Field GF(3) ). </p><p>Used in a <a href="/facts/Football_pool/f6t67Ty1">football pool</a> with 11 games, the ternary Golay code corresponds to 729 bets and guarantees exactly one bet with at most 2 wrong outcomes. </p><p>The set of codewords with <a href="/facts/Hamming_weight/dJIW7qg4">Hamming weight</a> 5 is a 3-(11,5,4) <a href="/facts/T-design/R523MRYh">design</a>. </p><p>The <a href="/facts/Generator_matrix/V76ugWLN">generator matrix</a> given by Golay (1949, Table 1.) is </p> [ 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 ] . {\displaystyle \left[{\begin{array}{cccccc|ccccc}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].} <p>The <a href="/facts/Automorphism_group/65vImKwe">automorphism group</a> of the (original) ternary Golay code is the <a href="/facts/Mathieu_group_M11/Ar9AVpaA">Mathieu group <i>M</i>11</a>, which is the smallest of the sporadic simple groups. </p> <h3>Extended ternary Golay code</h3> <p>The <a href="/facts/Enumerator_polynomial/yTeToEMW">complete weight enumerator</a> of the extended ternary Golay code is </p> x 12 + y 12 + z 12 + 22 ( x 6 y 6 + y 6 z 6 + z 6 x 6 ) + 220 ( x 6 y 3 z 3 + y 6 z 3 x 3 + z 6 x 3 y 3 ) . {\displaystyle x^{12}+y^{12}+z^{12}+22\left(x^{6}y^{6}+y^{6}z^{6}+z^{6}x^{6}\right)+220\left(x^{6}y^{3}z^{3}+y^{6}z^{3}x^{3}+z^{6}x^{3}y^{3}\right).} <p>The <a href="/facts/Automorphism_group/65vImKwe">automorphism group</a> of the extended ternary Golay code is 2.<i>M</i>12, where <i>M</i>12 is the <a href="/facts/Mathieu_group_M12/beS7gYGp">Mathieu group <i>M</i>12</a>. </p><p>The extended ternary Golay code can be constructed as the span of the rows of a <a href="/facts/Hadamard_matrix/q56o9lgM">Hadamard matrix</a> of order 12 over the field F3. </p><p>Consider all codewords of the extended code which have just six nonzero digits. The sets of positions at which these nonzero digits occur form the <a href="/facts/Steiner_system/DdakpJpm">Steiner system</a> S(5, 6, 12). </p><p>A <a href="/facts/Generator_matrix/V76ugWLN">generator matrix</a> for the extended ternary Golay code is </p> [ 1 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0 1 0 1 2 2 1 0 0 1 0 0 0 1 1 0 1 2 2 0 0 0 1 0 0 1 2 1 0 1 2 0 0 0 0 1 0 1 2 2 1 0 1 0 0 0 0 0 1 1 1 2 2 1 0 ] = [ I 6 | B ] . {\displaystyle \left[{\begin{array}{cccccc|cccccc}1&0&0&0&0&0&0&1&1&1&1&1\\0&1&0&0&0&0&1&0&1&2&2&1\\0&0&1&0&0&0&1&1&0&1&2&2\\0&0&0&1&0&0&1&2&1&0&1&2\\0&0&0&0&1&0&1&2&2&1&0&1\\0&0&0&0&0&1&1&1&2&2&1&0\\\end{array}}\right]=[I_{6}|B].} <p>The corresponding parity check matrix for this generator matrix is [ − B | I 6 ] T {\displaystyle [-B|I_{6}]^{T}} , where T {\displaystyle T} denotes the <i>transpose</i> of the matrix. </p><p>An alternative generator matrix for this code is </p> [ 1 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0 1 0 1 − 1 − 1 1 0 0 1 0 0 0 1 1 0 1 − 1 − 1 0 0 0 1 0 0 1 − 1 1 0 1 − 1 0 0 0 0 1 0 1 − 1 − 1 1 0 1 0 0 0 0 0 1 1 1 − 1 − 1 1 0 ] = [ I 6 | B a l t ] . {\displaystyle \left[{\begin{array}{rrrrrr|rrrrrr}1&0&0&0&0&0&0&1&1&1&1&1\\0&1&0&0&0&0&1&0&1&-1&-1&1\\0&0&1&0&0&0&1&1&0&1&-1&-1\\0&0&0&1&0&0&1&-1&1&0&1&-1\\0&0&0&0&1&0&1&-1&-1&1&0&1\\0&0&0&0&0&1&1&1&-1&-1&1&0\\\end{array}}\right]=[I_{6}|B_{\mathrm {alt} }].} <p>And its parity check matrix is [ − B a l t | I 6 ] T {\displaystyle [-B_{\mathrm {alt} }|I_{6}]^{T}} . </p><p>The three elements of the underlying finite field are represented here by { 0 , 1 , − 1 } {\displaystyle \{0,1,-1\}} , rather than by { 0 , 1 , 2 } {\displaystyle \{0,1,2\}} . It is also understood that 2 = 1 + 1 = − 1 {\displaystyle 2=1+1=-1} (<i>i.e.,</i> the <a href="/facts/Additive_inverse/n8gKUmCf">additive inverse</a> of 1) and − 2 = ( − 1 ) + ( − 1 ) = 1 {\displaystyle -2=(-1)+(-1)=1} . Products of these finite field elements are identical to those of the integers. Row and column sums are evaluated modulo 3. </p><p>Linear combinations, or <i>vector addition</i>, of the rows of the matrix produces all possible <i>words</i> contained in the code. This is referred to as the <i>span</i> of the rows. The inner product of any two rows of the generator matrix will always sum to zero. These rows, or vectors, are said to be <i>orthogonal</i>. </p><p>The matrix product of the generator and parity-check matrices, [ I 6 | B a l t ] [ − B a l t | I 6 ] T {\displaystyle [I_{6}|B_{\mathrm {alt} }]\,[-B_{\mathrm {alt} }|I_{6}]^{T}} , is the 6 × 6 {\displaystyle 6\times 6} matrix of all zeroes, and by intent. Indeed, this is an example of the very definition of any parity check matrix with respect to its generator matrix. </p> <h2 id="history-and-applications">History and Applications</h2> <p>The ternary Golay code was published by <a href="/facts/Marcel_J._E._Golay/8BJ8gj2T">Golay</a> (1949). It was independently discovered two years earlier by the <a href="/facts/Finland/G5Ak6T91">Finnish</a> <a href="/facts/Football_pool/f6t67Ty1">football pool</a> enthusiast Juhani Virtakallio, who published it in 1947 in issues 27, 28 and 33 of the football magazine <i>Veikkaaja</i>. (Barg 1993, p.25) </p><p>The ternary Golay code has been shown to be useful for an approach to fault-tolerant <a href="/facts/Quantum_computing/nbbcgmvq">quantum computing</a> known as <a href="/facts/Magic_state_distillation/FEPmRRqv">magic state distillation</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Berlekamp%25E2%2580%2593van_Lint%25E2%2580%2593Seidel_graph/rUPKRc8w">Berlekamp–van Lint–Seidel graph</a></li> <li><a href="/facts/Binary_Golay_code/UY04RQEC">Binary Golay code</a></li></ul> <ul><li>Barg, Alexander (1993), "At the dawn of the theory of codes", <i><a href="/facts/The_Mathematical_Intelligencer/tr4EnU3C">The Mathematical Intelligencer</a></i>, 15 (1): 20–26, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF03025254">10.1007/BF03025254</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1199273">1199273</a></li> <li><a href="/facts/Marcel_J._E._Golay/8BJ8gj2T">Golay, M. J. E.</a> (June 1949), <a href="https://web.archive.org/web/20150419200849/http://www.maths.manchester.ac.uk/~ybazlov/code/golay_paper.pdf">"Notes on digital coding"</a> (PDF), <i><a href="/facts/Proceedings_of_the_IRE/qhBDIIQd">Proceedings of the IRE</a></i>, 37: 657, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=4021352">4021352</a>, archived from <a href="https://pierre-hyvernat.apps.math.cnrs.fr/data/Enseignement/2223/info602/TP-Golay/golay_paper.pdf">the original</a> (PDF) on 19 April 2015</li></ul> <h2 id="further-reading">Further reading</h2> <ul><li>Blake, I. F. (1973), <i>Algebraic Coding Theory: History and Development</i>, Stroudsburg, Pennsylvania: Dowden, Hutchinson & Ross</li> <li><a href="/facts/John_Horton_Conway/g3PA1zoK">Conway, J. H.</a>; <a href="/facts/Neil_Sloane/kLWw29Me">Sloane, N. J. A.</a> (1999), <i>Sphere packings, lattices and groups</i>, Grundlehren der Mathematischen Wissenschaften, vol. 290 (3rd ed.), New York: Springer-Verlag, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-1-4757-6568-7">10.1007/978-1-4757-6568-7</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-98585-9, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1662447">1662447</a></li> <li><a href="/facts/Robert_Griess/rW17QTTh">Griess, Robert L. Jr.</a> (1998), <i>Twelve Sporadic Groups</i>, Springer Monographs in Mathematics, Berlin: Springer-Verlag, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-662-03516-0">10.1007/978-3-662-03516-0</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-540-62778-2, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1707296">1707296</a></li> <li><a href="/facts/G%25C3%25A9rard_Denis_Cohen/6fw3l3vr">Cohen, Gérard</a>; Honkala, Iiro; Litsyn, Simon; Lobstein, Antoine (1997), <i>Covering codes</i>, North-Holland Mathematical Library, vol. 54, Amsterdam: North-Holland, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-444-82511-8, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1453577">1453577</a></li> <li>Thompson, Thomas M. (1983), <i>From Error Correcting Codes through Sphere Packings to Simple Groups</i>, Carus Mathematical Monographs, vol. 21, Washington, DC: Mathematical Association of America, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-88385-023-0, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0749038">0749038</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Prakash, Shiroman (September 2020). "Magic state distillation with the ternary Golay code". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 476 (2241): 20200187. arXiv:2003.02717. doi:10.1098/rspa.2020.0187. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> </ol>