N. J. A. Sloane: Papers on codes over Z4 etc.

Notes:

The key idea (which is very beautiful) can be described in a few sentences. For many years there was a great mystery concerning some of the best binary codes known - the Preparata and Kerdock codes. Although these were nonlinear codes, they appeared to be duals to each other. Many people, including me, worked very hard to explain this mystery.

The answer turns out to be astonishingly simple, once one realizes that these should be regarded as linear codes over Z4 (the integers mod 4).

Start with the binary cyclic Hamming code of length 7, with generator polynomial 

        g(x) = x^3 + x + 1,
a divisor of x^7 - 1. "Lift" g(x) to the polynomial 
        G(x) = x^3 + 2 x^2 + x - 1
which divides x^7 - 1 (mod 4), and is congruent to g(x) (mod 2). Then G(x) generates a cyclic code over length 7 over Z4. Add a zero-sum check symbol, and we get a self-dual code (the "octacode") of length 8 over Z4. Map this to a binary code by sending 
         0    to   00
         1    to   01
         2    to   11
         3    to   10
and we get the Nordstrom-Robinson code, a nonlinear binary code of length 16 with 256 words and minimal distance 6.

Replace g(x) by the generator polynomial of a Hamming code of length 2^m - 1 (m odd), repeat the process, and we get the Preparata codes. Using the duals of the Z4 codes we get the Kerdock codes.

Beautiful!

The following papers give more details. Item 8 gives a brief overview. For self-dual codes over Z4 see items 1 and 11.

By lifting G(x) further, to mod 8, mod 16, etc., we eventually get the world's first code over the 2-adic numbers - this is the cyclic code of length 7 with generator polynomial

x^3 + a x^2 + (a-1) x - 1

where a = 0 + 2 + 4 + 32 + 128 + 256 + ... is the 2-adic number satisfying a^2 - a + 2 = 0. This generalizes the Hamming code of length 7, the octacode and the Nordstrom-Robinson code. See 7 for details.

  1. Self-Dual Codes over the Integers Modulo 4, [note: Fig. 1 and Fig. 2 are in separate files] J. H. Conway and N. J. A. Sloane, J. Combinatorial Theory, Series A, 62 (1993), pp. 30-45.

  2. A Linear Construction for Certain Kerdock and Preparata Codes, A. R. Calderbank, A. R. Hammons Jr., P. Vijay Kumar, N. J. A. Sloane and P. Sole", Bulletin Amer. Math. Soc., 29 (1993), pp. 218-222, Also DIMACS Technical Report 93-50, August 1993.

  3. The Nordstrom-Robinson Code is the Binary Image of the Octacode, G. D. Forney, Jr., N. J. A. Sloane and M. D. Trott, in Coding and Quantization: DIMACS / IEEE Workshop October 19-21, 1992, R. Calderbank, G. D. Forney, Jr. and N. Moayeri (editors), Amer. Math. Soc., 1993, pp. 19-26. Also DIMACS Technical Report 93-49, August 1993.

  4. The Z4-Linearity of Kerdock, Preparata, Goethals and Related Codes, A. R. Hammons Jr., P. Vijay Kumar, A. R. Calderbank, N. J. A. Sloane and P. Sole", IEEE Trans. Information Theory, 40 (1994), pp. 301-319, Also DIMACS Technical Report 93-52, August 1993. [This paper won the IEEE Information Theory Society 1995 Prize Paper Award.]

  5. Quaternary Constructions for the Binary Single-Error-Correcting Codes of Julin, Best and Others, J. H. Conway and N. J. A. Sloane, Designs, Codes and Cryptography, 41 (1994), pp. 31-42, Also DIMACS Technical Report 93-53, August 1993.

  6. On the Apparent Duality of the Kerdock and Preparata Codes, A. R. Hammons, P. V. Kumar, A. R. Calderbank, N. J. A. Sloane and P. Sole", in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Proceedings 10th International Symposium, AAECC-10, San Juan de Puerto Rico, May 1993); Lecture Notes in Computer Science, Vol. 673, G. Cohen, T. Mora and O. Moreno (editors), Springer-Verlag, NY, 1993.

  7. Modular and p-Adic Cyclic Codes, A. R. Calderbank and N. J. A. Sloane, Designs, Codes and Cryptography, 6 (1995), pp. 21-35.

  8. Algebraic Coding Theory: Recent Developments Related to the Integers Mod 4, N. J. A. Sloane, in Study of Algebraic Combinatorics (Proceedings Conference on Algebraic Combinatorics, Kyoto 1993), Research Institute for Mathematical Sciences, Kyoto, 1995, pp. 38-52.

  9. Double Circulant Codes over Z4 and Even Unimodular Lattices, A. R. Calderbank and N. J. A. Sloane, J. Algebraic Combinatorics, Vol. 6 (1997), pp. 119-131.

  10. The Ternary Golay Code, the Integers Mod 9 and the Coxeter-Todd Lattice, A. R. Calderbank and N. J. A. Sloane, IEEE Trans. Inform. Theory, 42 (1996), pp. 636-637. Unfortunately this paper is wrong: the lattice is not K_12.

  11. Self-Dual Codes, E. M. Rains and N. J. A. Sloane, in Handbook of Coding Theory, V. S. Pless and W. C. Huffman (editors), Elsevier, Amsterdam, 1998, pp. 177-294.

Up [ Full publication list | Return to my home page ]