On coset weight distributions of the Z4-linear Goethalscodes

We study the coset weight distributions of two well-known families of codes: the three-error-correcting binary Z₄-linear Goethals codes of length N=2^m+1, m⩾3 odd, and the Z₄ -linear Goethals codes over Z₄ of length n=N/2=2^m . The hard case is the weight distributions of cosets of weight 4. To know the weight distribution of the coset of weight 4 we have to know the number of codewords of weight 4 in such a coset. Altogether, there are nine different types of cosets of weight 4. For six cases, we give the exact expressions for the number of codewords of weight 4, and for three other cases, we give such expressions in terms of Kloosterman sums     

On Z4-duality

Recently the notion on binary codes called Z₄-linearity was introduced. This notion explains why Kerdock codes and Delsarte-Goethals codes admit formal duals in spite of their nonlinearity. The “Z₄-duals” of these codes (called “Preparata” and “Goethals” codes) are new nonlinear codes which admit simpler decoding algorithms than the previously known formal duals (the generalized Preparata and Goethals codes). We prove, by using the notion of exact weight enumerator, that the relationship between any Z₄-linear code and its Z₄ -dual is stronger than the standard formal duality and we deduce the weight enumerators of related generalized codes     

On algebraic decoding of the Z4-linear Goethals-likecodes

The Z₄-linear Goethals-like code of length 2^m has 2^2m+1-3m-2 codewords and minimum Lee distance 8 for any odd integer m⩾3. We present an algebraic decoding algorithm for all Z₄-linear Goethals-like codes C_k introduced by Helleseth et al.(1995, 1996). We use Dickson polynomials and their properties to solve the syndrome equations     

Improved estimates via exponential sums for the minimum distance ofZ4-linear trace codes

An upper hound for Weil-type exponential sums over Galois rings was derived by Kumar, Helleseth, and Calderbank (see ibid., vol.41, no.3, p.456, 1995). This bound leads directly to an estimate for the minimum distance of Z₄-linear trace codes. An improved minimum-distance estimate is presented. First, McEliece's result on the divisibility of the weights of binary cyclic codes is extended to Z₄ trace codes. The divisibility result is then combined with the techniques of Serre (1983) and of Moreno and Moreno (see ibid., vol.40, no.11, p.1101, 1994) to derive the improved minimum-distance estimate. The improved estimate is tight for the Kerdock code as well as for the Delsarte-Goethals codes     

Large families of quaternary sequences with low correlation

A family of quaternary (Z₄-alphabet) sequences of length L=2^r-1, size M⩾L²+3L+2, and maximum nontrivial correlation parameter C_max⩽2√(L+1)+1 is presented. The sequence family always contains the four-phase family 𝒜. When r is odd, it includes the family of binary Gold sequences. The sequence family is easily generated using two shift registers, one binary, the other quaternary. The distribution of correlation values is provided. The construction can be extended to produce a chain of sequence families, with each family in the chain containing the preceding family. This gives the design flexibility with respect to the number of intermittent users that can be supported, in a code-division multiple-access cellular radio system. When r is odd, the sequence families in the chain correspond to shortened Z₄-linear versions of the Delsarte-Goethals codes     

Cyclic codes and self-dual codes over F2+uF2

We introduce linear cyclic codes over the ring F₂+uF ₂={0,1,u,u¯=u+1}, where u²=0 and study them by analogy with the Z₄ case. We give the structure of these codes on this new alphabet. Self-dual codes of odd length exist as in the case of Z₄-codes. Unlike the Z₄ case, here free codes are not interesting. Some nonfree codes give rise to optimal binary linear codes and extremal self-dual codes through a linear Gray map     

Cyclic codes over Z4, locator polynomials, and Newton'sidentities

