Delsarte-Goethals code

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)