Namespaces
Variants
Actions

Difference between revisions of "Golay code"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (tex encoded by computer)
Line 1: Line 1:
From a purely mathematical point of view, the Golay codes are the most interesting codes constructed as yet (1996). The binary Golay code <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g1101601.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g1101602.png" />-dimensional subspace of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g1101603.png" /> with the property that any two vectors (i.e., words) differ in at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g1101604.png" /> positions (they have distance <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g1101605.png" />). In coding terminology, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g1101606.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g1101607.png" /> binary code, i.e., a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g1101608.png" />-error-correcting code (cf. [[Error-correcting code|Error-correcting code]]). Similarly, the ternary Golay code <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g1101609.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016010.png" /> ternary code. It was shown by A. Tietäväinen and J.H. van Lint (see [[#References|[a3]]]) that the Golay codes are the only non-trivial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016011.png" />-error-correcting perfect codes with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016012.png" /> over any alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016013.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016014.png" /> is a prime power. A perfect <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016016.png" />-error-correcting code is a subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016017.png" /> such that every vector in the space has distance at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016018.png" /> to a unique codeword.
+
<!--
 +
g1101601.png
 +
$#A+1 = 72 n = 0
 +
$#C+1 = 72 : ~/encyclopedia/old_files/data/G110/G.1100160 Golay code
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
An extension of a code <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016019.png" /> of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016020.png" /> is the set of words of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016021.png" /> obtained by adjoining an extra coordinate to all the words of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016022.png" /> in such a way that the sum of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016023.png" /> coordinates is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016024.png" />. The extended codes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016026.png" /> are of interest in group theory because their automorphism groups are the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016027.png" />-transitive Mathieu groups <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016028.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016029.png" /> (cf. also [[Mathieu group|Mathieu group]]).
+
{{TEX|auto}}
 +
{{TEX|done}}
  
For design theory (cf. also [[Design with mutually orthogonal resolutions|Design with mutually orthogonal resolutions]]; [[Block design|Block design]]), the Golay codes are important for the following reason. The words of weight (i.e., number of non-zero coordinates) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016030.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016031.png" /> are the blocks of the (unique) [[Steiner system|Steiner system]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016032.png" />. Similarly, the words of weight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016033.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016034.png" /> support the blocks of the (unique) Steiner system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016035.png" />.
+
From a purely mathematical point of view, the Golay codes are the most interesting codes constructed as yet (1996). The binary Golay code  $  {\mathcal G} _ {23 }  $
 +
is a  $  12 $-
 +
dimensional subspace of  $  \mathbf F _ {2} ^ {23 } $
 +
with the property that any two vectors (i.e., words) differ in at least  $  7 $
 +
positions (they have distance  $  d = 7 $).
 +
In coding terminology,  $  {\mathcal G} _ {23 }  $
 +
is a  $  [ 23,12,7 ] $
 +
binary code, i.e., a  $  3 $-
 +
error-correcting code (cf. [[Error-correcting code|Error-correcting code]]). Similarly, the ternary Golay code  $  {\mathcal G} _ {11 }  $
 +
is a  $  [ 11,6,5 ] $
 +
