Bounds and constructions of asymmetric or unidirectional error-correcting codes

Binary block codes for correctingt symmetric, asymmetric and unidirectional errors are calledt-SyEC codes,t-AsEC codes andt-UEC codes respectively. Two tables with bounds on the cardinality of binary block codes for correcting asymmetric and unidirectional errors respectively are presented. They include many improvements over the existing literature. The lower bounds follow from explicit constructions, while the upper bounds are obtained by applying combinatorial arguments to the weight structure of such codes.The authors are with Department of Mathematics and Computing Science of Eindhoven University of Technology, The Netherlands. Part of this work was presented at the IEEE International Symposium on Information Theory, Budapest, 1991     

1-Perfect Uniform and Distance Invariant Partitions

Let F ⁿ be the n-dimensional vector space over ℤ₂. A (binary) 1-perfect partition of F ⁿ is a partition of F ⁿ into (binary) perfect single error-correcting codes or 1-perfect codes. We define two metric properties for 1-perfect partitions: uniformity and distance invariance. Then we prove the equivalence between these properties and algebraic properties of the code (the class containing the zero vector). In this way, we characterize 1-perfect partitions obtained using 1-perfect translation invariant and not translation invariant propelinear codes. The search for examples of 1-perfect uniform but not distance invariant partitions enabled us to deduce a non-Abelian propelinear group structure for any Hamming code of length greater than 7. Received: March 6, 2000; revised version: November 30, 2000     

The Minimal Generator Matrix of a Vector Space

The atomic vectors of a finitely generated vector space C over a field F are characterized for C a subspace of the product vector space ? = ∏ _{i =1} ⁿ ? _i over F. For finite fields, the minimal trellis diagram for mixed-codes is determined, and this provides the L-section minimal trellis diagram for linear codes. As an example, an extremely simple yet comprehensive analysis of the trellis structure of Reed-Muller codes is given. In particular, a trellis oriented generator matrix for the 2 ^l -section minimal trellis diagram of a Reed-Muller code is presented. Received: February 27, 1997; revised version: May 6, 1999     

Toric Codes over Finite Fields

In this note, a class of error-correcting codes is associated to a toric variety defined over a finite field _q, analogous to the class of AG codes associated to a curve. For small q, many of these codes have parameters beating the Gilbert-Varshamov bound. In fact, using toric codes, we construct a (n,k,d)=(49,11,28) code over ₈, which is better than any other known code listed in Brouwers tables for that n, k and q. We give upper and lower bounds on the minimum distance. We conclude with a discussion of some decoding methods. Many examples are given throughout.     

Maximum Distance Separable Convolutional Codes

A maximum distance separable (MDS) block code is a linear code whose distance is maximal among all linear block codes of rate k/n. It is well known that MDS block codes do exist if the field size is more than n. In this paper we generalize this concept to the class of convolutional codes of a fixed rate k/n and a fixed code degree δ. In order to achieve this result we will introduce a natural upper bound for the free distance generalizing the Singleton bound. The main result of the paper shows that this upper bound can be achieved in all cases if one allows sufficiently many field elements. Received: December 10, 1998; revised version: May 14, 1999     

Bounds on Minimum Distance for Linear Codes over GF(5)

Let [n, k, d; q]-codes be linear codes of length n, dimension k and minimum Hamming distance d over GF(q). Let d ₅(n, k) be the maximum possible minimum Hamming distance of a linear [n, k, d; 5]-code for given values of n and k. In this paper, forty four new linear codes over GF(5) are constructed and a table of d ₅(n, k) k≤ 8, n≤ 100 is presented.     

Metacyclic error-correcting codes

Error-correcting codes which are ideals in group rings where the underlying group is metacyclic and non-abelian are examined. Such a groupG(M, N,R) is the extension of a finite cyclic group _M by a finite cyclic group _N and has a presentation of the form (S, T:S ^M =1,T ^N =1, T· S=S ^R ·T) where gcd(M, R)=1, R ^N =1 modM, R 1. Group rings that are semi-simple, i.e., where the characteristic of the field does not divide the order of the group, are considered. In all cases, the field of the group ring is of characteristic 2, and the order ofG is odd.Algebraic analysis of the structure of the group ring yields a unique direct sum decomposition ofFG(M, N, R) to minimal two-sided ideals (central codes). In every case, such codes are found to be combinatorically equivalent to abelian codes and of minimum distance that is not particularly desirable. Certain minimal central codes decompose to a direct sum ofN minimal left ideals (left codes). This direct sum is not unique. A technique to vary the decomposition is described. p]Metacyclic codes that are one-sided ideals were found to display higher minimum distances than abelian codes of comparable length and dimension. In several cases, codes were found which have minimum distances equal to that of the best known linear block codes of the same length and dimension.     