Certain nonlinear binary codes contain more codewords than any comparable linear code presently known. These include the Kerdock (1972) and Preparata (1968) codes that can be very simply constructed as binary images, under the Gray map, of linear codes over Z₄ that are defined by means of parity checks involving Galois rings. This paper describes how Fourier transforms on Galois rings and elementary symmetric functions can be used to derive lower bounds on the minimum distance of such codes. These methods and techniques from algebraic geometry are applied to find the exact minimum distance of a family of Z ₄. Linear codes with length 2^m (m, odd) and size 2(2^m+1-5m-2). The Gray image of the code of length 32 is the best (64, 2³⁷) code that is presently known. This paper also determines the exact minimum Lee distance of the linear codes over Z₄ that are obtained from the extended binary two- and three-error-correcting BCH codes by Hensel lifting. The Gray image of the Hensel lift of the three-error-correcting BCH code of length 32 is the best (64, 2³²) code that is presently known. This code also determines an extremal 32-dimensional even unimodular lattice     

Z4×(F2+uF2)上的一类循环码

定义了Z₄×（F₂+uF₂）上的循环码,明确了一类循环码的生成元结构,给出了该类循环码的极小生成元集.利用Gray映射,构造了一些二元非线性码.     

An Assmus-Mattson theorem for Z4-codes

The Assmus-Mattson theorem is a method to find designs in linear codes over a finite field. The purpose of this paper is to give an analog of this theorem for Z₄-codes by using the harmonic weight enumerator introduced by Bachoc. This theorem can find some 5-designs in the lifted Golay code over Z₄ which were discovered previously by other methods     

Two 16-state, rate R=2/4 trellis codes whose free distances meetthe Heller bound

For rate R=1/2 convolutional codes with 16 states there exists a gap between Heller's (1968) upper bound on the free distance and its optimal value. This article reports on the construction of 16-state, binary, rate R=2/4 nonlinear trellis and convolutional codes having d _free=8; a free distance that meets the Heller upper bound. The nonlinear trellis code is constructed from a 16-state, rate R=1/2 convolutional code over Z₄ using the Gray map to obtain a binary code. Both convolutional codes are obtained by computer search. Systematic feedback encoders for both codes are potential candidates for use in combination with iterative decoding. Regarded as modulation codes for 4-PSK, these codes have free squared Euclidean distance d_{E, free}²=16     

Algebraic construction of cyclic codes over Z8 with agood Euclidean minimum distance

Let S(8) denote the set of the eight admissible signals of an 8PSK communication system. The alphabet S(8) is endowed with the structure of Z₈, the set of integers taken modulo 8, and codes are defined to be Z₈-submodules of Z₈ⁿ. Three cyclic codes over Z₈ are then constructed. Their length is equal to 6, 8, and 7, and they, respectively, contain 64, 64, and 512 codewords. The square of their Euclidean minimum distance is equal to 8, 16-4√2 and 10-2√2, respectively. The size of the codes of length 6 and 7 can be doubled while the Euclidean minimum distance remains the same     

Translates of linear codes over Z4

We give a method to compute the complete weight distribution of translates of linear codes over Z₄. The method follows known ideas that have already been used successfully by others for Hamming weight distributions. For the particular case of quaternary Preparata codes, we obtain that the number of distinct complete weights for the dual Preparata codes and the number of distinct complete coset weight enumerators for the Preparata codes are both equal to ten, independent of the code length     

On the weight hierarchy of Preparata codes over Z4

Hammons et al. (see ibid., vol.40, p.301-19, 1994) showed that, when properly defined, the binary nonlinear Preparata code can be considered as the Gray map of a linear code over Z₄, the so called Preparata code over Z₄. We consider the rth generalized Hamming weight d_r(m) of the Preparata code of length 2^m over Z₄. For any m⩾3, d_r(m) is exactly determined for r=0.5, 1, 1.5, 2, 2.5 and 3.0. For a composite m, we give an upper bound on d_r(m) using the lifting technique. For m=3, 4, 5, 6 and 8, the weight hierarchy is completely determined. In the case of m=7, the weight hierarchy is completely determined except for d₄(7)     

On algebraic decoding of the Z4-linearCalderbank-McGuire code

