Math @ Duke

Publications [#235820] of Robert Calderbank
Papers Published
 Jr, ARH; Kumar, PV; Calderbank, AR; Sloane, NJA; Sole, P, Z_{4}linearity of Kerdock, Preparata, Goethals, and related codes,
IEEE Transactions on Information Theory, vol. 40 no. 2
(1994),
pp. 301319 [doi]
(last updated on 2018/02/20)
Abstract: Certain notorious nonlinear binary codes contain more codewords than any known linear code. These include the codes constructed by NordstromRobinson, Kerdock, Preparata, Goethals, and DelsarteGoethals. It is shown here that all these codes can be very simply constructed as binary 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 binary images have dual weight distributions. The Kerdock and 'Preparata' codes are duals over Z4  and the NordstromRobinson code is selfdual  which explains why their weight distributions are dual to each other. The Kerdock and 'Preparata' codes are Z4analogues of firstorder ReedMuller and extended Hamming codes, respectively. All these codes are extended cyclic codes over Z4, which greatly simplifies encoding and decoding. An algebraic harddecision decoding algorithm is given for the 'Preparata' code and a Hadamardtransform softdecision decoding algorithm for the Kerdock code. Binary firstand secondorder ReedMuller codes are also linear over Z4, but extended Hamming codes of length n ≥ 32 and the Golay code are not. Using Z4linearity, a new family of distance regular graphs are constructed on the cosets of the 'Preparata' code.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

