Kerdock Codes

The Kerdock code K(u) for an even u ≥ 4 is a binary, non-linear (2u, 22u, 2u−1 – 2(u−2)/2)-code with strength 5 [1]. Therefore it can also be interpreted as an orthogonal array OA(22u, 2u, ℤ2, 5). No linear code or linear orthogonal array with these parameters can exist [2].

In [3] it is shown that these codes can be constructed by applying the Gray-code mapping 0 $ \mapsto$ 00, 1 $ \mapsto$ 01, 2 $ \mapsto$ 11, and 3 $ \mapsto$ 10 to extended cyclic codes over 4. When this mapping is applied to the dual of the code over 4, Preparata codes are obtained.

Partition in Translates

K(u) is the disjoint union of 2u−1 translates of the first-order Reed-Muller code RM(1, u), an OA(2u+1, 2u, ℤ2, 3) [1]. Construction X and Construction X4 can be applied to this pair.

Special Cases

See Also


[1]Anthony M. Kerdock.
A class of low-rate nonlinear binary codes.
Information and Control, 20(2):182–187, March 1972.
[2]Andries E. Brouwer and L. M. G. M. Tolhuizen.
A sharpening of the Johnson bound for binary linear codes and the nonexistence of linear codes with Preparata parameters.
Designs, Codes and Cryptography, 3(2):95–98, May 1993.
doi:10.1007/BF01388407 MR1218941 (94d:94009)
[3]A. R. Hammons, Jr., P. V. Kumar, A. R. Calderbank, Neil J. A. Sloane, and P. Solé.
The 4-linearity of Kerdock, Preparata, Goethals and related codes.
IEEE Transactions on Information Theory, 40(2):301–319, March 1994.
[4]F. Jessie MacWilliams and Neil J. A. Sloane.
The Theory of Error-Correcting Codes.
North-Holland, Amsterdam, 1977.
[5]A. S. Hedayat, Neil J. A. Sloane, and John Stufken.
Orthogonal Arrays.
Springer Series in Statistics. Springer-Verlag, 1999.


Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.
Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Kerdock Codes.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03.

Show usage of this method