DIMACS TR: 93-52
The Z sub 4-Linearity of Kerdock, Preparata, Goethals and Related
Authors: A.Roger Hammons, Jr., P.Vijay Kumar, A. R. Calderbank,
N. J. A. Sloane, and Patrick Sole
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 sub 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 sub 4 domain implies that the binary images
have dual weight distributions.
The Kerdock and `Preparata' codes are duals over Z sub 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 sub 4-analogues of first-order
Reed-Muller and extended Hamming codes, respectively.
All these codes are extended cyclic codes over Z sub 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 sub 4, but extended Hamming codes of length n >= 32 and the Golay
code are not.
Using Z sub 4-linearity, a new family of distance regular graphs are
constructed on the cosets of the `Preparata' code.
Paper available at:
DIMACS Home Page