zbMATH — the first resource for mathematics

The \(\mathbb Z_4\)-linearity of Kerdock, Preparata, Goethals, and related codes. (English) Zbl 0811.94039
About 25 years ago, Preparata and Kerdock constructed two families of nonlinear codes that are better than the best linear codes with comparable parameters. It was soon observed that the parameters of these two families of codes are related by the MacWilliams identities in the same way as a linear code and its dual code are related. Up to the announcement of the results presented in this paper it was unclear whether this relation was just a coincidence or if there was more to it. Some distinguished colleagues, after studying the automorphism groups of these codes came to the conclusion that there was no.
This paper solves this old open problem in a very simple and elegant way. It turns out that the Kerdock code can be constructed starting from a simple linear code over the integers modulo 4. From this code one constructs a nonlinear binary code of twice this length by replacing 0, 1, 2, 3 by their binary images 00, 01, 11 resp. 10 under the Gray map. In a similar way taking the Gray map of the dual code (mod 4), one obtains a code with the same parameters as the Preparata code. This approach also explains why their weight enumerators are related by the MacWilliams identities. Most people now view the descriptions of the codes in this paper as the proper ones.
The paper also shows that other good nonlinear codes like the Delsarte-Goethals codes can be constructed in a similar manner. The theory of Galois rings turns out to be an important framework for studying such nonlinear codes over the integers mod 4.

94B60 Other types of codes
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
Full Text: DOI