Ternary Golay code

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Perfect ternary Golay code
Named after Marcel J. E. Golay
Classification
Type Linear block code
Parameters
Block length 11
Message length 6
Rate 6/11 ~ 0.545
Distance 5
Alphabet size 3
Notation [11,6,5]_3-code
Extended ternary Golay code
Named after Marcel J. E. Golay
Classification
Type Linear block code
Parameters
Block length 12
Message length 6
Rate 6/12 = 0.5
Distance 6
Alphabet size 3
Notation [12,6,6]_3-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 [11, 6, 5]_3-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 [12, 6, 6] linear code obtained by adding a zero-sum check digit to the [11, 6, 5] code. In finite group theory, the extended ternary Golay code is sometimes referred to as the ternary Golay code.[citation needed]

Properties[edit]

Ternary Golay code[edit]

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



\left[
\begin{array}{ccccccccccc}

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{array}
\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 F3.

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.

Extended ternary Golay code[edit]

The complete weight enumerator of the extended ternary Golay code is

x^{12}+y^{12}+z^{12}+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.M12, where M12 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 F3.

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

History[edit]

The ternary Golay code was first introduced by the Finnish football pool enthusiast Juhani Virtakallio, who published it in 1947 in issues 27, 28 and 33 of the football magazine Veikkaaja. (Barg 1993, p.25) It was independently rediscovered by Golay (1949).

See also[edit]

References[edit]