The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes(*) 

A. Roger Hammons, Jr.(**)
Hughes Aircraft Company 
Network Systems Division, Germantown, MD 20876 U.S.A. 

P. Vijay Kumar(**)
Communication Science Institute, EE-Systems 
University of Southern California, Los Angeles, CA 90089~U.S.A. 

A. R. Calderbank(***) and N. J. A. Sloane(***) 
Mathematical Sciences Research Center 
AT&T Bell Laboratories, Murray Hill, NJ 07974 U.S.A. 

Patrick Sol'{e}(****)
CNRS -- I3S, 250 rue A. Einstein, b^{a}timent 4 
Sophia -- Antipolis, 06560 Valbonne, France 


ABSTRACT

Certain notorious nonlinear binary codes contain more codewords than any
known linear code.  These include the codes constructed by Nordstrom-Robinson, 
Kerdock, Preparata, Goethals, and Delsarte-Goethals.
It is shown here that all these codes can be very simply constructed
as binary images under the Gray map of linear codes over Z_4, the integers
mod 4 (although this requires a slight modification of the Preparata and Goethals codes).

The construction implies that all these binary codes are
distance invariant.  Duality in the Z_4 domain implies that the binary images
have dual weight distributions.
The Kerdock and "Preparata" codes are duals over Z_4 -- and the Nordstrom-Robinson
code is self-dual -- which explains why their weight distributions are dual to each other.
The Kerdock and "Preparata" codes are Z_4-analogues of first-order
Reed-Muller and extended Hamming codes, respectively.

All these codes are extended cyclic codes over Z_4,
which greatly simplifies encoding and decoding.
An algebraic hard-decision decoding algorithm is given for the
"Preparata" code and a Hadamard-transform soft-decision
decoding algorithm for the Kerdock code.
Binary first- and second-order Reed-Muller codes are also linear
over Z_4, but extended Hamming codes of length n >= 32 and the Golay
code are not.

Using Z_4-linearity, a new family of distance regular graphs are
constructed on the cosets of the "Preparata" code.


For the full version see
http://www.research.att.com/~njas/doc/linear.pdf (pdf) or
http://www.research.att.com/~njas/doc/linear.ps (ps)



(*) A different version of this paper appeared in 
IEEE Trans. Inform. Theory, 40 (1994), 301-319.

(**) The work of A.~R. Hammons, Jr. and P.~V. Kumar was supported in part by the
National Science Foundation under Grant NCR-9016077 and by Hughes
Aircraft Company under its Ph.D. fellowship program.~~}

(***) Present address:
Information Sciences Research
AT&T Shannon Lab
Florham Park, NJ 07932-0971 USA
Email: njas@research.att.com

(****) P. Sol'{e} thanks the DIMACS Center and the IEEE for travel support.