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[edit]