Namespaces
Variants
Actions

Delsarte-Goethals code

From Encyclopedia of Mathematics
Revision as of 17:20, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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 be an even integer. Let be an integer satisfying . For each and there is a Delsarte–Goethals code, denoted . This code has length , and is sandwiched between the Kerdock code and the second-order Reed–Muller code of the same length (cf. also Kerdock and Preparata codes; Error-correcting code):

The number of codewords in is and the minimum distance is . As increases, the number of codewords increases and the minimum distance decreases. When , the Delsarte–Goethals code coincides with the Kerdock code , and when the Delsarte–Goethals code coincides with .

The construction of involves taking the union of certain cosets of in . 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 , and this property determines the minimum distance. The fact that it is possible to find 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 -linear code. A direct proof of the minimum distance from the 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 construction gives an explanation for their existence, see [a3].

References

[a1] A.R. Calderbank, G. McGuire, "-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 " 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 -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=17142
This article was adapted from an original article by G. McGuire (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article