Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Available in electronic format
Available in print format 		Bulletin of the American Mathematical Society
Bulletin of the American Mathematical Society
ISSN 1088-9485(e) ISSN 0273-0979(p)

     

A linear construction for certain Kerdock and Preparata codes

Author(s): A. R. Calderbank; A. R. Hammons; P. Vijay Kumar; N. J. A. Sloane; Patrick Solé
Journal: Bull. Amer. Math. Soc. 29 (1993), 218-222.
MSC (2000): Primary 94B05; Secondary 94B15
MathSciNet review: 1215307
Retrieve article in: 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:

[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: 10.1090/S0273-0979-1993-00426-9
PII: S 0273-0979(1993)00426-9
Copyright of article: Copyright 1993, American Mathematical Society




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia