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
MathSciNet review: 1215307
Full-text PDF

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] Ronald D. Baker, Jacobus H. van Lint, and Richard M. Wilson, On the Preparata and Goethals codes, IEEE Trans. Inform. Theory 29 (1983), no. 3, 342–345. MR 712393, 10.1109/TIT.1983.1056675
  • [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, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 18, Springer-Verlag, Berlin, 1989. MR 1002568
  • [Ca89] Claude Carlet, A simple description of Kerdock codes, Coding theory and applications (Toulon, 1988) Lecture Notes in Comput. Sci., vol. 388, Springer, New York, 1989, pp. 202–208. MR 1023691, 10.1007/BFb0019858
  • [CS92] J. H. Conway and N. J. A. Sloane, Sphere-packings, lattices and groups, 2nd ed., Springer-Verlag, New York, 1992.
  • [CS93] J. H. Conway and N. J. A. Sloane, Self-dual codes over the integers modulo 4, J. Combin. Theory Ser. A 62 (1993), no. 1, 30–45. MR 1198379, 10.1016/0097-3165(93)90070-O
  • [DG75] P. Delsarte and J.-M. Goethals, Alternating bilinear forms over 𝐺𝐹(𝑞), J. Combinatorial Theory Ser. A 19 (1975), 26–50. MR 0401810
  • [FST93] G. D. Forney Jr., N. J. A. Sloane, and M. D. Trott, The Nordstrom-Robinson code is the binary image of the octacode, Coding and quantization (Piscataway, NJ, 1992) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 14, Amer. Math. Soc., Providence, RI, 1993, pp. 19–26. MR 1267739
  • [Go74] J.-M. Goethals, Two dual families of nonlinear binary codes, Electron. Lett. 10 (1974), 471–472. MR 0456917
  • [Go76] Jean-Marie Goethals, Nonlinear codes defined by quadratic forms over 𝐺𝐹(2), Information and Control 31 (1976), no. 1, 43–74. MR 0406682
  • [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] William M. Kantor, An exponential number of generalized Kerdock codes, Inform. and Control 53 (1982), no. 1-2, 74–80. MR 715523, 10.1016/S0019-9958(82)91139-1
  • [Ka82a] W. M. Kantor, Spreads, translation planes and Kerdock sets. II, SIAM J. Algebraic Discrete Methods 3 (1982), no. 3, 308–318. MR 666856, 10.1137/0603032
  • [Ka83] William M. Kantor, On the inequivalence of generalized Preparata codes, IEEE Trans. Inform. Theory 29 (1983), no. 3, 345–348. MR 712394, 10.1109/TIT.1983.1056676
  • [Ke72] A. M. Kerdock, A class of low-rate nonlinear binary codes, Information and Control 20 (1972), 182–187; ibid. 21 (1972), 395. MR 0345707
  • [K187] Michael Klemm, Über die Identität von MacWilliams für die Gewichtsfunktion von Codes, Arch. Math. (Basel) 49 (1987), no. 5, 400–406 (German). MR 915913, 10.1007/BF01194097
  • [VL83] J. H. van Lint, Kerdock codes and Preparata codes, Proceedings of the fourteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1983), 1983, pp. 25–41. MR 734527
  • [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] Franco P. Preparata, A class of optimum nonlinear double-error-correcting codes, Information and Control 13 (1968), 378–400. MR 0242563
  • [So89] Patrick Solé, A quaternary cyclic code, and a family of quadriphase sequences with low correlation properties, Coding theory and applications (Toulon, 1988) Lecture Notes in Comput. Sci., vol. 388, Springer, New York, 1989, pp. 193–201. MR 1023690, 10.1007/BFb0019857
  • [Ya90] Mieko Yamada, Distance-regular digraphs of girth 4 over an extension ring of 𝑍/4𝑍, Graphs Combin. 6 (1990), no. 4, 381–394. MR 1092588, 10.1007/BF01787706

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

Article copyright: © Copyright 1993 American Mathematical Society