N. J. A. Sloane: Papers on codes over Z4 etc.
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
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.
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.
- Self-Dual Codes over the Integers Modulo 4,
Fig. 1 and
are in separate files]
J. H. Conway and N. J. A. Sloane,
J. Combinatorial Theory, Series A, 62 (1993), pp. 30-45.
- 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.
- 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.
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
- 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.
- 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.
- Modular and p-Adic Cyclic Codes,
A. R. Calderbank and N. J. A. Sloane, Designs, Codes and Cryptography, 6 (1995), pp. 21-35.
- 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.
- 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.
- 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,
Unfortunately this paper is wrong: the lattice is not K_12.
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.
Full publication list |
Return to my home page