Skip to main content

The Z4-Linearity of Kerdock, Preparata, Goethals, and Related Codes

Publication ,  Journal Article
Hammons, AR; Kumar, PV; Calderbank, AR; Sloane, NJA; Solé, P
Published in: IEEE Transactions on Information Theory
January 1, 1994

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 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 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 Reed-Muller and extended Hamming codes, respectively. All these codes are 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-Muller codes are also linear over Z4, but extended Hamming codes of length n > 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. © 1994 IEEE

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

IEEE Transactions on Information Theory

DOI

EISSN

1557-9654

ISSN

0018-9448

Publication Date

January 1, 1994

Volume

40

Issue

2

Start / End Page

301 / 319

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Hammons, A. R., Kumar, P. V., Calderbank, A. R., Sloane, N. J. A., & Solé, P. (1994). The Z4-Linearity of Kerdock, Preparata, Goethals, and Related Codes. IEEE Transactions on Information Theory, 40(2), 301–319. https://doi.org/10.1109/18.312154
Hammons, A. R., P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P. Solé. “The Z4-Linearity of Kerdock, Preparata, Goethals, and Related Codes.” IEEE Transactions on Information Theory 40, no. 2 (January 1, 1994): 301–19. https://doi.org/10.1109/18.312154.
Hammons AR, Kumar PV, Calderbank AR, Sloane NJA, Solé P. The Z4-Linearity of Kerdock, Preparata, Goethals, and Related Codes. IEEE Transactions on Information Theory. 1994 Jan 1;40(2):301–19.
Hammons, A. R., et al. “The Z4-Linearity of Kerdock, Preparata, Goethals, and Related Codes.” IEEE Transactions on Information Theory, vol. 40, no. 2, Jan. 1994, pp. 301–19. Scopus, doi:10.1109/18.312154.
Hammons AR, Kumar PV, Calderbank AR, Sloane NJA, Solé P. The Z4-Linearity of Kerdock, Preparata, Goethals, and Related Codes. IEEE Transactions on Information Theory. 1994 Jan 1;40(2):301–319.

Published In

IEEE Transactions on Information Theory

DOI

EISSN

1557-9654

ISSN

0018-9448

Publication Date

January 1, 1994

Volume

40

Issue

2

Start / End Page

301 / 319

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing