Ternary Golay Code

In coding theory, the ternary Golay codes are two closely related error-correcting codes.
The code generally known simply as the ternary Golay code is an 1, 6, 53-code, that is, it is a linear code over a ternary alphabet; the relative distance of the code is as large as it possibly can be for a ternary code, and hence, the ternary Golay code is a perfect code.
The extended ternary Golay code is a 2, 6, 6linear code obtained by adding a zero-sum check digit to the 1, 6, 5code.
In finite group theory, the extended ternary Golay code is sometimes referred to as the ternary Golay code.

Properties

Ternary Golay code

The ternary Golay code consists of 3⁶ = 729 codewords.
Its parity check matrix is
:$\left[ \begin 1 & 1 & 1 & 2 & 2 & 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 1 & 2 & 1 & 0 & 2 & 0 & 1 & 0 & 0 & 0\\ 1 & 2 & 1 & 0 & 1 & 2 & 0 & 0 & 1 & 0 & 0\\ 1 & 2 & 0 & 1 & 2 & 1 & 0 & 0 & 0 & 1 & 0\\ 1 & 0 & 2 & 2 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \end \right].$
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₃ (''i.e.,'' the Galois Field GF(3) ).

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.

The set of codewords with Hamming weight 5 is a 3-(11,5,4) design.

The generator matrix given by Golay (1949, Table 1.) is

:$\left[ \begin 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 \right] = [X, Y].$

The automorphism group of the (original) ternary Golay code is the Mathieu group M11, which is the smallest of the sporadic simple groups.

Extended ternary Golay code

The complete weight enumerator of the extended ternary Golay code is
:$x^+y^+z^+22\left(x^6y^6+y^6z^6+z^6x^6\right)+220\left(x^6y^3z^3+y^6z^3x^3+z^6x^3y^3\right).$

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

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).

A generator matrix for the extended ternary Golay code is

:$\left[ \begin 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 \right] = [I_6, B].$

The corresponding parity check matrix for this generator matrix is $[-B, I_6]^T$, where $T$ denotes the ''transpose'' of the matrix.

An alternative generator matrix for this code is

:$\left[ \begin 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 \right] = [I_6, B_].$

And its parity check matrix is I_6T.

The three elements of the underlying finite field are represented here by $\$, rather than by $\$.
It is also understood that $2=1+1=-1$ (''i.e.,'' the additive inverse of 1) and $-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.

Linear combinations, or ''vector addition'', of the rows of the matrix
produces all possible ''words'' contained in the code. This is referred to as the ''span'' 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 ''orthogonal''.

The matrix product of the generator and parity-check matrices,
B_, I_6T, is the $6\times6$ 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.

History and Applications

The ternary Golay code was published by . It was independently discovered two years earlier by the Finnish football pool enthusiast Juhani Virtakallio, who published it in 1947 in issues 27, 28 and 33 of the football magazine '' Veikkaaja''.

The ternary Golay code has been shown to be useful for an approach to fault-tolerant quantum computing known as magic state distillation.

See also

* Berlekamp–van Lint–Seidel graph
* Binary Golay code

References

*
*

Further reading

*
*
*
*
*{{citation
, last = Thompson , first = Thomas M.
, isbn = 0-88385-023-0
, mr = 749038
, publisher = Mathematical Association of America , location = Washington, DC
, series = Carus Mathematical Monographs
, title = From Error Correcting Codes through Sphere Packings to Simple Groups
, volume = 21
, year = 1983

Coding theory
Finite fields

ja:3元ゴレイ符号