A linear construction for certain Kerdock and Preparata codes
HTML articles powered by AMS MathViewer
- by A. R. Calderbank, A. R. Hammons, P. Vijay Kumar, N. J. A. Sloane and Patrick Solé PDF
- Bull. Amer. Math. Soc. 29 (1993), 218-222 Request permission
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
- 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, DOI 10.1109/TIT.1983.1056675 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. 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.
- 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, DOI 10.1007/978-3-642-74341-2
- 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, DOI 10.1007/BFb0019858 J. H. Conway and N. J. A. Sloane, Sphere-packings, lattices and groups, 2nd ed., Springer-Verlag, New York, 1992.
- 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, DOI 10.1016/0097-3165(93)90070-O
- P. Delsarte and J.-M. Goethals, Alternating bilinear forms over $GF(q)$, J. Combinatorial Theory Ser. A 19 (1975), 26–50. MR 401810, DOI 10.1016/0097-3165(75)90090-4
- 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, DOI 10.1090/dimacs/014/03
- J.-M. Goethals, Two dual families of nonlinear binary codes, Electron. Lett. 10 (1974), 471–472. MR 456917, DOI 10.1049/el:19740375
- Jean-Marie Goethals, Nonlinear codes defined by quadratic forms over $\textrm {GF}(2)$, Information and Control 31 (1976), no. 1, 43–74. MR 406682, DOI 10.1016/S0019-9958(76)90384-3 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. 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. 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.
- William M. Kantor, An exponential number of generalized Kerdock codes, Inform. and Control 53 (1982), no. 1-2, 74–80. MR 715523, DOI 10.1016/S0019-9958(82)91139-1
- William M. Kantor, Spreads, translation planes and Kerdock sets. I, SIAM J. Algebraic Discrete Methods 3 (1982), no. 2, 151–165. MR 655556, DOI 10.1137/0603015
- William M. Kantor, On the inequivalence of generalized Preparata codes, IEEE Trans. Inform. Theory 29 (1983), no. 3, 345–348. MR 712394, DOI 10.1109/TIT.1983.1056676
- A. M. Kerdock, A class of low-rate nonlinear binary codes, Information and Control 20 (1972), 182–187; ibid. 21 (1972), 395. MR 345707, DOI 10.1016/S0019-9958(72)90376-2
- 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, DOI 10.1007/BF01194097
- 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 F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes, North-Holland, Amsterdam, 1977. A. W. Nordstrom and J. P. Robinson, An optimum nonlinear code, Inform. Control 11 (1967), 613-616.
- Franco P. Preparata, A class of optimum nonlinear double-error-correcting codes, Information and Control 13 (1968), 378–400. MR 242563, DOI 10.1016/S0019-9958(68)90874-7
- 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, DOI 10.1007/BFb0019857
- Mieko Yamada, Distance-regular digraphs of girth $4$ over an extension ring of $\textbf {Z}/4\textbf {Z}$, Graphs Combin. 6 (1990), no. 4, 381–394. MR 1092588, DOI 10.1007/BF01787706
Additional Information
- © Copyright 1993 American Mathematical Society
- 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