{'fraction_non_alphanumeric': 0.055310168826069886, 'fraction_numerical': 0.021569493521790342, 'mean_word_length': 3.856751281134549, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes

Certain notorious nonlinear binary codes contain more codewords than any known linear code. These include the codes constructed by Nordstrom-Robinson, Kerdock, Preparata, Goethals, and Delsarte-Goethals. It is shown here that all these codes can be very simply constructed as binary images under the Gray map of linear codes over Z_4, the integers mod 4 (although this requires a slight modification of the Preparata and Goethals codes). The construction implies that all these binary codes are distance invariant. Duality in the Z_4 domain implies that the binary images have dual weight distributions. The Kerdock and"Preparata"codes are duals over Z_4 -- and the Nordstrom-Robinson code is self-dual -- which explains why their weight distributions are dual to each other. The Kerdock and"Preparata"codes are Z_4-analogues of first-order Reed-Muller and extended Hamming codes, respectively. All these codes are extended cyclic codes over Z_4, which greatly simplifies encoding and decoding. An algebraic hard-decision decoding algorithm is given for the"Preparata"code and a Hadamard-transform soft-decision decoding algorithm for the Kerdock code. Binary first- and second-order Reed-Muller codes are also linear over Z_4, but extended Hamming codes of length n>= 32 and the Golay code are not. Using Z_4-linearity, a new family of distance regular graphs are constructed on the cosets of the"Preparata"code.


I. Introduction
Several notorious families of nonlinear codes have more codewords than any comparable linear code presently known. These are the Nordstrom-Robinson , Kerdock, Preparata , Goethals and Delsarte-Goethals codes [10], [28], [31], [32], [46], [56], [58], [61]. Besides their excellent error-correcting capabilities these codes are remarkable because the Kerdock and Preparata codes are 'formal duals', in the sense that although these codes are nonlinear, the weight distribution of one is the MacWilliams transform of the weight distribution of the other [56,Chap. 15]. The main unsolved question concerning these codes has always been whether they are duals in some more algebraic sense. Many authors have investigated these codes, and have found that (except for the Nordstrom-Robinson code) they are not unique, and indeed that large numbers of codes exist with the same weight distributions [2], [13], [43], [44], [45], [54]. Kantor [45] declares that the "apparent relationship between these [families of codes] is merely a coincidence." Although this may be true for many versions of these codes, we will show that, when properly defined, Kerdock and Preparata codes are linear over Z 4 (the integers mod 4), and that as Z 4 -codes they are duals. They are in fact just extended cyclic codes over Z 4 .
When studying these four-phase sequences, Hammons and Kumar and later independently Calderbank, Sloane and Solé noticed the striking resemblance between the 2-adic (i.e. base 2) expansions of the quaternary codewords and the standard construction of the Kerdock codes.
The reader can see this for himself by comparing the formulae on page 1107 of [7] (the common starting point for the two independent discoveries) and page 458 of [56].
Both teams then realized that the Kerdock code is simply the image of the quaternary code (when extended by an zero-sum check symbol) under the Gray map defined below (see (15)).
This was a logical step to pursue since the Gray map translates a quaternary code with high minimal Lee or Euclidean distance into a binary code of twice the length with high minimal Hamming distance.
The discovery that the quaternary dual gives a code which is the 'correct' definition of the 'Preparata' code followed almost immediately.
The two teams worked independently until the middle of November 1992, when, discovering the considerable overlap between their work, they decided to join forces. The discoveries about the Kerdock and Preparata codes are in a paper [38] presented by Hammons and Kumar at the International Symposium on Information Theory (San Antonio, January 1993, but submitted in June 1992), in Hammons' dissertation [34], and in a manuscript [39] (now replaced by the present paper) submitted in early November 1992 to these Transactions. Hammons  The present paper is a compositum of all our results.
The discovery that the Nordstrom-Robinson code is a quaternary version of the octacode was made by Forney, Sloane and Trott in early October 1992, and is described in [30]. (It was already known to Hammons and Kumar in June 1992 that the Nordstrom-Robinson code was linear over Z 4 , but they had not made the identification with the octacode.) It can be shown that the binary nonlinear single-error-correcting codes found by Best [4], Julin [42], Sloane and Whitehead [65] and others can also be more simply described as codes over Z 4 (although here the corresponding Z 4 -codes are nonlinear). This will be described elsewhere [24]. Large sequence families for code-division multiple-access (CDMA) that are supersets of the near optimum four-phase sequence families described above and which are related to the Delsarte-Goethals codes are investigated in [49].
The paper is arranged as follows. Section II discusses linear codes over Z 4 , their duals, and their images as binary codes under the Gray map. Necessary and sufficient conditions are given for a binary code to be the image of a linear code over Z 4 . Reed-Muller codes of length 2 m and orders 0, 1, 2, m − 1, m satisfy these conditions, but extended Hamming codes and the Golay code do not. Cyclic codes over Z 4 are studied by means of Galois rings GR(4 m ) rather than the Galois fields GF (2 m ) used to analyze binary cyclic codes, and Section III is devoted to these rings.
In Section IV we show that Kerdock codes are extended cyclic codes over Z 4 , and in fact are simply Z 4 -analogues of first-order Reed-Muller codes (see the generator matrix (49) and also §5.4). The Nordstrom-Robinson code is discussed in §4. 5. Subsequent subsections give the weight distribution of the Kerdock codes and a soft-decision decoding algorithm for them.
In Section V we show that the binary images of the quaternary duals of the Kerdock codes are Preparata-like codes, having essentially the same properties as Preparata's original codes.
Theorem 15, however, shows that the 'Preparata' codes are strictly different from the original construction. §5.2 provides a finite field transform characterization of the 'Preparata' codes and compares them with the original codes. The 'Preparata' codes have a very simple decoding algorithm ( §5.3). (This is considerably simpler than any previous decoding algorithm -compare [5].) Section 5.4 defines a family of quaternary Reed-Muller codes QRM (m, r) which generalizes the quaternary Kerdock and 'Preparata' codes. The final subsections are concerned with the automorphism groups of these codes ( §5.5), and a new family of distance regular graphs defined on the cosets of the 'Preparata' code ( §5.6).
In Section VI we show that the binary nonlinear Delsarte-Goethals codes [28] are also extended cyclic codes over Z 4 , and that their Z 4 -duals have essentially the same properties as the Goethals codes [31], [32] and the 'Goethals-Delsarte' codes of Hergert [40].
Postscript. After this paper was completed, V. I. Levenshtein drew our attention to an article by Nechaev [57]. In this article Nechaev considers the quaternary sequences {c t } given (in the notation of the present paper) by The principal result of [57] shows that the set of {b t } is a nonlinear binary cyclic code which is equivalent to the binary Kerdock code punctured in two coordinates. However, [57] makes no mention of the fundamental isometry of Eq. (15), nor of Preparata codes and the sense in which they are duals of Kerdock codes.
II. Quaternary and related binary codes 2.1. Quaternary codes.
By a quaternary code C of length n we shall mean a linear block code over Z 4 , i.e. an additive subgroup of Z n 4 . Such codes have been studied recently both in connection with the construction of sequences with low correlation ( [6], [7], [67], [72]) and in a variety of other contexts (see [23] and the references contained therein).
We define an inner product on Z n 4 by a·b = a 1 b 1 + · · ·+ a n b n ( mod 4), and then the notions of dual code (C ⊥ ), self-orthogonal code (C ⊆ C ⊥ ) and self-dual code (C = C ⊥ ) are defined in the standard way (cf. [47], [56]). For many applications there is no need to distinguish between +1 components of codewords and −1 components, and so we say that two codes are equivalent if one can be obtained from the other by permuting the coordinates and (if necessary) changing the signs of certain coordinates. Codes differing by only a permutation of coordinates are called permutation-equivalent. The automorphism group Aut(C) of C consists of all permutations and sign-changes of the coordinates that preserve the set of codewords.
Any code is permutation-equivalent to a code C with generator matrix of the form where A and C are Z 2 -matrices and B is a Z 4 -matrix. The code is then an elementary abelian group of type 4 k 1 2 k 2 , containing 2 2k 1 +k 2 codewords. We shall indicate this by saying that C has type 4 k 1 2 k 2 , or simply that |C| = 4 k 1 2 k 2 .
Eq. (1) illustrates a difference in point of view between ring theory and coding theory.
Quaternary codes are Z 4 -modules. A ring theorist would point out, correctly, that a quaternary code is not in general a free module [41], and so need not have a basis. Although this is true, (1) is a perfectly good generator matrix. Encoding is carried out by writing the information and mapping u to the codeword uG. The code C is a free Z 4 -module if and only if k 2 = 0.
If C has generator matrix (1), the dual code C ⊥ has generator matrix and type 4 n−k 1 −k 2 2 k 2 .

Weight enumerators.
Several weight enumerators are associated with a quaternary code C. The complete weight enumerator (or c.w.e.) of C is where n j (a) is the number of components of a that are congruent to j (mod 4) (cf. [47], [56, p. 141]). Permutation-equivalent codes have the same c.w.e., but equivalent codes may have distinct c.w.e.'s. The appropriate weight enumerator for an equivalence class of codes is the symmetrized weight enumerator (or s.w.e.), obtained by identifying X and Z in (3): The Lee weights of 0, 1, 2, 3 ∈ Z 4 are 0, 1, 2, 1 respectively, and the Lee weight wt L (a) of a ∈ Z n 4 is the rational sum of the Lee weights of its components. This weight function defines a distance d L ( , ) on Z N 4 called the Lee metric. The Lee weight enumerator of C is a homogeneous polynomial of degree 2n. Finally, the Hamming weight enumerator of C, less useful than the others, is We then have the following analogues of the MacWilliams identity, giving the weight enumerators for the dual code C ⊥ ( [47], [48], [23]): There are also several analogues of Gleason's theorem, giving bases for the weight enumerators of self-dual codes -see [47], [23].

Associated complex-valued sequences.
We may associate to every Z 4 -valued vector a = (a 1 , . . . , a n ) an equivalent complex roots-ofunity sequence s = i a = (i a 1 , . . . , i an ), where i = √ −1. Then, given a set C of quaternary vectors, we let denote the corresponding set of complex sequences. When C is regarded as a set of CDMA signature sequences, its effectiveness depends on the complex correlations (or Hermitian inner products) of the sequences in Ω(C). When C is regarded as a code, its error-correcting capability depends on the Euclidean distance properties of Ω(C). If a, b are quaternary vectors with associated vectors s = i a , t = i b , then where H denotes the Hermitian inner product, and is the complex correlation of a and b. Note that ζ depends only on the difference a − b. By (11), if the nontrivial correlations of Ω(C) are low in magnitude, then the set possesses large minimal Euclidean distance. We also see that 2.4. Binary codes associated with quaternary codes; the Gray map.
In communication systems employing quadrature phase-shift keying (QPSK), the preferred assignment of two information bits to the four possible phases is the one shown in Fig. 1, in which adjacent phases differ by only one binary digit. This mapping is called Gray encoding and has the advantage that, when a quaternary codeword is transmitted across an additive white Gaussian noise channel, the errors most likely to occur are those causing a single erroneously decoded information bit.
Note that α(c) + β(c) + γ(c) = 0 for all c ∈ Z 4 . We construct binary codes from quaternary codes using the Gray map φ : Z n 4 → Z 2n 2 given by When we speak of the binary image of a quaternary code C, we will always mean its image C = φ(C) under the Gray map. We use script letters for quaternary codes, with the corresponding Latin letters for their binary images.
C is in general a nonlinear binary code of length 2n. If C is linear, and C is defined by (1), then C has generator matrix     We say that a binary code C is Z 4 -linear if its coordinates can be arranged so that it is the image under the Gray map φ of a quaternary code C.
The crucial property of the Gray map is that it preserves distances.
Theorem 1. φ is a distance-preserving map or isometry from Proof. It is easy to see from the definitions (and Fig. 1) that where wt( ) and d( , ) are the usual Hamming weight and distance functions for binary vectors.
From (13), (18), the Hamming distance between the binary images φ(a) and φ(b) is proportional to the squared Euclidean distance between the complex sequences i a and i b .
Two other binary codes C (1) , C (2) are canonically associated with a quaternary code C.
These are the linear codes defined by If C has generator matrix (1), then C (1) is an [n, k 1 ] code with generator matrix while C (2) ⊇ C (1) is an [n, k 1 + k 2 ] code with generator matrix -compare (16). It is shown in [23] that given any binary codes C ′ , C ′′ of length n with C ′′ ⊇ C ′ , there is a quaternary code C with C (1) = C ′ , C (2) = C ′′ .

Weight and distance properties.
Since in general C = φ(C) is not linear, it need not have a dual. We define its Z 4 -dual to be Note that one cannot add an arrow marked 'dual' on the right side to produce a commuting diagram.
In this section we discuss the weight and distance properties of C and C ⊥ . The principal results to be derived here are the following: (1) C and C ⊥ are distance invariant.
(2) The weight distributions of C and C ⊥ are MacWilliams transforms of one another.
A binary code C is said to be distance invariant [56, p. 40] if the Hamming weight distributions of its translates u + C are the same for all u ∈ C.
Theorem 2. If C is a (linear) quaternary code, then its binary Gray representation C = φ(C) is distance invariant.
Proof. C is distance invariant (with respect to Lee distance) because it is linear, and the result then follows from Theorem 1.
For a distance invariant code C of length n, the (Hamming) weight enumerator is independent of c ∈ C. If C = φ(C), it follows from Theorem 1 and (5) that Theorem 3. If C and C ⊥ are dual quaternary codes, then the weight distributions of the binary codes C = φ(C) and C ⊥ = φ(C ⊥ ) are related by the binary MacWilliams transform.

Existence and linearity conditions.
We now give necessary and sufficient conditions for a binary code to be Z 4 -linear, and for the binary image of a quaternary code to be a linear code. The reader who is primarily interested in Kerdock and Preparata codes should skip to Section III.
Since φ(−c) = (γ(c), β(c)), it follows that if C is Z 4 -linear then C is fixed under the 'swap' map σ that interchanges the left and right halves of each codeword: In other words σ applies the permutation (1, n + 1)(2, n + 2) · · · (n, 2n) (26) to the coordinates. This is a fixed-point-free involution in the automorphism group of C.

Theorem 4. A binary, not necessarily linear, code C of even length is Z 4 -linear if and only
if its coordinates can be arranged so that where σ is the swap map that interchanges the left and right halves of a vector, and * denotes the componentwise product of two vectors.
Proof. This is an immediate consequence of the easily-verified identity for all a, b ∈ Z n 4 .

Theorem 5. The binary image φ(C) of a quaternary linear code C is linear if and only if
Proof. This is an immediate consequence of the identity for all a, b ∈ Z n 4 .

Theorem 6. A binary linear code C of even length is Z 4 -linear if and only if its coordinates
can be permuted so that where σ is as in Theorem 4.
Proof. This is also a consequence of (28).
Conditions (29), (27) and (31) are very restrictive, and (we are now speaking informally) imply that most binary codes are not Z 4 -linear.
For example, the [16,5,8] code RM (1, 4) and the [16,11,4] code RM (2, 4) are the binary images of the quaternary codes with generator matrices In Eq. (31), if u, v are represented by Boolean functions of degree r, and (u + σ(u)) * (v + σ(v)) = 0, then (u + σ(u)) * (v + σ(v)) is a Boolean function of degree 2r − 2. So an rth order Reed-Muller code with r ≤ m/2 satisfies (31) provided r ≤ 2 (which gives an alternative proof of part of Theorem 7), but we conjecture that it does not satisfy (31) then there is no permutation of the coordinates of C such that the permuted code is equal to φ(C) for some quaternary code C. However, we have found a proof of this only for (m − 2)nd order RM codes.
Let F be the subcode of H fixed under the swap map σ of (25), and let ψ be the homomorphism Let E consist of the right-hand halves of the codewords in im ψ.
Then E is a [2 m−1 , ≥ 2 m−1 − m, 2] code, containing say A i words of weight i. We know from Theorem 6 that E is closed under componentwise multiplication.
Therefore the A 2 + A 3 words of weights 2 and 3 in E must be disjoint, or else E would contain a word of weight 1. Omitting these words from E, we are left with a code of length Hamming code of length 2 m−1 . For m ≥ 5 we now use (33) to deduce that E contains a word of weight 1, a contradiction.
Theorem 8 demonstrates that a binary code can be Z 4 -linear, even though its dual is not.
For RM (1, m) is Z 4 -linear, while in general its dual, RM (m − 2, m), is not.

The Golay code.
Since the Nordstrom-Robinson code is Z 4 -linear (as we shall see in Theorem 12) and is closely connected with the Golay code ( [56, p. 73], it is natural to ask if the Golay code itself is Theorem 9. The [24,12,8] Golay code G is not Z 4 -linear. Proof. Suppose on the contrary that G is the binary image of a quaternary linear code G. The swap map σ (see (26)) is a fixed-point-free involution in Aut(G), the Mathieu group M 24 . It is known ( [19], [22]) that M 24 contains a single conjugacy class of such involutions. Therefore, without loss of generality, we may suppose that this involution is the map defined by addition of the hexacodeword 11 ω ω ω ω in the MOG description of G (see [22], Chap. 11, §9). In the

MOG diagram this is the permutation
The diagram specifies the division of the 24 coordinates into twelve pairs, although we do not yet know which coordinate of each pair is on the left (in (25)) and which is on the right.
III. Cyclic codes over Z 4 and Galois rings 3.1. Galois rings.
To study BCH and other cyclic codes of length n over an alphabet of size q, it is customary to work in a Galois field GF (q m ), an extension of degree m of a ground field GF (q) [56]. The ground field GF (q) is identified with the alphabet, and the extension field is chosen so that it contains an nth root of unity.
A similar approach is used for cyclic codes of length n over Z 4 , only now one constructs a Galois ring GR(4 m ) (not a field), that is an extension of Z 4 of degree m containing an nth root of unity.
Galois rings have been studied by MacDonald [55], Liebler and Mena [52], Shankar [64], Solé [67], Yamada [71], Boztaş, Hammons and Kumar [7], among others, and of course the general machinery of commutative algebra, as described for example in Zariski and Samuel [76], is applicable to these rings. We list here some of the basic facts we shall need; proofs may be found in the above references.
Let Yamada [71]). The polynomial h(X) is a primitive basic irreducible polynomial, and may be found as follows. Let , where e(X) contains only even powers and d(X) only odd powers.
Then h(X) is given by h(X 2 ) = ±(e 2 (X)−d 2 (X)). This is Graeffe's method [70], [67] for finding a polynomial whose roots are the squares of the roots of h 2 (X). For example, when m = 3, Table I in [7] gives all primitive basic irreducible polynomials of degree m ≤ 10.
Let ξ be a root of h(X), so that ξ n = 1. Then the Galois ring GR(4 m ) is defined to be . There are two canonical ways to represent the 4 m elements of R (just as there are two canonical ways, multiplicative and additive, to represent elements of GF (q m )).
In the first representation, every element c ∈ R has a unique 'multiplicative' or 2-adic where a and b belong to the set The map τ : c → a is given by and satisfies (see [71]). Given c, one determines a from (37) and then b from (35).
In the second representation, each element c ∈ R has a unique 'additive' representation For example, if m = 3 and h is given by (34), the additive representations for the elements of This table may be produced (just as for Galois fields) by a (modulo 4) shift register whose feedback polynomial is h(X). By using (35), the table gives the additive representation of every element of R.
One essential difference between R = GR(4 m ) and a Galois field is that R contains zero divisors: these are the elements of the radical 2R, the unique maximal ideal in R (R is a local ring). Let µ denote the map R → R/2R. Then θ = µ(ξ) is a root of h 2 (X), and we can identify We denote the set of regular or invertible elements of R by R * = R \ 2R. Every element of R * has a unique representation in the form where H is the cyclic group of order 2 m − 1 generated by ξ, and E is the group of principal units of R, that is, elements of the form 1 + 2t, t ∈ T . E has the structure of an elementary abelian group of order 2 m and is isomorphic to the additive group of GF (2 m ).

Frobenius and trace maps.
The Frobenius map f from R to R is the ring automorphism that takes any element c = a+2b ∈ R to f generates the Galois group of R over Z 4 , and f m is the identity map. The relative trace from R to Z 4 is defined by For comparison, the usual trace from GF (2 m ) to Z 2 is given by and the Frobenius map is simply the squaring map The following commutativity relationships between these maps are easily verified: In particular, since tr is not identically zero, it follows that the Galois ring trace is nontrivial.
In fact, T is an onto mapping from R to Z 4 . The set of elements of R invariant under f is identical with Z 4 .

Dependencies among ξ j .
For later use we record some results about dependencies among the powers ξ j .
Proof. If on the contrary we had ±ξ j ± ξ k = 2λ, λ ∈ R, then applying µ we obtain θ j + θ k = 0, which contradicts the fact that θ is primitive in GF (2 m ).

The ring R.
As usual when studying cyclic codes of length n it is convenient to represent codewords by polynomials modulo X n − 1. We identify v = (v 0 , v 1 , . . . , v n−1 ) with the polynomial v(X) = n−1 r=0 v r X r in the ring R = Z 4 [X]/(X n − 1). We must be careful when working with R: it is not a unique factorization domain -for example X 4 − 1 has two distinct factorizations into irreducible polynomials in R: Note also that every element 1 + 2λ, λ ∈ R, is a root of X 2 − 1. On the other hand R is a principal ideal domain: just as in the binary case, cyclic codes have a single generator (the proof is given in Calderbank and Sloane, Modular and p-adic cyclic codes, Designs, Codes and Cryptography, to appear).

IV. Kerdock codes
The main result of this section is a very simple quaternary construction for Kerdock codes.
4.1. The Kerdock code is an extended cyclic code over Z 4 .
Let h(X) be a primitive basic irreducible polynomial of degree m, as above, and let g(X) be the reciprocal polynomial to (X n − 1)/((X − 1)h(X)), where n = 2 m − 1. This code is distance invariant.
K is a code of type 4 m+1 . The binary code K (1) associated with K (see (19)) is RM (1, m).
(the second one being read from (41)).
For m = 5, we may take h(X) Kerdock codes contain more codewords than any known linear code with the same minimal distance (although we are not aware of any theorem to guarantee this, except at length 16).

Family A.
If we omit the factor X − 1 from the parity check polynomial for K − , we obtain a cyclic code containing 4 m codewords. Let A denote the family of cyclically distinct vectors obtained from this code by deleting the zero vector and failing to distinguish between a vector and any of its cyclic shifts. The corresponding collection Ω(A) of complex-valued sequences has been studied in [6], [7], [67], [72] as a family of asymptotically optimal CDMA signature sequences (referred to as Family A in [7]). Since the sequences of Ω(A) have low values of auto-and cross-correlation, the set Ω(A) also has large minimal Euclidean distance. Thus where v (λ) = (T (λ), T (λξ), T (λξ 2 ), . . . , T (λξ n−1 )) .
This theorem is essentially equivalent to Theorem 3 of [7]. Proof of Theorem 10. We consider an arbitrary codeword c ∈ K in the form (54). We will show that c t has 2-adic expansion given by where the elements π, η ∈ GF (2 m ) and A, B ∈ Z 2 are arbitrary, and we adopt the convention that θ ∞ = 0.
The next step is to observe that the vectors (b t ) and (a t + b t ) defined by (56) The fact that φ(K) is distance invariant follows from Theorem 2.
It is shown in [8] that when m is odd, the family of binary sequences {Q(πθ t )+tr(ηθ t ) : η, π in GF (2 m ), not both zero} has Gold-like correlation properties, but a larger linear span.

The Nordstrom-Robinson code.
The case m = 3 is particularly interesting. The Kerdock and Preparata codes of length 16 coincide, giving the Nordstrom-Robinson code ( [58]; see also [62]). This is the unique binary code of length 16, minimal distance 6, containing 256 words [66], [33]. In this case K is the 'octacode', whose generator matrix is given in (51). The octacode may also be characterized as the unique self-dual quaternary code of length 8 and minimal Lee weight 6 [23], or as the 'glue code' required to construct the 24-dimensional Leech lattice from eight copies of the face-centered cubic lattice [22,Chap. 24]. Thus the following theorem is a special case of Theorem 10.

Theorem 12. The Nordstrom-Robinson code is the binary image of the octacode under the Gray map.
The symmetrized weight enumerator of the octacode is ( [23]) and the weight distribution of the Nordstrom-Robinson code is then given by (24).

Weight distribution.
The weight distribution of any Kerdock code is also easily determined from the new quaternary description.
Proof. This is a slight modification of the argument used in [7] to obtain the correlation distribution of the associated complex sequences. We assume the codewords c ∈ K are defined as in Theorem 11. As mentioned in §4.5, the words for which π = 0 (and λ ∈ R * in (53)) form a first-order Reed-Muller code, and account for the words of weights 0, 2 m and 2 m+1 .
When m is even, m ≥ 2, a similar argument shows that φ(K) is a nonlinear code of length 2 m+1 , with 4 m+1 codewords, minimal distance 2 m − 2 m/2 , and weight distribution This code is not as good as a double-error-correcting BCH code.

Soft-decision decoding of Kerdock codes.
Although in the theoretical development we make a distinction between the quaternary code K and the associated nonlinear binary code K = φ(K) (and similarly in Section V between P = K ⊥ and P = φ(P)), they are really two different descriptions of the same code. For instance, a decoder for the quaternary code obviously provides a decoder for the binary code and conversely.
The following is a new soft-decision decoding algorithm for the Kerdock code. This is comparable in complexity to previously known techniques that were derived from the binary description of the code. Brute-force decoding of a received vector {v t : t ∈ ∆} requires the computation of its correlation with all possible received signals. In particular, the decoder must compute the correlation for all λ = ξ r +2ξ s , r, s ∈ ∆ and all δ ∈ Z 4 , and find that pair (λ, δ) for which Real{ζ(λ, δ)} is a maximum.
An immediate reduction in complexity is obtained by writing where we adopt the convention that for l in ∆, l + ∞ = ∞. The correlation sums ζ(ξ r + 2ξ s , δ) This complex-data FHT decoding algorithm is of the same order of complexity as recently published real-data FHT decoders for the Kerdock codes [1], [29] based on the general super-code decoding method of Conway and Sloane [20]. These real-data algorithms perform 2 m FHTs of size 2 m+1 . Finally, we note that the case m = 3 corresponds to decoding the Nordstrom-Robinson code.

V. Preparata codes
In this section we show that the binary image of the dual code P = K ⊥ is a Preparata-like code with essentially the same properties as Preparata's original code (yet is much simpler to construct).

The 'Preparata' code is an extended cyclic code over Z 4 .
Let h(X) and g(X) be defined as in §4.1. Note that P − has parity check polynomial g(X), and that (49), (50) are equivalent parity check matrices for P. Also P is a code of type 4 2 m −m−1 . The code P = φ(P) is the Z 4 -dual of K, and we refer to it as a 'Preparata' code, using the quotes to distinguish it from Preparata's original code. It is known that the Preparata code (and P ) contains more codewords than any linear code with the same minimal distance [10]. The binary code P (1) associated with P (see (19)) is RM (m − 2, m).
Proof of Theorem 14. It follows from Theorems 2 and 3 that P is distance invariant and its weight distribution is the MacWilliams transform of that of K. By Theorem 24 of [56], Chapter 15, P has the same weight distribution as the original Preparata code.
Semakov, Zinoviev and Zaitsev [63] had already shown in 1971 that any code with the same parameters as the Preparata code must be distance invariant.
There is one essential difference between P and the original Preparata code. It is known that the latter is contained in the extended Hamming code spanned by its codewords. Proof. The first assertion follows by considering the binary images of the following sequence of codes: For the second assertion we use the fact that P is an extended cyclic code with generator polynomial h(X) = m j=0 h j X j (say). Let h ∞ = −h(1) = ±1, since h 2 (1) = 1. Then P has a generator matrix of the form It follows from (30) that the linear span of P = φ(P) contains all words of the form φ(2α(a) * α(b)), for a, b ∈ P. Taking a and b to be as indicated in (65)

Transform-domain characterization of 'Preparata' codes.
In spite of the previous theorem, in this section we shall show that the 'Preparata' code P = φ(P) and Preparata's original code have similar characterizations by finite field transforms.
Proof. This follows from the definition of the Galois ring transform and the parity check matrix for P given in Eq. (49).

Theorem 17. The binary 'Preparata' code P consists of all vectors
Note that equations (66) are over R, whereas equations (67) are over GF (2 m ).
As we have already seen in §4.5, the appropriate quaternary code in the case m = 3 is the self-dual octacode.

Decoding the quaternary 'Preparata' code in the Z 4 domain.
There is a very simple decoding algorithm for the 'Preparata' code P, obtained by working in the Z 4 domain. This is an optimal syndrome decoder: it corrects all error patterns of Lee weight at most 2, detects all errors of Lee weight 3, and detects some errors of Lee weight 4.
A decision tree for the algorithm is shown in Fig. 2. We use the parity check matrix H given in (49), and assume m is odd and ≥ 3.
be the received vector. The syndrome Hv ′ has two components, which we write as where A, B ∈ T .
In Theorem 13 we saw that exactly four nonzero weights occur in the Lee weight distribution of the quaternary Kerdock code K = P ⊥ , and hence also in the Hamming weight distribution of K. It follows that the covering radius of P is at most 4 ( Double errors of Lee weight 2. We begin by supposing that t = 0 and where X, Y ∈ T and X = Y . Note that A = 0 since by (P1) X − Y is invertible. We have . The unique solution to these equations is y = b 2 /a, x = a + b 2 /a. Note that when b = 0 or b = a, the double error involves the first column of H. Next we suppose that t = 2 and that where X, Y ∈ T , X = Y , A = 0. Proceeding as above we find and so x and y are distinct roots of the equation A necessary and sufficient condition for this equation to have distinct roots is that (see [56], Chap. 9, Theorem 15; [51]).
Finally we suppose that t = 2 and where X, Y ∈ T , X = Y , A = 0. We now find that a = x + y , (b + a) 2 = xy , and so x and y are distinct roots of the equation A necessary and sufficient condition for this equation to have distinct roots is that

Quaternary Reed-Muller codes
In §2.7 we defined a quaternary code ZRM (r, m − 1) whose image under the Gray map φ is the binary Reed-Muller code RM (r, m), provided r ∈ {0, 1, 2, m − 1, m}. In this section we define another quaternary Reed-Muller code, QRM (r, m), whose image under the map α is RM (r, m) for all r, and which includes the Kerdock and 'Preparata' codes as special cases.
Definition. Let QRM (0, m) be the quaternary repetition code of length n = 2 m , and for 1 ≤ r ≤ m let QRM (r, m) be generated by QRM (0, m) together with all vectors of the form where j ranges over all representatives of cyclotomic cosets mod 2 m − 1 for which wt(j) ≤ r, and λ j ranges over R. Then QRM (r, m) is a quaternary code of length n = 2 m and type 4 k , where k = 1 + m 1 + · · · + m r .
Consider any system Ω of linear equations over Z 4 , in the variables c x , x ∈ T (see (36))), that x∈T together with equations of the form Theorem 20. The linear system Ω is invariant under the doubly transitive group G of 'affine' permutations of the form where a, b ∈ T and a = 0. The order of G is 2 m (2 m − 1).
Proof. Repeated application of the Frobenius automorphism (43) to Eq. (78) gives for all j. It now follows from (77), (78) and (80) that Hence Ω is invariant under G. Remarks. By the automorphism group Aut(C) of a binary nonlinear code C we will mean the set of all coordinate permutations that preserve the code. It is easy to see that if C = φ(C) is the binary image of a linear quaternary code C, then Aut(C) is isomorphic to a subgroup of Aut(C).
For odd m ≥ 5 these groups have the same orders as those in the Corollary.
We conclude that, for odd m ≥ 5, the groups mentioned in the Corollary are the full automorphism groups of these quaternary codes. (For the 'Preparata' codes we use the fact that they have the same automorphism group as their duals.) The case m = 3 is exceptional. The quaternary octacode has an automorphism group of order 1344 (Conway and Sloane [23]), whereas the group of the binary Nordstrom-Robinson code has order 80640 (Berlekamp [3], see also Conway and Sloane [21]).

Definition.
A Z 4 -coset of P is the image under φ of a coset of P in Z N/2 4 . We construct a graph Γ m on the Z 4 -cosets of P by joining two cosets by an edge if they are the images of cosets x + P, y + P such that x − y + P has minimal Lee weight 1.
Let Π denote the partition of Z N 2 into Z 4 -cosets of P . Then Γ n can be thought of as the quotient graph ([9, §11.1.B]) of the N -hypercube by the partition Π.
The aim of this section is to show that Γ m is distance regular and to compute its distance distribution diagram and eigenmatrix P. For this purpose we need certain regularity properties of P and Π.
If C is a binary code of length N , its outer distribution matrix B = (B x,j ) is the 2 N ×(N +1) matrix with typical entry B x,j = |{y ∈ C : d(x, y) = j}| (Delsarte [26]). In other words the rows of B are the weight distributions of the translates of

C.
A code C of covering radius r is said to be completely regular [27] if B contains exactly r + 1 distinct rows. A partition Π of Z N 2 into cosets is said to be completely regular if all members of the partition are completely regular with the same matrix.

Lemma 1. The covering radius of P is 4.
Proof. In the previous section we saw that it is at most 4. But P is contained in a code with the same weight distribution as an extended Hamming code (Theorem 15), and so by the supercode lemma [17] the covering radius is at least 4. Proof. The well-known recurrence relation between the columns of B ( [26], [56]) has order 4, by Lemma 1, and so it is sufficient to check that B x,j can take at most five different values for fixed x ∈ Z N 2 and 0 ≤ j ≤ 4. If d(x, P ) ≤ 2, the fact that P has minimal distance 6 shows that B x,j is either 0 or 1. If d(x, P ) = 3 then Lemma 2 shows that B x,3 = (N − 1)/3. Clearly As in [25] it will be noticed that P is neither linear, perfect, nor uniformly packed, and so (in the notation of Levenshtein [50]) is not a design of Delsarte type (i.e. d ≥ 2s ′ − 1); P is a highly nontrivial example of a completely regular code. Furthermore the Z 4 -linearity of P and the properties of φ show that each Z 4 -coset of P is completely regular with the same outer distribution matrix. Hence Π is completely regular. The next result follows immediately from Theorems 11.1.6 and 11.1.5 of [9]. We now proceed to a more detailed study of the parameters of Γ m . Recall that the valencies v j are the numbers of points at distance j from a given point. The intersection numbers a j , b j , c j are defined in Chapter 4 of [9]. Proof. Let us take a parity check matrix H of the form (49) for P. For a coset x + P let Hx ′ be the associated syndrome and let ν(x) be the leading bit of Hx ′ . Then ν is a map from the vertices of Γ m onto {0, 1}. Let X j be the set ν −1 (j), j = 0, 1. Since ν(x) = 1 if x has weight 1, two cosets with the same image under ν cannot have adjacent images in Γ m .
Proof. From [68] and the fact that P has size 2 N /N 2 and four nonzero dual distances d ′ The desired result then follows from d ′ Corollary. The eigenmatrix P for Γ m is Proof. See [9], §4.1.B, or [25], Proposition 3.17.
Remarks. 1) Let R j denote the jth class of the association scheme corresponding to Γ m . Then R 1 + R 3 has only three eigenvalues, N 2 , 0, −N 2 , and is a strongly regular graph isomorphic to the complete bipartite graph K N 2 /2, N 2 /2 . It would be interesting to see if R 3 is also distance regular.
Proof. (a) Comparing Eqs. (37) and (34) of [56], Chap. 15, we see that the difference between the Kerdock code and the Delsarte-Goethals code comes from the vectors (c, c), where c belongs to the code defined by Eq. (31) of that chapter. We already know from Theorem 10 that the first two rows of (81) produce the Kerdock code, and it is easily seen that the remaining rows produce the required (c, c) words. (b) This follows because the Goethals-Delsarte code is by construction (see Hergert [40]) a distance invariant codes whose weight enumerator is the MacWilliams transform of the Delsarte-Goethals code. The minimal Lee distance of these dual codes is no more than 8, since they contain words of shape 2 4 , corresponding to the doubles of words in the extended Hamming code defined by the binary images of the first two rows of (81). That the minimal Lee distance is at least 8 follows from Theorem 25 below. 2) For the automorphism groups of these codes, see Section 5.5.
Setting s = a + a 2 , we obtain the quadratic equation We shall prove that this equation has no solution. First observe that y 1 = 1, so the equation does not have a double root. Suppose the equation has two distinct roots. It follows from (83) that there exist distinct nonzero elements Y 1 , However, this implies the existence of codewords in the 'Preparata' code of type 1 2 3 2 0 n−3 , which is not the case. Hence (84) has no solutions and the proof is complete.
We are presently investigating other generalizations of (49).

VII. Conclusions
The classical theory of cyclic codes, which includes BCH, Reed-Solomon, Reed-Muller codes, etc., regards these codes as ideals in polynomial rings over finite fields. Some famous nonlinear codes found by Nordstrom-Robinson, Kerdock, Preparata, Goethals and others, more powerful than any linear codes, cannot be handled by this machinery. We have shown that when suitably defined all these codes are ideals in polynomial rings over the ring of integers