In
coding theory
Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are stud ...
, the ternary Golay codes are two closely related
error-correcting code
In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
s.
The code generally known simply as the ternary Golay code is an
-code, that is, it is a
linear code In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although turbo codes can be seen as ...
over a
ternary
Ternary (from Latin ''ternarius'') or trinary is an adjective meaning "composed of three items". It can refer to:
Mathematics and logic
* Ternary numeral system, a base-3 counting system
** Balanced ternary, a positional numeral system, useful ...
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
In mathematics and computer science, in the field of coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the sphere-packing bound or the volume bound from an interpretation in terms of pack ...
.
The extended ternary Golay code is a
2, 6, 6linear code In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although turbo codes can be seen as ...
obtained by adding a zero-sum
check digit
A check digit is a form of redundancy check used for error detection on identification numbers, such as bank account numbers, which are used in an application where they will at least sometimes be input manually. It is analogous to a binary parity ...
to the
1, 6, 5
Onekama ( ) is a village in Manistee County in the U.S. state of Michigan. The population was 411 at the 2010 census. The village is located on the shores of Portage Lake and is surrounded by Onekama Township. The town's name is derived from "On ...
code.
In finite
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
, 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
6 = 729 codewords.
Its
parity check matrix In coding theory, a parity-check matrix of a linear block code ''C'' is a matrix which describes the linear relations that the components of a codeword must satisfy. It can be used to decide whether a particular vector is a codeword and is also used ...
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
A quadratic residue code is a type of cyclic code.
Examples
Examples of quadratic
residue codes include the (7,4) Hamming code
over GF(2), the (23,12) binary Golay code
over GF(2) and the (11,6) ternary Golay code
over GF(3).
Constructions
There ...
of length 11 over the
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
F
3 (''i.e.,'' the Galois Field
GF(3) ).
Used in a
football pool
In the United Kingdom, the football pools, often referred to as "the pools", is a betting pool based on predicting the outcome of association football matches taking place in the coming week. The pools are typically cheap to enter, and may encou ...
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
A design is a plan or specification for the construction of an object or system or for the implementation of an activity or process or the result of that plan or specification in the form of a prototype, product, or process. The verb ''to design'' ...
.
The
generator matrix
In coding theory, a generator matrix is a matrix whose rows form a basis for a linear code. The codewords are all of the linear combinations of the rows of this matrix, that is, the linear code is the row space of its generator matrix.
Terminol ...
given by Golay (1949, Table 1.) is
:
The
automorphism group
In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...
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
:
The
automorphism group
In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...
of the extended ternary Golay code is 2.''M''
12, where ''M''
12 is the
Mathieu group M12
In the area of modern algebra known as group theory, the Mathieu group ''M12'' is a sporadic simple group of order
: 12111098 = 2633511 = 95040.
History and properties
''M12'' is one of the 26 sporadic groups and was introduc ...
.
The extended ternary Golay code can be constructed as the span of the rows of a
Hadamard matrix
In mathematics, a Hadamard matrix, named after the French mathematician Jacques Hadamard, is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal. In geometric terms, this means that each pair of rows ...
of order 12 over the field F
3.
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
250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line.
In combinatorial mathematics, a Steiner system (named after Jakob Steiner) ...
S(5, 6, 12).
A
generator matrix
In coding theory, a generator matrix is a matrix whose rows form a basis for a linear code. The codewords are all of the linear combinations of the rows of this matrix, that is, the linear code is the row space of its generator matrix.
Terminol ...
for the extended ternary Golay code is
:
The corresponding parity check matrix for this generator matrix is
, where
denotes the ''transpose'' of the matrix.
An alternative generator matrix for this code is
:
And its parity check matrix is
.
The three elements of the underlying finite field are represented here by
, rather than by
.
It is also understood that
(''i.e.,'' the additive inverse of 1) and
. 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,
, is the
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
Finnish may refer to:
* Something or someone from, or related to Finland
* Culture of Finland
* Finnish people or Finns, the primary ethnic group in Finland
* Finnish language, the national language of the Finnish people
* Finnish cuisine
See also ...
football pool enthusiast
Juhani Virtakallio Juhani is a common Finnish male given name and Arabic surname.
Given name
* Juhani Aaltonen (born 1935), Finnish jazz saxophonist and flautist
* Juhani Aho
* Juhani Kaskeala
* Juhani Komulainen
* Juhani Kumpulainen
* Juhani Lahtinen
* Juhani ...
, who published it in 1947 in issues 27, 28 and 33 of the football
magazine
A magazine is a periodical publication, generally published on a regular schedule (often weekly or monthly), containing a variety of content. They are generally financed by advertising, purchase price, prepaid subscriptions, or by a combinatio ...
''
Veikkaaja''.
The ternary Golay code has been shown to be useful for an approach to fault-tolerant
quantum computing
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
known as
magic state distillation
Magic state distillation is a method for creating more accurate quantum states from multiple noisy ones, which is important for building fault tolerant quantum computers. It has also been linked to quantum contextuality, a concept thought to co ...
.
See also
*
Berlekamp–van Lint–Seidel graph
In graph theory, the Berlekamp–Van Lint–Seidel graph is a locally linear strongly regular graph with parameters (243,22,1,2). This means that it has 243 vertices, 22 edges per vertex (for a total of 2673 edges), exactly one shared neighbor per ...
*
Binary Golay code
In mathematics and electronics engineering, a binary Golay code is a type of linear error-correcting code used in digital communications. The binary Golay code, along with the ternary Golay code, has a particularly deep and interesting connection ...
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元ゴレイ符号