Ternary Golay code

From Wikipedia, the free encyclopedia

There are two closely related error-correcting codes known as ternary Golay codes. The code generally known simply as the ternary Golay code is a perfect (11, 6, 5) ternary linear code; the extended ternary Golay code is a (12, 6, 6) linear code obtained by adding a zero-sum check digit to the (11, 6, 5) code.

Contents 1 Properties 1.1 Ternary Golay code 1.2 Extended ternary Golay code 2 History 3 See also 4 References

[edit] Properties

[edit] Ternary Golay code

The ternary Golay code consists of 3⁶ = 729 codewords. Its parity check matrix is

Any two different codewords differ in at least 5 positions. Every ternary word of length 11 has a Hamming distance of at most 2 from exactly one codeword. The code can also be constructed as the quadratic residue code of length 11 over the finite field F₃.

Used in a football pool with 11 games, the ternary Golay code corresponds to 729 bets and guarantees exactly one bet with at most 2 wrong outcomes.

[edit] Extended ternary Golay code

The complete weight enumerator of the extended ternary Golay code is

.

The automorphism group of the extended ternary Golay code is 2.M₁₂, where M₁₂ is a Mathieu group.

The extended ternary Golay code can be constructed as the span of the rows of a Hadamard matrix of order 12 over the field F₃.

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 Steiner system S(5, 6, 12).

[edit] History

The ternary Golay code has been constructed by Marcel J. E. Golay. He published it in a very short correspondence in 1949. Independently and slightly earlier the same code has also been developed by the Finnish football pool enthusiast Juhani Virtakallio who published it in 1947.

[edit] See also

• Binary Golay code

[edit] References

• M.J.E. Golay, Notes on digital coding, Proceedings of the I.R.E. 37 (1949) 657
• I.F. Blake (ed.), Algebraic Coding Theory: History and Development, Dowden, Hutchinson & Ross, Stroudsburg 1973
• J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, Springer, New York, Berlin, Heidelberg, 1988.
• Robert L. Griess, Twelve Sporadic Groups, Springer, 1998.
• G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering Codes, Elsevier (1997) ISBN 0-444-82511-8
• Th. M. Thompson, From Error Correcting Codes through Sphere Packings to Simple Groups, The Mathematical Association of America 1983, ISBN 0-88385-037-0