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.     

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.     

Dual codes of systematic group codes over abelian groups

For systematic codes over finite fields the following result is well known: If [I∣P] is the generator matrix then the generator matrix of its dual code is The main result is a generalization of this for systematic group codes over finite abelian groups. It is shown that given the endomorphisms which characterize a group code over an abelian group, the endomorphisms which characterize its dual code are identified easily. The self-dual codes are also characterized. It is shown that there are self-dual and MDS group codes over elementary abelian groups which can not be obtained as linear codes over finite fields. Received March 7, 1995; revised version April 3, 1996     

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.     

Improved Bounds for Quaternary Linear Codes of Dimension 6

In this paper, twenty new codes of dimension 6 are presented which give improved bounds on the maximum possible minimum distance of quaternary linear codes. These codes belong to the class of quasi-twisted (QT) codes, and have been constructed using a stochastic optimization algorithm, tabu search. A table of upper and lower bounds for d ⁴(n,6) is presented for n≤ 200. Received: 20 December 1996 / Accepted: 13 May 1997     

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.     

On the Extendibility of Near-MDS Elliptic Codes

The Main Conjecture on maximum distance separable (MDS) codes states that, except for some special cases, the maximum length of a q-ary linear MDS code of is q+1. This conjecture does not hold true for near maximum distance separable codes because of the existence of q-ary near-MDS elliptic codes having length bigger than q+1. An interesting related question is whether a near-MDS elliptic code may be extended to a longer near-MDS code. In this paper we prove some non-extendibility results for certain near-MDS elliptic codes.     

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.     

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     

On the Concatenated Structure of a Linear Code

We address here the problem of finding a concatenated structure in a linear code ? given by its generating matrix, that is, if ? is equivalent to the concatenation of an inner code B ₀ and an outer code E ₀, then find two codes B and E such that their concatenation is equivalent to ?. If the concatenated structure exists and is non trivial (i.e. the inner code B is non trivial), the dual distance of ? is equal to the dual distance of B. If this dual distance is small enough to allow the computation of many small weight words in the dual of ?, it is possible to recover first an inner code B, then an outer code E whose concatenation is equivalent to ?. These two codes are equivalent respectively to the original inner and outer codes B ₀ and E ₀.     

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.     

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.     

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.     

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     

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.     

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     

On the Equivalence of Codes over Finite Rings

It is known that if a finite ring R is Frobenius then equivalences of linear codes over R are always monomial transformations. Among other results, in this paper we show that the converse of this result holds for finite local and homogeneous semilocal rings. Namely, it is shown that for every finite ring R which is a direct sum of local and homogeneous semilocal subrings, if every Hamming-weight preserving R-linear transformation of a codeC₁ onto a code C₂ is a monomial transformation then R is a Frobenius ring.Partially supported by Center of Ring Theory and Applications, Ohio University.     

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     

Generalized quasi-cyclic codes: structural properties and code construction

Generalized quasi-cyclic (GQC) codes are defined by generator matrices comprised of circulant matrices of lengths not necessarily identical. A decomposition of these codes is given by using the Chinese reminder theorem. The focus is to characterize ρ-generator GQC codes in details. A good lower bound on the minimum distance of such a code in terms of the minimum distance of the constituent codes is given. Construction methods are given and a set of GQC codes is provided that from minimum distance perspective are optimal codes among the known linear codes having the same length and dimension.     

On liouvillian solutions of linear differential equations

This paper deals with the problem of finding liouvillian solutions of a homogeneous linear differential equationL(y)=0 of ordern with coefficients in a differential fieldk. For second order linear differential equations with coefficients ink _o(x), wherek _o is a finite algebraic extension ofQ, such an algorithm has been given by J. Kovacic and implemented. A general decision procedure for finding liouvillian solutions of a differential equation of ordern has been given by M.F. Singer, but the resulting algorithm, although constructive, is not in implementable form even for second order equations. Both algorithms use the fact that, ifL(y)=0 has a liouvillian solution, then,L(y)=0 has a solutionz such thatu=z/z is algebraic overk. Using the action of the differential galois group onu and the theory of projective representation we get sharp bounds (n) for the algebraic degree ofu for differential equations of arbitrary ordern. For second order differential equations we get the bound (2)=12 used in the algorithm of J. Kovacic and for third order differential equation we improve the bound given by M.F. Singer from 360 to (3)36. We also show that not all values less than or equal to (n) are possible values for the algebraic degree ofu. For second order differential equations we rediscover the values 2, 4, 6, and 12 used in the Kovacic Algorithm and for third order differential equations we get the possibilities 3,4, 6, 7, 9, 12, 21, and 36. We prove that if the differential Galois group ofL(y)=0 is a primitive unimodular linear group, then all liouvillian solutions are algebraic. From this it follows that, if a third order differential equationL(y)=0 is not of Fuchsian type, then the logarithmic derivative of some liouvillian solution ofL(y)=0 is algebraic of degree 3. We also derive an upper bound for the minimal numberN(n) of possible degreesm of the minimal polynomial of an algebraic solution of the riccati equation associated withL(y)=0.Supported by Deutsche Forschungsgemeinschaft while visiting North Carolina State University