Namespaces
Variants
Actions

Difference between revisions of "Kerdock and Preparata codes"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (tex encoded by computer)
Line 1: Line 1:
 +
<!--
 +
k1100801.png
 +
$#A+1 = 35 n = 3
 +
$#C+1 = 35 : ~/encyclopedia/old_files/data/K110/K.1100080 Kerdock and Preparata codes
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
{{MSC|}}
 
{{MSC|}}
  
A most famous relation in coding theory is a discrete avatar of the [[Fourier transform]] which relates the weight enumerator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k1100801.png" /> of a linear code <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k1100802.png" /> and the weight enumerator of its dual <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k1100803.png" /> with respect to the standard scalar product, namely
+
A most famous relation in coding theory is a discrete avatar of the [[Fourier transform]] which relates the weight enumerator $  W _ {C} $
 +
of a linear code $  C $
 +
and the weight enumerator of its dual $  C  ^  \perp  $
 +
with respect to the standard scalar product, namely
 +
 
 +
$$
 +
W _ {C  ^  \perp  } ( x,y ) = {
 +
\frac{1}{\left | C \right | }
 +
} W _ {C} ( x + y,x - y ) .
 +
$$
 +
 
 +
(Cf. [[MacWilliams identities|MacWilliams identities]].) A simple example of a dual pair of codes is the [[Hamming code]]  $  H _ {m} $,
 +
a (big)  $  [ n = 2  ^ {m} ,n - m - 1,4 ] $
 +
code whose dual is the (small) first-order [[Reed–Muller code]]  $  R _ {m} $.
 +
The matrix
 +
 
 +
$$
 +
\left (
 +
 
 +
\begin{array}{ccccccc}
 +
1  & 1  & 1  & 1  & 1  &\dots  & 1  \\
 +
0  & 1  &\alpha  &\alpha  ^ {2}  &\alpha  ^ {3}  &\dots  &\alpha ^ {n - 1 }  \\
 +
\end{array}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k1100804.png" /></td> </tr></table>
+
\right ) ,
 +
$$
  
(Cf. [[MacWilliams identities|MacWilliams identities]].) A simple example of a dual pair of codes is the [[Hamming code]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k1100805.png" />, a (big) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k1100806.png" /> code whose dual is the (small) first-order [[Reed–Muller code]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k1100807.png" />. The matrix
+
where  $  n = 2  ^ {m} - 1 $
 +
and  $  \alpha $
 +
is a root of  $  {\overline{f}\; } ( x ) $,
 +
is both a generator matrix for  $  R _ {m} $
 +
and a parity check matrix for  $  H _ {m} $.  
 +
The small code $  R _ {m} $
 +
has the simple weight distribution
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k1100808.png" /></td> </tr></table>
+
$$
 +
W _ {R _ {m}  } ( x,y ) = x  ^ {n} + y  ^ {n} + ( 2n - 2 ) ( xy ) ^ {n/2 } .
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k1100809.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008010.png" /> is a root of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008011.png" />, is both a generator matrix for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008012.png" /> and a parity check matrix for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008013.png" />. The small code <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008014.png" /> has the simple weight distribution
+
The MacWilliams formula now gives an explicit expression for $  W _ {H _ {m}  } $
 +
which would be cumbersome to obtain directly.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008015.png" /></td> </tr></table>
+
There is no Fourier transform without Abelian groups and therefore there is no MacWilliams formula for non-linear codes. The discovery first of the  $  ( 16,256,6 ) $[[
 +
Nordstrom–Robinson code]] in 1967, non-linear and still formally self-dual for the MacWilliams relation, followed in 1968 and 1972 [[#References|[a8]]] by the discovery of two infinite families of non-linear codes, the [[Preparata code]]s and Kerdock codes, respectively, whose weight enumerators are MacWilliams dual of each other, were until [[#References|[a4]]] an unexplained phenomenon. The unsuccessful efforts of many distinguished researchers on this notoriously difficult problem [[#References|[a8]]] led one of them to declare [[#References|[a5]]] that it was  "merely a coincidence" .
  
The MacWilliams formula now gives an explicit expression for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008016.png" /> which would be cumbersome to obtain directly.
+
A well-known trick in modulation theory to address the  $  4 $-
 +
PSK constellation consists of using a (very simple) case of the Gray mapping. This is a mapping from  $  \mathbf Z _ {4} $
 +
to $  { \mathop{\rm GF} } ( 2 )  ^ {2} $
 +
defined by
  
There is no Fourier transform without Abelian groups and therefore there is no MacWilliams formula for non-linear codes. The discovery first of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008017.png" /> [[Nordstrom–Robinson code]] in 1967, non-linear and still formally self-dual for the MacWilliams relation, followed in 1968 and 1972 [[#References|[a8]]] by the discovery of two infinite families of non-linear codes, the [[Preparata code]]s and Kerdock codes, respectively, whose weight enumerators are MacWilliams dual of each other, were until [[#References|[a4]]] an unexplained phenomenon. The unsuccessful efforts of many distinguished researchers on this notoriously difficult problem [[#References|[a8]]] led one of them to declare [[#References|[a5]]] that it was  "merely a coincidence" .
+
$$
 +
0 \rightarrow 00, 1 \rightarrow 01, 2 \rightarrow 11, 3 \rightarrow 10,
 +
$$
  
A well-known trick in modulation theory to address the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008019.png" />-PSK constellation consists of using a (very simple) case of the Gray mapping. This is a mapping from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008020.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008021.png" /> defined by
+
and extended to a mapping from  $  \mathbf Z _ {4}  ^ {n} $
 +
to  $  { \mathop{\rm GF} } ( 2 ) ^ {2n } $
 +
in the natural way. The key property is that the mapping $  \phi $
 +
from $  \mathbf Z _ {4}  ^ {n} $
 +
equipped with the [[Lee distance]] to  $  { \mathop{\rm GF} } ( 2 ) ^ {2n } $
 +
equipped with the Hamming distance is an [[Isometric mapping|isometric mapping]] of metric spaces. The trace parametrization of quaternary  $  M $-
 +
sequences can be used to show that the Kerdock code as defined in [[#References|[a8]]], p. 1107, is essentially the cyclic code associated to construction  $  A $
 +
of [[#References|[a1]]], p. 458, and the construction of [[#References|[a9]]]. In particular, if  $  \xi $
 +
denotes a primitive root of  $  n $
 +
in a suitable [[Galois ring|Galois ring]], [[#References|[a7]]], then the matrix
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008022.png" /></td> </tr></table>
+
$$
 +
\left (
  
and extended to a mapping from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008023.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008024.png" /> in the natural way. The key property is that the mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008025.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008026.png" /> equipped with the [[Lee distance]] to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008027.png" /> equipped with the Hamming distance is an [[Isometric mapping|isometric mapping]] of metric spaces. The trace parametrization of quaternary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008028.png" />-sequences can be used to show that the Kerdock code as defined in [[#References|[a8]]], p. 1107, is essentially the cyclic code associated to construction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008029.png" /> of [[#References|[a1]]], p. 458, and the construction of [[#References|[a9]]]. In particular, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008030.png" /> denotes a primitive root of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008031.png" /> in a suitable [[Galois ring|Galois ring]], [[#References|[a7]]], then the matrix
+
\begin{array}{ccccccc}
 +
1  & 1  & 1  & 1  & 1  &\dots  & 1  \\
 +
0 & 1  &\xi  &\xi  ^ {2}  &\xi  ^ {3}  &\dots  &\xi ^ {n - 1 }  \\
 +
\end{array}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008032.png" /></td> </tr></table>
+
\right )
 +
$$
  
(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008033.png" />, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008034.png" /> odd) is both a generator matrix for the Kerdock code and a parity check matrix for the  "Preparata"  code. One sees that the Kerdock and Preparata codes are quaternary analogues of the first-order [[Reed–Muller code]] and of the extended [[Hamming code]], respectively. The Goethals and Delsarte–Goethals codes, which are also a quaternary dual pair, are related in a less simple manner to three error-correcting [[BCH code]]s.
+
( $  n = 2  ^ {m} - 1 $,  
 +
with $  m \geq  3 $
 +
odd) is both a generator matrix for the Kerdock code and a parity check matrix for the  "Preparata"  code. One sees that the Kerdock and Preparata codes are quaternary analogues of the first-order [[Reed–Muller code]] and of the extended [[Hamming code]], respectively. The Goethals and Delsarte–Goethals codes, which are also a quaternary dual pair, are related in a less simple manner to three error-correcting [[BCH code]]s.
  
Besides MacWilliams duality, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008035.png" /> structure also bears influence on the decoding (cf. [[#References|[a4]]], Fig. 2) and on the coset structure of the Preparata code, which gives rise to a new distance-regular graph of diameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008036.png" /> [[#References|[a4]]].
+
Besides MacWilliams duality, the $  \mathbf Z _ {4} $
 +
structure also bears influence on the decoding (cf. [[#References|[a4]]], Fig. 2) and on the coset structure of the Preparata code, which gives rise to a new distance-regular graph of diameter $  4 $[[#References|[a4]]].
  
 
The article [[#References|[a4]]], which solves a twenty-year-old riddle, was awarded the 1995 IEEE Information Theory award for best paper. Geometrical repercussions can be found in [[#References|[a3]]], [[#References|[a6]]].
 
The article [[#References|[a4]]], which solves a twenty-year-old riddle, was awarded the 1995 IEEE Information Theory award for best paper. Geometrical repercussions can be found in [[#References|[a3]]], [[#References|[a6]]].

Revision as of 22:14, 5 June 2020



A most famous relation in coding theory is a discrete avatar of the Fourier transform which relates the weight enumerator $ W _ {C} $ of a linear code $ C $ and the weight enumerator of its dual $ C ^ \perp $ with respect to the standard scalar product, namely

$$ W _ {C ^ \perp } ( x,y ) = { \frac{1}{\left | C \right | } } W _ {C} ( x + y,x - y ) . $$

(Cf. MacWilliams identities.) A simple example of a dual pair of codes is the Hamming code $ H _ {m} $, a (big) $ [ n = 2 ^ {m} ,n - m - 1,4 ] $ code whose dual is the (small) first-order Reed–Muller code $ R _ {m} $. The matrix

$$ \left ( \begin{array}{ccccccc} 1 & 1 & 1 & 1 & 1 &\dots & 1 \\ 0 & 1 &\alpha &\alpha ^ {2} &\alpha ^ {3} &\dots &\alpha ^ {n - 1 } \\ \end{array} \right ) , $$

where $ n = 2 ^ {m} - 1 $ and $ \alpha $ is a root of $ {\overline{f}\; } ( x ) $, is both a generator matrix for $ R _ {m} $ and a parity check matrix for $ H _ {m} $. The small code $ R _ {m} $ has the simple weight distribution

$$ W _ {R _ {m} } ( x,y ) = x ^ {n} + y ^ {n} + ( 2n - 2 ) ( xy ) ^ {n/2 } . $$

The MacWilliams formula now gives an explicit expression for $ W _ {H _ {m} } $ which would be cumbersome to obtain directly.

There is no Fourier transform without Abelian groups and therefore there is no MacWilliams formula for non-linear codes. The discovery first of the $ ( 16,256,6 ) $[[ Nordstrom–Robinson code]] in 1967, non-linear and still formally self-dual for the MacWilliams relation, followed in 1968 and 1972 [a8] by the discovery of two infinite families of non-linear codes, the Preparata codes and Kerdock codes, respectively, whose weight enumerators are MacWilliams dual of each other, were until [a4] an unexplained phenomenon. The unsuccessful efforts of many distinguished researchers on this notoriously difficult problem [a8] led one of them to declare [a5] that it was "merely a coincidence" .

A well-known trick in modulation theory to address the $ 4 $- PSK constellation consists of using a (very simple) case of the Gray mapping. This is a mapping from $ \mathbf Z _ {4} $ to $ { \mathop{\rm GF} } ( 2 ) ^ {2} $ defined by

$$ 0 \rightarrow 00, 1 \rightarrow 01, 2 \rightarrow 11, 3 \rightarrow 10, $$

and extended to a mapping from $ \mathbf Z _ {4} ^ {n} $ to $ { \mathop{\rm GF} } ( 2 ) ^ {2n } $ in the natural way. The key property is that the mapping $ \phi $ from $ \mathbf Z _ {4} ^ {n} $ equipped with the Lee distance to $ { \mathop{\rm GF} } ( 2 ) ^ {2n } $ equipped with the Hamming distance is an isometric mapping of metric spaces. The trace parametrization of quaternary $ M $- sequences can be used to show that the Kerdock code as defined in [a8], p. 1107, is essentially the cyclic code associated to construction $ A $ of [a1], p. 458, and the construction of [a9]. In particular, if $ \xi $ denotes a primitive root of $ n $ in a suitable Galois ring, [a7], then the matrix

$$ \left ( \begin{array}{ccccccc} 1 & 1 & 1 & 1 & 1 &\dots & 1 \\ 0 & 1 &\xi &\xi ^ {2} &\xi ^ {3} &\dots &\xi ^ {n - 1 } \\ \end{array} \right ) $$

( $ n = 2 ^ {m} - 1 $, with $ m \geq 3 $ odd) is both a generator matrix for the Kerdock code and a parity check matrix for the "Preparata" code. One sees that the Kerdock and Preparata codes are quaternary analogues of the first-order Reed–Muller code and of the extended Hamming code, respectively. The Goethals and Delsarte–Goethals codes, which are also a quaternary dual pair, are related in a less simple manner to three error-correcting BCH codes.

Besides MacWilliams duality, the $ \mathbf Z _ {4} $ structure also bears influence on the decoding (cf. [a4], Fig. 2) and on the coset structure of the Preparata code, which gives rise to a new distance-regular graph of diameter $ 4 $[a4].

The article [a4], which solves a twenty-year-old riddle, was awarded the 1995 IEEE Information Theory award for best paper. Geometrical repercussions can be found in [a3], [a6].

References

[a1] S. Boztas, A.R. Hammons, P. V. Kumar, "-phase sequence with near optimum correlation properties" IEEE Trans. Inform. Th. , 38 (1992) pp. 1101–1113
[a2] J.H. Conway, N.J.A. Sloane, "Sphere packings, lattices and groups" , Springer (1992)
[a3] A.R. Calderbank, P.J. Cameron, W.M. Kantor, J.J. Seidel, "-Kerdock codes, orthogonal spreads, and extremal euclidean line sets" Proc. London Math. Soc. (to appear)
[a4] A.R. Hammons, P.V. Kumar, A.R. Calderbank, N.J.A. Sloane, P. Solé, "The -linearity of Kerdock, Preparata, Goethals, and related codes" IEEE Trans. Information Th. , 40 (1994) pp. 301–319
[a5] W.M. Kantor, "On the inequivalence of generalized Preparata codes" IEEE Inform. Th. , 29 (1983) pp. 345–348
[a6] W.M. Kantor, "Quaternionic line sets and quaternionic Kerdock codes" Linear Alg. & Its Appl. (special issue in honor of J.J. Seidel) , 226–228 (1995) pp. 749–779
[a7] B.R. MacDonald, "Finite rings with identity" , M. Dekker (1974)
[a8] F.J. MacWilliams, N.J.A. Sloane, "The theory of error-correcting codes" , North-Holland (1977)
[a9] P. Solé, "A quaternary cyclic code and a family of quaternary sequences with low correlation" , Lecture Notes in Computer Science , 388 , Springer (1989) pp. 193–201
How to Cite This Entry:
Kerdock and Preparata codes. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Kerdock_and_Preparata_codes&oldid=47487
This article was adapted from an original article by P. Solé (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article