The quaternary Calderbank-McGuire (see Des., Codes Cryptogr., vol.10, no.2, 1997) code is a Z₄-linear code of length 32 which has 2³⁷ codewords and a minimum Lee distance of 12. The Gray map of this code is known to be a nonlinear binary (64, 2³⁷,12) code. The Z₄-linear Calderbank-McGuire code can correct all errors with Lee weight ⩽5. An algebraic decoding algorithm for the code is presented in this paper. Furthermore, we discuss an alternative decoding method which takes advantage of the efficient BCH decoding algorithm     

Minimal tail-biting trellises: the Golay code and more

Tail-biting trellis representations of block codes are investigated. We develop some elementary theory, and present several intriguing examples, which we hope will stimulate further developments in this field. In particular, we construct a 16-state 12-section structurally invariant tail-biting trellis for the (24, 12, 8) binary Golay code. This tail-biting trellis representation is minimal: it simultaneously minimizes all conceivable measures of state complexity. Moreover, it compares favorably with the minimal conventional 12-section trellis for the Golay code, which has 256 states at its midpoint, or with the best quasi-cyclic representation of this code, which leads to a 64-state tail-biting trellis. Unwrapping this tail-biting trellis produces a periodically time-varying 16-state rate-1/2 “convolutional Golay code” with d=8, which has attractive performance/complexity properties. We furthermore show that the (6, 3, 4) quaternary hexacode has a minimal 8-state group tail-biting trellis, even though it has no such linear trellis over F₄. Minimal tail-biting trellises are also constructed for the (8, 4, 4) binary Hamming code, the (4, 2, 3) ternary tetracode, the (4, 2, 3) code over F₄, and the Z₄-linear (8. 4, 4) octacode     

Quasi-cyclic codes over Z4 and some new binarycodes

Previously, (linear) codes over Z₄ and quasi-cyclic (QC) codes (over fields) have been shown to yield useful results in coding theory. Combining these two ideas we study Z ₄-QC codes and obtain new binary codes using the usual Gray map. Among the new codes, the lift of the famous Golay code to Z₄ produces a new binary code, a (92, 2²⁴, 28)-code, which is the best among all binary codes (linear or nonlinear). Moreover, we characterize cyclic codes corresponding to free modules in terms of their generator polynomials     

The Z4-linearity of Kerdock, Preparata, Goethals, andrelated codes

Certain notorious nonlinear binary codes contain more codewords than any known linear code. These include the codes constructed by Nordstrom-Robinson (1967), Kerdock (1972), Preparata (1968), Goethals (1974), and Delsarte-Goethals (1975). 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₄, 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₄ domain implies that the binary images have dual weight distributions. The Kerdock and “Preparata” codes are duals over Z₄-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₄-analogues of first-order Reed-Muller and extended Hamming codes, respectively. All these codes are extended cyclic codes over Z₄, 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 I(Kerdock code. Binary first- and second-order Reed-Muller codes are also linear over Z₄ , but extended Hamming codes of length n⩾32 and the Golay code are not. Using Z₄-linearity, a new family of distance regular graphs are constructed on the cosets of the “Preparata” code     

Further results on generalized Hamming weights for Goethals andPreparata codes over Z4

This article contains results on the generalized Hamming weights (GHW) for the Goethals and Preparata codes over Z₄. We give an upper bound on the rth generalized Hamming weights d_r(m,j) for the Goethals code G_m(j) of length 2^m over Z ₄, when m is odd. We also determine d_3.5(m,j) exactly. The upper bound is shown to be tight up to r=3.5. Furthermore, we determine the rth generalized Hamming weight d_r(m) for the Preparata code of length 2^m over Z₄ when r=3.5 and r=4     

Quaternary Convolutional Codes From Linear Block Codes Over Galois Rings

From a linear block code B over the Galois ring GR(4, m) with a k times n generator matrix and minimum Hamming distance d, a rate-k/n convolutional code over the ring Z₄ with squared Euclidean free distance at least 2d and a nonrecursive encoder with memory at most m - 1 is constructed. When the generator matrix of B is systematic, the convolutional encoder is systematic, basic, noncatastrophic and minimal. Long codes constructed in this manner are shown to satisfy a Gilbert-Varshnmov bound.     

Z2k-linear codes

We introduce a generalization to Z₂k of the Gray map and generalized versions of Kerdock and Delsarte-Goethals codes