Namespaces
Variants
Actions

Difference between revisions of "Delsarte-Goethals code"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (AUTOMATIC EDIT (latexlist): Replaced 29 formulas out of 29 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
 
Line 1: Line 1:
 +
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
 +
 +
Out of 29 formulas, 29 were replaced by TEX code.-->
 +
 +
{{TEX|semi-auto}}{{TEX|done}}
 
A code belonging to a family of non-linear binary error-correcting codes (cf. also [[Error-correcting code|Error-correcting code]]). Delsarte–Goethals codes were first presented in a joint paper [[#References|[a2]]] by Ph. Delsarte and J.-M. Goethals.
 
A code belonging to a family of non-linear binary error-correcting codes (cf. also [[Error-correcting code|Error-correcting code]]). Delsarte–Goethals codes were first presented in a joint paper [[#References|[a2]]] by Ph. Delsarte and J.-M. Goethals.
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d1300501.png" /> be an even integer. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d1300502.png" /> be an integer satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d1300503.png" />. For each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d1300504.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d1300505.png" /> there is a Delsarte–Goethals code, denoted <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d1300506.png" />. This code has length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d1300507.png" />, and is sandwiched between the Kerdock code <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d1300508.png" /> and the second-order Reed–Muller code <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d1300509.png" /> of the same length (cf. also [[Kerdock and Preparata codes|Kerdock and Preparata codes]]; [[Error-correcting code|Error-correcting code]]):
+
Let $m \geq 4$ be an even integer. Let $r$ be an integer satisfying $0 \leq r \leq m / 2 - 1$. For each $m$ and $r$ there is a Delsarte–Goethals code, denoted $\operatorname{DG}( m , r )$. This code has length $2 ^ { m }$, and is sandwiched between the Kerdock code $K ( m )$ and the second-order Reed–Muller code $\operatorname{RM}( 2 , m )$ of the same length (cf. also [[Kerdock and Preparata codes|Kerdock and Preparata codes]]; [[Error-correcting code|Error-correcting code]]):
  
<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/d/d130/d130050/d13005010.png" /></td> </tr></table>
+
\begin{equation*} K ( m ) \subseteq \operatorname {DG} ( m , r ) \subseteq \operatorname {RM} ( 2 , m ). \end{equation*}
  
The number of codewords in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005011.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005012.png" /> and the minimum distance is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005013.png" />. As <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005014.png" /> increases, the number of codewords increases and the minimum distance decreases. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005015.png" />, the Delsarte–Goethals code coincides with the Kerdock code <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005016.png" />, and when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005017.png" /> the Delsarte–Goethals code coincides with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005018.png" />.
+
The number of codewords in $\operatorname{DG}( m , r )$ is $2 ^ { r ( m - 1 )  + 2 m}$ and the minimum distance is $2 ^ { m - 1 } - 2 ^ { m / 2 - 1 + r }$. As $r$ increases, the number of codewords increases and the minimum distance decreases. When $r = 0$, the Delsarte–Goethals code coincides with the Kerdock code $K ( m )$, and when $r = m / 2 - 1$ the Delsarte–Goethals code coincides with $\operatorname{RM}( 2 , m )$.
  
The construction of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005019.png" /> involves taking the union of certain cosets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005020.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005021.png" />. These cosets are determined by certain bilinear forms. The rank of these forms, and the rank of the sum of any two of them, is at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005022.png" />, and this property determines the minimum distance. The fact that it is possible to find <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005023.png" /> such forms is proved in [[#References|[a2]]] (see also [[#References|[a5]]]).
+
The construction of $\operatorname{DG} ( r , m )$ involves taking the union of certain cosets of $\operatorname {RM} ( 1 , m )$ in $\operatorname{RM}( 2 , m )$. These cosets are determined by certain bilinear forms. The rank of these forms, and the rank of the sum of any two of them, is at least $m - 2 r$, and this property determines the minimum distance. The fact that it is possible to find $2 ^ { r(m-1) + m - 1}$ such forms is proved in [[#References|[a2]]] (see also [[#References|[a5]]]).
  
The Delsarte–Goethals codes have been shown to have another construction. It was shown in [[#References|[a3]]] that they are the Gray image of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005024.png" />-linear code. A direct proof of the minimum distance from the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005025.png" /> construction was given in [[#References|[a1]]].
+
The Delsarte–Goethals codes have been shown to have another construction. It was shown in [[#References|[a3]]] that they are the Gray image of a $\mathbf{Z}_{4}$-linear code. A direct proof of the minimum distance from the $\mathbf{Z}_{4}$ construction was given in [[#References|[a1]]].
  
There exist non-linear binary codes whose distance distribution is the MacWilliams transform of the distribution of the Delsarte–Goethals codes, see [[#References|[a4]]]. These codes act like dual codes, and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005026.png" /> construction gives an explanation for their existence, see [[#References|[a3]]].
+
There exist non-linear binary codes whose distance distribution is the MacWilliams transform of the distribution of the Delsarte–Goethals codes, see [[#References|[a4]]]. These codes act like dual codes, and the $\mathbf{Z}_{4}$ construction gives an explanation for their existence, see [[#References|[a3]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A.R. Calderbank,  G. McGuire,  "<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005027.png" />-linear codes obtained as projections of Kerdock and Delsarte–Goethals codes"  ''Linear Alg. &amp; Its Appl.'' , '''226–228'''  (1995)  pp. 647–665</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P. Delsarte,  J.M. Goethals,  "Alternating bilinear forms over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005028.png" />"  ''J. Combin. Th. A'' , '''19'''  (1975)  pp. 26–50</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A.R. Hammons,  P.V. Kumar,  A.R. Calderbank,  N.J.A. Sloane,  P. Sole,  "The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130050/d13005029.png" />-linearity of Kerdock, Preparata, Goethals, and related codes"  ''IEEE Trans. Inform. Th.'' , '''40'''  (1994)  pp. 301–319</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  F.B. Hergert,  "On the Delsarte–Goethals codes and their formal duals"  ''Discr. Math.'' , '''83'''  (1990)  pp. 249–263</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  F.J. MacWilliams,  N.J.A. Sloane,  "The theory of error-correcting codes" , North-Holland  (1977)</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  A.R. Calderbank,  G. McGuire,  "$\mathbf{Z}_{4}$-linear codes obtained as projections of Kerdock and Delsarte–Goethals codes"  ''Linear Alg. &amp; Its Appl.'' , '''226–228'''  (1995)  pp. 647–665</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  P. Delsarte,  J.M. Goethals,  "Alternating bilinear forms over $G F ( q )$"  ''J. Combin. Th. A'' , '''19'''  (1975)  pp. 26–50</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  A.R. Hammons,  P.V. Kumar,  A.R. Calderbank,  N.J.A. Sloane,  P. Sole,  "The $\mathbf{Z}_{4}$-linearity of Kerdock, Preparata, Goethals, and related codes"  ''IEEE Trans. Inform. Th.'' , '''40'''  (1994)  pp. 301–319</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  F.B. Hergert,  "On the Delsarte–Goethals codes and their formal duals"  ''Discr. Math.'' , '''83'''  (1990)  pp. 249–263</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  F.J. MacWilliams,  N.J.A. Sloane,  "The theory of error-correcting codes" , North-Holland  (1977)</td></tr></table>

Latest revision as of 16:52, 1 July 2020

A code belonging to a family of non-linear binary error-correcting codes (cf. also Error-correcting code). Delsarte–Goethals codes were first presented in a joint paper [a2] by Ph. Delsarte and J.-M. Goethals.

Let $m \geq 4$ be an even integer. Let $r$ be an integer satisfying $0 \leq r \leq m / 2 - 1$. For each $m$ and $r$ there is a Delsarte–Goethals code, denoted $\operatorname{DG}( m , r )$. This code has length $2 ^ { m }$, and is sandwiched between the Kerdock code $K ( m )$ and the second-order Reed–Muller code $\operatorname{RM}( 2 , m )$ of the same length (cf. also Kerdock and Preparata codes; Error-correcting code):

\begin{equation*} K ( m ) \subseteq \operatorname {DG} ( m , r ) \subseteq \operatorname {RM} ( 2 , m ). \end{equation*}

The number of codewords in $\operatorname{DG}( m , r )$ is $2 ^ { r ( m - 1 ) + 2 m}$ and the minimum distance is $2 ^ { m - 1 } - 2 ^ { m / 2 - 1 + r }$. As $r$ increases, the number of codewords increases and the minimum distance decreases. When $r = 0$, the Delsarte–Goethals code coincides with the Kerdock code $K ( m )$, and when $r = m / 2 - 1$ the Delsarte–Goethals code coincides with $\operatorname{RM}( 2 , m )$.

The construction of $\operatorname{DG} ( r , m )$ involves taking the union of certain cosets of $\operatorname {RM} ( 1 , m )$ in $\operatorname{RM}( 2 , m )$. These cosets are determined by certain bilinear forms. The rank of these forms, and the rank of the sum of any two of them, is at least $m - 2 r$, and this property determines the minimum distance. The fact that it is possible to find $2 ^ { r(m-1) + m - 1}$ such forms is proved in [a2] (see also [a5]).

The Delsarte–Goethals codes have been shown to have another construction. It was shown in [a3] that they are the Gray image of a $\mathbf{Z}_{4}$-linear code. A direct proof of the minimum distance from the $\mathbf{Z}_{4}$ construction was given in [a1].

There exist non-linear binary codes whose distance distribution is the MacWilliams transform of the distribution of the Delsarte–Goethals codes, see [a4]. These codes act like dual codes, and the $\mathbf{Z}_{4}$ construction gives an explanation for their existence, see [a3].

References

[a1] A.R. Calderbank, G. McGuire, "$\mathbf{Z}_{4}$-linear codes obtained as projections of Kerdock and Delsarte–Goethals codes" Linear Alg. & Its Appl. , 226–228 (1995) pp. 647–665
[a2] P. Delsarte, J.M. Goethals, "Alternating bilinear forms over $G F ( q )$" J. Combin. Th. A , 19 (1975) pp. 26–50
[a3] A.R. Hammons, P.V. Kumar, A.R. Calderbank, N.J.A. Sloane, P. Sole, "The $\mathbf{Z}_{4}$-linearity of Kerdock, Preparata, Goethals, and related codes" IEEE Trans. Inform. Th. , 40 (1994) pp. 301–319
[a4] F.B. Hergert, "On the Delsarte–Goethals codes and their formal duals" Discr. Math. , 83 (1990) pp. 249–263
[a5] F.J. MacWilliams, N.J.A. Sloane, "The theory of error-correcting codes" , North-Holland (1977)
How to Cite This Entry:
Delsarte-Goethals code. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Delsarte-Goethals_code&oldid=50050
This article was adapted from an original article by G. McGuire (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article