The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes
<|reference_start|>The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes: 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.<|reference_end|>
@article{hammons,2002the,
    title={The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes},
    author={A. Roger Hammons, Jr., P. Vijay Kumar, A.R. Calderbank, N.J.A. Sloane,
  Patrick Sol'e},
    journal={IEEE Trans. Inform. Theory, 40 (1994), 301-319},
    year={2002},
    archivePrefix={arXiv},
    eprint={math/0207208},
    primaryClass={math.CO cs.IT math.IT}
}