Two “Dual” Families of Nearly-Linear Codes over ℤ p , p odd

Since the paper by Hammons e.a. [1], various authors have shown an enormous interest in linear codes over the ring ℤ₄. A special weight function on ℤ₄ was introduced and by means of the so called Gray map ϕ : ℤ₄→ℤ₂ ² a relation was established between linear codes over ℤ₄ and certain interesting non-linear binary codes of even length. Here, we shall generalize these notions to codes over ℤ _p2 where p is an arbitrary prime. To this end, a new weight function will be proposed for ℤ _p2 . Further, properties of linear codes over ℤ _p2 will be discussed and the mapping ϕ will be generalized to an isometry between ℤ _p2 and ℤ _p ^p , resp. between ℤ _p2 ⁿ and ℤ _p ^pn . Some properties of Galois rings over ℤ _q will be described and two dual families of linear codes of length n = p ^m − 1, gcd(m, p) = 1, over ℤ _q will be constructed. Taking q = p ², their images under the new mapping can be viewed as a generalization of the binary Kerdock and the Preparata code, although they miss some of their nice combinatorial properties. Received: June 19, 2000; revised version: November 6, 2000     

The number of MDS [7, 3] codes on finite fields of characteristic 2

A code of lengthn, dimensionk and minimum distanced ismaximum distance separable (MDS) ifk+d=n+1. We give the number of MDS codes of length 7 and dimension 3 on finite fields withq elements whereq=2 ^m . In order to get this number, we compute the number of configurations of seven points in the projective plane overF _q , no three of which are collinear.     

Maximal AMDS codes

Complete (n, k)-arcs in PG(k − 1, q) and projective (n, k) _q -AMDS codes that admit no projective extensions are equivalent objects. We show that projective AMDS codes of reasonable length admit only linear extensions. Thus, we are able to prove the maximality of many known linear AMDS codes. At the same time our results sharply limit the possibilities for constructing long nonlinear AMDS codes. We also show that certain short linear AMDS codes are maximal. Central to our approach is the Bruen–Silverman model of linear codes first introduced in Alderson (On MDS codes and Bruen–Silverman codes. Ph.D. Thesis, University of Western Ontario, 2002) and Alderson et al. (J. Combin. Theory Ser. A 114(6), 1101–1117, 2007). The authors acknowledge support from the N.S.E.R.C. of Canada.     

Group codes on certain algebraic curves with many rational points

We construct a series of algebraic geometric codes using a class of curves which have many rational points. We obtain codes of lengthq ² over _q , whereq = 2q ₀ ² andq ₀ = 2 ⁿ , such that dimension + minimal distance q ² + 1 – q ₀ (q – 1). The codes are ideals in the group algebra _q [S], whereS is a Sylow-2-subgroup of orderq ² of the Suzuki-group of orderq ² (q ² + 1)(q – 1). The curves used for construction have in relation to their genera the maximal number of GF _q -rational points. This maximal number is determined by the explicit formulas of Weil and is effectively smaller than the Hasse—Weil bound.Supported by Deutsche Forschungsgemeinschaft while visiting Essen University     

Structural properties and enumeration of quasi cyclic codes

Given any finite fieldF _q , an (N, K) quasi cyclic code is defined as aK dimensional linear subspace ofF _q ^N which is invariant underT ⁿ for some integern, 0 <n N, and whereT is the cyclic shift operator. Quasi cyclic codes are shown to be isomorphic to theF _q []-submodules ofF _q ^N where the product(gl)· is naturally defined as ₀ + ₁T ⁿ +...+ _m T ^mn if()= ₀ + ₁ +...+ _{m m} .In the case where (N/n, q)=1, all quasi cyclic codes are shown to be decomposable into the direct sum of a fixed number of indecomposable components called irreducible cyclicF _q []-submodules providing for the complete characterisation and enumeration of some subclasses of quasi cyclic codes including the cyclic codes, the quasi cyclic codes with a cyclic basis, the maximal and the irreducible ones. Finally a general procedure is presented which allows for the determination and characterisation of the dual of any quasi cyclic code.     

Transform domain characterization of cyclic codes overZ m

