Namespaces
Variants
Actions

Difference between revisions of "Kerdock and Preparata codes"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
m (fixing link)
 
(2 intermediate revisions by 2 users not shown)
Line 33: Line 33:
  
 
\begin{array}{ccccccc}
 
\begin{array}{ccccccc}
  1  & 1  & 1  & 1  & 1  &\dots & 1  \\
+
  1  & 1  & 1  & 1  & 1  &\cdots & 1  \\
  0  & 1  &\alpha  &\alpha  ^ {2}  &\alpha  ^ {3}  &\dots &\alpha ^ {n - 1 }  \\
+
  0  & 1  &\alpha  &\alpha  ^ {2}  &\alpha  ^ {3}  &\cdots &\alpha ^ {n - 1 }  \\
 
\end{array}
 
\end{array}
  
Line 42: Line 42:
 
where  $  n = 2  ^ {m} - 1 $
 
where  $  n = 2  ^ {m} - 1 $
 
and  $  \alpha $
 
and  $  \alpha $
is a root of  $  {\overline{f}\; } ( x ) $,  
+
is a root of  $  {\overline{f} } ( x ) $,  
 
is both a generator matrix for  $  R _ {m} $
 
is both a generator matrix for  $  R _ {m} $
 
and a parity check matrix for  $  H _ {m} $.  
 
and a parity check matrix for  $  H _ {m} $.  
Line 55: Line 55:
 
which would be cumbersome to obtain directly.
 
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 ) $[[
+
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" .
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" .
 
  
A well-known trick in modulation theory to address the  $  4 $-
+
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} $
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} $
 
to  $  { \mathop{\rm GF} } ( 2 )  ^ {2} $
 
defined by
 
defined by
Line 82: Line 80:
  
 
\begin{array}{ccccccc}
 
\begin{array}{ccccccc}
  1  & 1  & 1  & 1  & 1  &\dots & 1  \\
+
  1  & 1  & 1  & 1  & 1  &\cdots & 1  \\
  0  & 1  &\xi  &\xi  ^ {2}  &\xi  ^ {3}  &\dots &\xi ^ {n - 1 }  \\
+
  0  & 1  &\xi  &\xi  ^ {2}  &\xi  ^ {3}  &\cdots &\xi ^ {n - 1 }  \\
 
\end{array}
 
\end{array}
  
Line 94: Line 92:
  
 
Besides MacWilliams duality, the  $  \mathbf Z _ {4} $
 
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]]].
+
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]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S. Boztas,  A.R. Hammons,  P. V. Kumar,  "<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008037.png" />-phase sequence with near optimum correlation properties"  ''IEEE Trans. Inform. Th.'' , '''38'''  (1992)  pp. 1101–1113</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J.H. Conway,  N.J.A. Sloane,  "Sphere packings, lattices and groups" , Springer  (1992)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A.R. Calderbank,  P.J. Cameron,  W.M. Kantor,  J.J. Seidel,  "<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008038.png" />-Kerdock codes, orthogonal spreads, and extremal euclidean line sets"  ''Proc. London Math. Soc.''  (to appear)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A.R. Hammons,  P.V. Kumar,  A.R. Calderbank,  N.J.A. Sloane,  P. Solé,  "The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110080/k11008039.png" />-linearity of Kerdock, Preparata, Goethals, and related codes"  ''IEEE Trans. Information Th.'' , '''40'''  (1994)  pp. 301–319</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  W.M. Kantor,  "On the inequivalence of generalized Preparata codes"  ''IEEE Inform. Th.'' , '''29'''  (1983)  pp. 345–348</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  W.M. Kantor,  "Quaternionic line sets and quaternionic Kerdock codes"  ''Linear Alg. &amp; Its Appl. (special issue in honor of J.J. Seidel)'' , '''226–228'''  (1995)  pp. 749–779</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  B.R. MacDonald,  "Finite rings with identity" , M. Dekker  (1974)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  F.J. MacWilliams,  N.J.A. Sloane,  "The theory of error-correcting codes" , North-Holland  (1977)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  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</TD></TR></table>
+
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S. Boztas,  A.R. Hammons,  P. V. Kumar,  "$4$-phase sequence with near optimum correlation properties"  ''IEEE Trans. Inform. Th.'' , '''38'''  (1992)  pp. 1101–1113</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J.H. Conway,  N.J.A. Sloane,  "Sphere packings, lattices and groups" , Springer  (1992)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A.R. Calderbank,  P.J. Cameron,  W.M. Kantor,  J.J. Seidel,  "$\mathbf{Z}_4$-Kerdock codes, orthogonal spreads, and extremal euclidean line sets"  ''Proc. London Math. Soc.''  (to appear)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A.R. Hammons,  P.V. Kumar,  A.R. Calderbank,  N.J.A. Sloane,  P. Solé,  "The $\mathbf{Z}_4$-linearity of Kerdock, Preparata, Goethals, and related codes"  ''IEEE Trans. Information Th.'' , '''40'''  (1994)  pp. 301–319</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  W.M. Kantor,  "On the inequivalence of generalized Preparata codes"  ''IEEE Inform. Th.'' , '''29'''  (1983)  pp. 345–348</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  W.M. Kantor,  "Quaternionic line sets and quaternionic Kerdock codes"  ''Linear Alg. &amp; Its Appl. (special issue in honor of J.J. Seidel)'' , '''226–228'''  (1995)  pp. 749–779</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  B.R. MacDonald,  "Finite rings with identity" , M. Dekker  (1974)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  F.J. MacWilliams,  N.J.A. Sloane,  "The theory of error-correcting codes" , North-Holland  (1977)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  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</TD></TR></table>

Latest revision as of 02:58, 18 May 2022



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 &\cdots & 1 \\ 0 & 1 &\alpha &\alpha ^ {2} &\alpha ^ {3} &\cdots &\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 &\cdots & 1 \\ 0 & 1 &\xi &\xi ^ {2} &\xi ^ {3} &\cdots &\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, "$4$-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, "$\mathbf{Z}_4$-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 $\mathbf{Z}_4$-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