ternary code. It was shown by A. Tietäväinen and J.H. van Lint (see [[#References|[a3]]]) that the Golay codes are the only non-trivial  $  e $-
 +
error-correcting perfect codes with  $  e > 1 $
 +
over any alphabet  $  Q $
 +
for which  $  | Q | $
 +
is a prime power. A perfect  $  e $-
 +
error-correcting code is a subset of  $  Q  ^ {n} $
 +
such that every vector in the space has distance at most  $  e $
 +
to a unique codeword.
 +
 
 +
An extension of a code  $  C $
 +
of length  $  n $
 +
is the set of words of length  $  n + 1 $
 +
obtained by adjoining an extra coordinate to all the words of  $  C $
 +
in such a way that the sum of the  $  n + 1 $
 +
coordinates is  $  0 $.
 +
The extended codes  $  {\mathcal G} _ {24 }  $
 +
and  $  {\mathcal G} _ {12 }  $
 +
are of interest in group theory because their automorphism groups are the  $  5 $-
 +
transitive Mathieu groups  $  M _ {24 }  $
 +
and  $  M _ {12 }  $(
 +
cf. also [[Mathieu group|Mathieu group]]).
 +
 
 +
For design theory (cf. also [[Design with mutually orthogonal resolutions|Design with mutually orthogonal resolutions]]; [[Block design|Block design]]), the Golay codes are important for the following reason. The words of weight (i.e., number of non-zero coordinates) $  8 $
 +
in $  {\mathcal G} _ {24 }  $
 +
are the blocks of the (unique) [[Steiner system|Steiner system]] $  S ( 5,8,24 ) $.  
 +
Similarly, the words of weight $  6 $
 +
in $  {\mathcal G} _ {12 }  $
 +
support the blocks of the (unique) Steiner system $  S ( 5,6,12 ) $.
  
 
For each of the codes, several constructions are known. E.g.,
 
For each of the codes, several constructions are known. E.g.,
  
1) Make a list of the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016036.png" /> written binary as vectors in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016037.png" />. Delete each vector that has distance less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016038.png" /> to a previous vector that has not been deleted. At the end of this procedure, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016039.png" /> vectors will remain. They form a linear code, in fact <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110160/g11016040.png" />.
+
1) Make a list of the numbers 0,1 \dots 2 ^ {24 } - 1 $
 +
written binary as vectors in $  \mathbf F _ {2} ^ {24 } $.  
 +
Delete each vector that has distance less than $  8 $
 +
to a previous vector that has not been deleted. At the end of this procedure, $  4096 $
 +
vectors will remain. They form a linear code, in fact $  {\mathcal G} _ {24 }  $.
  
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 $  \mathbf F _ {2} ^ {23 } $
 +
and $  \mathbf F _ {3} ^ {11 } $,  
 +
consider the codes of length $  n = 23 $,  
 +
respectively $  n = 11 $,  
 +
generated by the vectors $  {\vec{c} } _ {i} $(
 +
$  1 \leq  i \leq  n $)  
 +
for which $  c _ {i,j }  = 1 $
 +
if $  j - i $
 +
is a non-zero square and 0 $
 +
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 $  ( 11 \times 11 ) $-[[
 +
circulant matrix]] with top row $  ( 01000111011 ) $.  
 +
This is the incidence matrix of the unique $  2 $-  
 +
$  ( 11,6,3 ) $-
 +
design. Form $  P $
 +
by bordering this matrix with a column of $  1 $'
 +
s in front and a row of $  1 $'
 +
s on top, with a 0 $
 +
in the upper left-hand corner (cf. [[Bordering method|Bordering method]]). Then adjoin $  I _ {12 }  $
 +
in front of $  P $.  
 +
One obtains a $  ( 12 \times 24 ) $-
 +
matrix $  G $
 +
in which every row has eight $  1 $'
 +
s (except the top row, which has $  12 $).  
 +
The rows of $  G $
 +
generate $  {\mathcal G} _ {24 }  $.
  
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 $  ( 5 \times 5 ) $-
 +
circulant with top row $  ( 0,1, - 1, - 1,1 ) $
 +
and border it on top with a row of $  1 $'
 +
s. To this, adjoin $  I _ {6} $
 +
in front to form a $  ( 6 \times 11 ) $-
 +
matrix $  G $.  
 +
The rows of $  G $
 +
generate the $  [ 11,6,5 ] $
 +
ternary Golay code.
  
 
For other constructions and more theory of these codes, see the references.
 
For other constructions and more theory of these codes, see the references.

Revision as of 19:42, 5 June 2020


From a purely mathematical point of view, the Golay codes are the most interesting codes constructed as yet (1996). The binary Golay code $ {\mathcal G} _ {23 } $ is a $ 12 $- dimensional subspace of $ \mathbf F _ {2} ^ {23 } $ with the property that any two vectors (i.e., words) differ in at least $ 7 $ positions (they have distance $ d = 7 $). In coding terminology, $ {\mathcal G} _ {23 } $ is a $ [ 23,12,7 ] $ binary code, i.e., a $ 3 $- error-correcting code (cf. Error-correcting code). Similarly, the ternary Golay code $ {\mathcal G} _ {11 } $ is a $ [ 11,6,5 ] $ 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 $ e $- error-correcting perfect codes with $ e > 1 $ over any alphabet $ Q $ for which $ | Q | $ is a prime power. A perfect $ e $- error-correcting code is a subset of $ Q ^ {n} $ such that every vector in the space has distance at most $ e $ to a unique codeword.

An extension of a code $ C $ of length $ n $ is the set of words of length $ n + 1 $ obtained by adjoining an extra coordinate to all the words of $ C $ in such a way that the sum of the $ n + 1 $ coordinates is $ 0 $. The extended codes $ {\mathcal G} _ {24 } $ and $ {\mathcal G} _ {12 } $ are of interest in group theory because their automorphism groups are the $ 5 $- transitive Mathieu groups $ M _ {24 } $ and $ M _ {12 } $( 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) $ 8 $ in $ {\mathcal G} _ {24 } $ are the blocks of the (unique) Steiner system $ S ( 5,8,24 ) $. Similarly, the words of weight $ 6 $ in $ {\mathcal G} _ {12 } $ support the blocks of the (unique) Steiner system $ S ( 5,6,12 ) $.

For each of the codes, several constructions are known. E.g.,

1) Make a list of the numbers $ 0,1 \dots 2 ^ {24 } - 1 $ written binary as vectors in $ \mathbf F _ {2} ^ {24 } $. Delete each vector that has distance less than $ 8 $ to a previous vector that has not been deleted. At the end of this procedure, $ 4096 $ vectors will remain. They form a linear code, in fact $ {\mathcal G} _ {24 } $.

2) In the spaces $ \mathbf F _ {2} ^ {23 } $ and $ \mathbf F _ {3} ^ {11 } $, consider the codes of length $ n = 23 $, respectively $ n = 11 $, generated by the vectors $ {\vec{c} } _ {i} $( $ 1 \leq i \leq n $) for which $ c _ {i,j } = 1 $ if $ j - i $ is a non-zero square and $ 0 $ otherwise. One thus obtains the binary and the ternary Golay code.

3) Consider the $ ( 11 \times 11 ) $-[[ circulant matrix]] with top row $ ( 01000111011 ) $. This is the incidence matrix of the unique $ 2 $- $ ( 11,6,3 ) $- design. Form $ P $ by bordering this matrix with a column of $ 1 $' s in front and a row of $ 1 $' s on top, with a $ 0 $ in the upper left-hand corner (cf. Bordering method). Then adjoin $ I _ {12 } $ in front of $ P $. One obtains a $ ( 12 \times 24 ) $- matrix $ G $ in which every row has eight $ 1 $' s (except the top row, which has $ 12 $). The rows of $ G $ generate $ {\mathcal G} _ {24 } $.

4) As in 3), form a $ ( 5 \times 5 ) $- circulant with top row $ ( 0,1, - 1, - 1,1 ) $ and border it on top with a row of $ 1 $' s. To this, adjoin $ I _ {6} $ in front to form a $ ( 6 \times 11 ) $- matrix $ G $. The rows of $ G $ generate the $ [ 11,6,5 ] $ 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)
How to Cite This Entry:
Golay code. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Golay_code&oldid=47103
This article was adapted from an original article by J.H. van Lint (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article