Cyclic codes with symbols from a residue class integer ringZ _m are characterized in terms of the discrete Fourier transform (DFT) of codewords defined over an appropriate extension ring ofZ _m . It is shown that a cyclic code of length n overZ _m ,n relatively prime tom, consists ofn-tuples overZ _m having a specified set of DFT coefficients from the elements of an ideal of a subring of the extension ring. Whenm is equal to a product of distinct primes every cyclic code overZ _m has an idempotent generator and it is shown that the idempotent generators can be easily identified in the transform domain. The dual code pairs overZ _m are characterized in the transform domain for cyclic codes. Necessary and sufficient conditions for the existence of self-dual codes overZ _m are obtained and nonexistence of self-dual codes for certain values ofm is proved.     

Duadic Codes over F2 + uF2

Duadic codes over F ₂ + u F ₂ are introduced as abelian codes by their zeros. This is the function field analogue of duadic codes over Z ₄ introduced recently by Langevin and Solé. They produce binary self-dual codes via a suitable Gray map. Their binary images are themselves abelian, thus generalizing a result of van Lint for cyclic binary codes of even length. We classify them in modest lengths and exhibit interesting non-cyclic examples. Received: April 26, 2000; revised version: May 5, 2001     

Optimal Formally Self-Dual Codes over ?5 and ?7

In this paper, we study optimal formally self-dual codes over ?₅ and ?₇. We determine the highest possible minimum weight for such codes up to length 24. We also construct formally self-dual codes with highest minimum weight, some of which have the highest minimum weight among all known linear codes of corresponding length and dimension. In particular, the first known [14, 7, 7] code over ?₇ is presented. We show that there exist formally self-dual codes which have higher minimum weights than any comparable self-dual codes. Received: May 18, 1998; revised version: September 4, 1999     

Bounds on the minimum distance of the duals of extended BCH codes over\mathbb{F}_p

LetC be an extended cyclic code of lengthp ^m over . The border ofC is the set of minimal elements (according to a partial order on [0,p ^m –1]) of the complement of the defining-set ofC. We show that an affine-invariant code whose border consists of only one cyclotomic coset is the dual of an extended BCH code if, and only if, this border is the cyclotomic coset, sayF(t, i), ofp ^t –1–i, with 1 t m and 0 i < p–1. We then study such privileged codes. We first make precize which duals of extendedBCH codes they are. Next, we show that Weil's bound in this context gives an explicit formula; that is, the couple (t, i) fully determines the value of the Weil bound for the code with borderF(t, i). In the case where this value is negative, we use the Roos method to bound the minimum distance, greatly improving the BCH bound.     

On a signal processing algorithms based class of linear codes

In this work, the correspondence between linear (n,k,d) codes and aperiodic convolution algorithms for computing a system ofk bilinear forms over GF(p^m) is explored. A number of properties are established for the linear codes that can be obtained from a computational procedure of this type. A particular bilinear form is considered and a class of linear codes over GF(2^m) is derived with varyingk andd parameters. The code lengthn is equal to the multiplicative complexity of the computation of an aperiodic convolution and an efficient computation thereof leads to the shortest codes possible using this approach, many of which are optimal or near-optimal. A new decoding procedure for this class of linear codes is presented which exploits the block structure of the generator matrix of the codes. Several interesting observations are made on the nature of the codes obtained as a result of such computations. Such a computation of bilinear forms can be generalized to include other bilinear forms and the related classes of codes.     

Linear codes with balanced weight distribution

In this paper, we study particular linear codes defined overF _q , with an astonishing property, their weight distribution is balanced, i.e. there is the same number of codewords for each nonzero weight of the code. We call these codesBWD-codes. We first study BWD-codes by means of the Pless identities and we completely characterize the two-weight projective case. We study the class of codes defined under subgroups of the multiplicative group ofF _q ^s , using the Gauss sums. Then, given a primep and an integerN dividingp – 1, we construct all theN-weight BWD-codes of that class. We conclude this paper by some tables of BWD-codes and an open problem.     

Reed-Muller Codes on Complete Intersections

By using results and techniques from commutative algebra such as the vanishing ideal of a set of points, its a-invariant, the Hilbert polynomial and series, as well as finite free resolutions and the canonical module, some results about Reed-Muller codes defined on a zero-dimensional complete intersection in the n-projective dimensional space are given. Several examples of this class of codes are presented in order to illustrate the ideas. Received: March 11, 1999; revised version: November 6, 2000     

Weight distribution and dual distance

Several results in coding theory (e.g. the Carlitz-Uchiyama bound) show that the weight distributions of certain algebraic codes of lengthn are concentrated aroundn/2 within a range of width n. It is proved in this article that the extreme weights of a linear binary code of sufficiently high dual distance cannot be too close ton/2, the gap being of order n. The tools used involve the Pless identities and the orthogonality properties of Krawtchouk polynomials, as well as estimates on their zeroes. As a by-product upper bounds on the minimum distance of self-dual binary codes are derived.