Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

A linear construction for certain Kerdock and Preparata codes


Authors: A. R. Calderbank, A. R. Hammons, P. Vijay Kumar, N. J. A. Sloane and Patrick Solé
Journal: Bull. Amer. Math. Soc. 29 (1993), 218-222
MSC (2000): Primary 94B05; Secondary 94B15
DOI: https://doi.org/10.1090/S0273-0979-1993-00426-9
MathSciNet review: 1215307
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The Nordstrom-Robinson, Kerdock, and (slightly modified) Preparata codes are shown to be linear over $ {\mathbb{Z}_4}$, the integers $ {\bmod\;4}$. The Kerdock and Preparata codes are duals over $ {\mathbb{Z}_4}$, and the Nordstrom-Robinson code is self-dual. All these codes are just extended cyclic codes over $ {\mathbb{Z}_4}$. This provides a simple definition for these codes and explains why their Hamming weight distributions are dual to each other. First- and second-order Reed-Muller codes are also linear codes over $ {\mathbb{Z}_4}$, but Hamming codes in general are not, nor is the Golay code.


References [Enhancements On Off] (What's this?)

  • [BLW83] R. D. Baker, J. H. van Lint, and R. M. Wilson, On the Preparata and Goethals codes, IEEE Trans. Inform. Theory 29 (1983), 342-345. MR 712393 (85c:94029)
  • [Bo90] S. Boztaş, Near-optimal $ 4\phi $ (4-phase) sequences and optimal binary sequences for CDMA, Ph.D. dissertation, Univ. of Southern California, Los Angeles, 1990.
  • [BHK92] S. Boztaş, A. R. Hammons, Jr., and P. V. Kumar, 4-phase sequences with near-optimum correlation properties, IEEE Trans. Inform. Theory 38 (1992), 1101-1113.
  • [BCN89] A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-regular graphs, Springer-Verlag, New York, 1989. MR 1002568 (90e:05001)
  • [Ca89] C. Carlet, A simple description of Kerdock codes, Lecture Notes in Comput. Sci., vol. 388, Springer-Verlag, Berlin and New York, 1989, pp. 202-208. MR 1023691 (90j:94037)
  • [CS92] J. H. Conway and N. J. A. Sloane, Sphere-packings, lattices and groups, 2nd ed., Springer-Verlag, New York, 1992.
  • [CS93] -, Self-dual codes over the integers modulo 4, J. Combin. Theory Ser. A 62 (1993), 30-45. MR 1198379 (93m:94026)
  • [DG75] P. Delsarte and J. M. Goethals, Alternating bilinear forms over $ GF(q)$, J. Combin. Theory Ser. A 19 (1975), 26-50. MR 0401810 (53:5637)
  • [FST93] G. D. Forney, Jr., N. J. A. Sloane, and M. D. Trott, The Nordstrom-Robinson code is the binary image of the octacode, Proceedings DIMACS/IEEE Workshop on Coding and Quantization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Amer. Math. Soc., Providence, RI (to appear). MR 1267739 (94m:94019)
  • [Go74] J. M. Goethals, Two dual families of nonlinear binary codes, Electron. Lett. 10 (1974), 471-472. MR 0456917 (56:15136)
  • [Go76] -, Nonlinear codes defined by quadratic forms over $ GF(2)$, Inform. Control 31 (1976), 43-74. MR 0406682 (53:10468)
  • [Ha92] A. R. Hammons, Jr., On four-phase sequences with low correlation and their relation to Kerdock and Preparata codes, Ph.D. dissertation, Univ. of Southern California, November 1992.
  • [HK93] A. R. Hammons, Jr., and P. V. Kumar, On the apparent duality of Kerdock and Preparata codes, Abstracts, IEEE Internat. Sympos. Inform. Theory, San Antonio, TX, January 1993.
  • [HKCSS] A. R. Hammons, Jr., P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P. Solé, The $ {\mathbb{Z}_4}$linearity of Kerdock, Preparata, Goethals and related codes, IEEE Trans. Inform. Theory, in press.
  • [Ka82] W. M. Kantor, An exponential number of generalized Kerdock codes, Inform. Control 53 (1982), 74-80. MR 715523 (85i:94022)
  • [Ka82a] -, Spreads, translation planes and Kerdock sets, SIAM J. Algebra Discrete Math. 3 (1982), 151-165, 308-318. MR 666856 (83m:51013b)
  • [Ka83] -, On the inequivalence of generalized Preparata codes, IEEE Trans. Inform. Theory 29 (1983), 345-348. MR 712394 (85a:94030)
  • [Ke72] A. M. Kerdock, A class of low-rate nonlinear binary codes, Inform. Control 20 (1972), 182-187. MR 0345707 (49:10438)
  • [K187] M. Klemm, Über die Identität von MacWilliams für die Gewichtsfunktion von Codes, Arch. Math. (Brno) 49 (1987), 400-406. MR 915913 (89b:94031)
  • [VL83] J. H. van Lint, Kerdock and Preparata codes, Congr. Numer. 39 (1983), 25-41. MR 734527 (85h:94037)
  • [MS77] F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes, North-Holland, Amsterdam, 1977.
  • [NR67] A. W. Nordstrom and J. P. Robinson, An optimum nonlinear code, Inform. Control 11 (1967), 613-616.
  • [Pr68] F. P. Preparata, A class of optimum nonlinear double-error correcting codes, Inform. Control 13 (1968), 378-400. MR 0242563 (39:3894)
  • [So89] P. Solé, A quaternary cyclic code, and a family of quadriphase sequences with low correlation properties, Lecture Notes in Comput. Sci., vol. 388, Springer-Verlag, New York and Berlin, 1989, pp. 193-201. MR 1023690 (90j:94036)
  • [Ya90] M. Yamada, Distance-regular digraphs of girth 4 over an extension ring of $ Z/4Z$, Graphs Combin. 6 (1990), 381-394. MR 1092588 (92h:05065)

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 94B05, 94B15

Retrieve articles in all journals with MSC (2000): 94B05, 94B15


Additional Information

DOI: https://doi.org/10.1090/S0273-0979-1993-00426-9
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society