Ar. Hammons et al., THE Z4-LINEARITY OF KERDOCK, PREPARATA, GOETHALS, AND RELATED CODES, IEEE transactions on information theory, 40(2), 1994, pp. 301-319
Citations number
75
Categorie Soggetti
Information Science & Library Science","Engineering, Eletrical & Electronic
Certain notorious nonlinear binary codes contain more codewords than a
ny 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 bina
ry images under the Gray map of linear codes over Z4, 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 Z4 domain implies that the bina
ry images have dual weight distributions. The Kerdock and ''Preparata'
' codes are duals over Z4-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 Z4-analogues of first-order Re
ed-Muller and extended Hamming codes, respectively. All these codes ar
e extended cyclic codes over Z4, 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-M
uller codes are also linear over Z4, but extended Hamming codes of len
gth n greater-than-or-equal-to 32 and the Golay code are not. Using Z4
-linearity, a new family of distance regular graphs are constructed on
the cosets of the ''Preparata'' code.