Difference between revisions of "Golay code"
(Importing text file) |
m (link) |
||
Line 11: | Line 11: | ||
2) In the spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016041.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016042.png" />, consider the codes of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016043.png" />, respectively <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016044.png" />, generated by the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016045.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016046.png" />) for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016047.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016048.png" /> is a non-zero square and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016049.png" /> otherwise. One thus obtains the binary and the ternary Golay code. | 2) In the spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016041.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016042.png" />, consider the codes of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016043.png" />, respectively <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016044.png" />, generated by the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016045.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016046.png" />) for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016047.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016048.png" /> is a non-zero square and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016049.png" /> otherwise. One thus obtains the binary and the ternary Golay code. | ||
− | 3) Consider the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016050.png" />-circulant matrix with top row <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016051.png" />. This is the incidence matrix of the unique <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016052.png" />- <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016053.png" />-design. Form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016054.png" /> by bordering this matrix with a column of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016055.png" />'s in front and a row of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016056.png" />'s on top, with a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016057.png" /> in the upper left-hand corner (cf. [[Bordering method|Bordering method]]). Then adjoin <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016058.png" /> in front of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016059.png" />. One obtains a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016060.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016061.png" /> in which every row has eight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016062.png" />'s (except the top row, which has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016063.png" />). The rows of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016064.png" /> generate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016065.png" />. | + | 3) Consider the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016050.png" />-[[circulant matrix]] with top row <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016051.png" />. This is the incidence matrix of the unique <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016052.png" />- <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016053.png" />-design. Form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016054.png" /> by bordering this matrix with a column of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016055.png" />'s in front and a row of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016056.png" />'s on top, with a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016057.png" /> in the upper left-hand corner (cf. [[Bordering method|Bordering method]]). Then adjoin <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016058.png" /> in front of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016059.png" />. One obtains a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016060.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016061.png" /> in which every row has eight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016062.png" />'s (except the top row, which has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016063.png" />). The rows of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016064.png" /> generate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016065.png" />. |
4) As in 3), form a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016066.png" />-circulant with top row <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016067.png" /> and border it on top with a row of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016068.png" />'s. To this, adjoin <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016069.png" /> in front to form a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016070.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016071.png" />. The rows of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016072.png" /> generate the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016073.png" /> ternary Golay code. | 4) As in 3), form a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016066.png" />-circulant with top row <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016067.png" /> and border it on top with a row of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016068.png" />'s. To this, adjoin <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016069.png" /> in front to form a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016070.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016071.png" />. The rows of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016072.png" /> generate the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016073.png" /> ternary Golay code. |
Revision as of 16:25, 16 January 2016
From a purely mathematical point of view, the Golay codes are the most interesting codes constructed as yet (1996). The binary Golay code is a
-dimensional subspace of
with the property that any two vectors (i.e., words) differ in at least
positions (they have distance
). In coding terminology,
is a
binary code, i.e., a
-error-correcting code (cf. Error-correcting code). Similarly, the ternary Golay code
is a
ternary code. It was shown by A. Tietäväinen and J.H. van Lint (see [a3]) that the Golay codes are the only non-trivial
-error-correcting perfect codes with
over any alphabet
for which
is a prime power. A perfect
-error-correcting code is a subset of
such that every vector in the space has distance at most
to a unique codeword.
An extension of a code of length
is the set of words of length
obtained by adjoining an extra coordinate to all the words of
in such a way that the sum of the
coordinates is
. The extended codes
and
are of interest in group theory because their automorphism groups are the
-transitive Mathieu groups
and
(cf. also Mathieu group).
For design theory (cf. also Design with mutually orthogonal resolutions; Block design), the Golay codes are important for the following reason. The words of weight (i.e., number of non-zero coordinates) in
are the blocks of the (unique) Steiner system
. Similarly, the words of weight
in
support the blocks of the (unique) Steiner system
.
For each of the codes, several constructions are known. E.g.,
1) Make a list of the numbers written binary as vectors in
. Delete each vector that has distance less than
to a previous vector that has not been deleted. At the end of this procedure,
vectors will remain. They form a linear code, in fact
.
2) In the spaces and
, consider the codes of length
, respectively
, generated by the vectors
(
) for which
if
is a non-zero square and
otherwise. One thus obtains the binary and the ternary Golay code.
3) Consider the -circulant matrix with top row
. This is the incidence matrix of the unique
-
-design. Form
by bordering this matrix with a column of
's in front and a row of
's on top, with a
in the upper left-hand corner (cf. Bordering method). Then adjoin
in front of
. One obtains a
-matrix
in which every row has eight
's (except the top row, which has
). The rows of
generate
.
4) As in 3), form a -circulant with top row
and border it on top with a row of
's. To this, adjoin
in front to form a
-matrix
. The rows of
generate the
ternary Golay code.
For other constructions and more theory of these codes, see the references.
M.J.E. Golay (1902– 1989) was a Swiss physicist who worked in many different fields. He is known for his work on infrared spectroscopy and the invention of the capillary column, but to mathematicians mainly for his discovery of the two Golay codes.
References
[a1] | A.E. Brouwer, "Block designs" R. Graham (ed.) M. Grötschel (ed.) L. Lovász (ed.) , Handbook of Combinatorics , Elsevier (1995) pp. Chapt. 14 |
[a2] | P.J. Cameron, J.H. van Lint, "Designs, graphs, codes and their links" , Cambridge Univ. Press (1991) |
[a3] | J.H. van Lint, "Introduction to coding theory" , Springer (1992) |
[a4] | J.H. van Lint, R.M. Wilson, "A course in combinatorics" , Cambridge Univ. Press (1992) |
[a5] | F.J. MacWilliams, N.J.A. Sloane, "The theory of error-correcting codes" , North-Holland (1977) |
Golay code. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Golay_code&oldid=37539