Interest in codes that are defined over rings rather than fields arose following the discovery by A.R. Hammons, P.V. Kumar, A.R. Calderbank, N.J.A. Sloane and P. Solé in 1994 that the nonlinear Preparata and Kerdock binary codes can be derived in a natural manner from linear codes over ℤ4. The Preparata and Kerdock binary codes are among the best binary codes known — the Preparata code has more codewords for its length than any known linear code.
Magma provides basic facilities for computing with codes over Galois rings, including the construction of cyclic codes, the calculation of minimum weight, and the complete weight enumerator. Substantial additional functionality is available for the special case of codes over ℤ4.
For modules defined over rings with zero divisors, the concept of dimension does not exist as the modules are not free. But in Magma each code over such a ring has a unique generator matrix corresponding to the Howell form. The number of rows k in this unique generator matrix will be called the pseudo-dimension of the code. It should be noted that this pseudo-dimension is not invariant with respect to equivalent codes, and so does not play the same role as the dimension of a code over GF(q). The rank of the generator matrix is always well-defined and unique (being based on the Smith form which is well-defined over principal ideal rings (PIRs), but k may sometimes be larger than the rank. Without a concept of dimension, codes over finite rings are referenced by their cardinality. A code C is called an (n,M,d) code if it has length n, cardinality M, and minimum Hamming weight d. In this section, as in the case of codes over finite fields, the term “code” will refer to a linear code unless otherwise specified.
Let R be the Galois ring over which a code C is to be defined; thus C is a submodule of the R-module M = R(n). A basic approach to defining C is to specify a list of generators for C. Just as in the case of codes over finite fields, cyclic codes are an important family of linear codes over finite rings and a number of special constructions are provided. New codes can be formed from an existing code C by extending, padding, shortening, and puncturing C. Codes can also be created by taking two existing codes defined over the same ring R and combining them in some way such as forming their direct sum, direct product, concatenation, Plotkin sum, etc.
Constructions are provided for a number of important families of codes over the ring ℤ4. These include the Kerdock, Preparata, Reed–Muller codes, the Goethals, Delsarte–Goethals, Quadratic Residue codes, the Hadamard code, and the simplex alpha and beta codes. Magma provides functions for constructing three important binary codes which can be derived from a ℤ4-code. Perhaps the most important of these is the binary image of a quaternary code under the Gray map. Functions are also provided that construct codes over ℤ4 obtained by modifying the codewords of an existing code over ℤ4. The main operations are various forms of the Plotkin sum.
The usual basic operations for submodules of M = R(n) are supported for codes C belonging to R(n). In the case in which R = ℤ4, functions are available which compute the image and kernel of C with respect to the Gray map. The image will be a binary linear code while the kernel will be code with parent module M.
In the case of codes over Galois rings, three metrics are used: the Hamming metric, the Lee metric, and the Euclidean metric. For each metric algorithms are provided for computing the minimum weight, the weight distribution, and the dual weight distribution. The minimum weight is computed using a variant of the highly efficient minimum weight algorithm developed for codes over finite fields and so minimum weight can be determined in quite large codes. The weight enumerator, weight distribution, and dual weight distribution can be computed with respect to each of the metrics. The complete weight enumerator is available. For codes over ℤ4 the symmetric weight enumerator can also be computed.
The Octacode is a (8,256,4) code generated by the vectors (1,0,0,0,3,1,2,1), (0,1,0,0,1,2,3,1), (0,0,1,0,3,3,3,2), and (0,0,0,1,2,3,1,1) over ℤ4. The Hamming weight enumerator, the Lee weight enumerator and the Euclidean weight enumerator are, respectively: