Campopiano-type bounds in non-Hamming array coding

Campopiano [C.N. Campopiano, Bounds on burst error correcting codes, IRE Trans. IT-8 (1962) 257-259] obtained an upper bound for burst error correction in classical coding systems where codes are subsets/subspaces of the space , the space of all n-tuples with entries from a finite field F_q equipped with the Hamming metric. In [S. Jain, Bursts in m-metric array codes, Linear Algebra Appl., in press], the author introduced the notion of burst errors for m-metric array coding systems where m-metric array codes are subsets/subspaces of the space Mat_m×s(F_q), the linear space of all m × s matrices with entries from a finite field F_q, endowed with a non-Hamming metric and obtained some lower bounds for burst error correction. In this paper, we obtain various construction upper bounds on the parameters of m-metric array codes for the detection and correction of burst errors.     

Some constructions of linearly optimal group codes

We continue here the research on (quasi)group codes over (quasi)group rings. We give some constructions of [n,n-3,3]_q-codes over F_q for n=2q and n=3q. These codes are linearly optimal, i.e. have maximal dimension among linear codes having a given length and distance. Although codes with such parameters are known, our main results state that we can construct such codes as (left) group codes. In the paper we use a construction of Reed-Solomon codes as ideals of the group ring F_qG where G is an elementary abelian group of order q.     

CT bursts—from classical to array coding

R.T. Chien and D.T. Tang [On definition of a burst, IBM J. Res. Develop. 9 (1965) 292-293] introduced the concept of Chien and Tang bursts (CT bursts) for classical coding systems where codes are subsets (or subspaces) of the space , the space of all n-tuples with entries from a finite field F_q. In this paper, we extend the notion of CT bursts for array coding systems where array codes are subsets (or subspaces) of the space Mat_m×s(F_q), the linear space of all m×s matrices with entries from a finite field F_q, endowed with a non-Hamming metric [M.Yu. Rosenbloom, M.A. Tsfasman, Codes for m-metric, Problems Inform. Transmission 33 (1997) 45-52]. We also obtain some bounds on the parameters of array codes for the detection and correction of CT burst errors.     

Lower bounds for codes correcting moderate-density bursts of fixed length with Lee weight consideration

Lee weight is more appropriate for some practical situations than Hamming weight as it takes into account magnitude of each digit of the word. In this paper, considering Lee weight, we obtain necessary lower bound over the number of parity checks to correct bursts of length b (fixed) whose weight lies between certain limits. We also obtain Lee weight bound for such type of moderate-density bursts with limited intensity.     

Determining all indecomposable codes over some Hopf algebras

We determine all indecomposable codes over a class of Hopf algebras named Taft Algebras. We calculate dual codes and tensor products of these indecomposable codes and give applications of them.     

Defining sets of extended cyclic codes invariant under the affine group

We describe the defining sets of extended cyclic codes of length pⁿ over a field and over the ring of integers modulo p^e admitting the affine group AGL_m(p^t), n=mt, as a permutation group.     

Density of constant radius normal binary covering codes

A binary code with covering radius R is a subset C of the hypercube Q_n={0,1}ⁿ such that every x∈Q_n is within Hamming distance R of some codeword c∈C, where R is as small as possible. For a fixed coordinate i∈[n], define to be the set of codewords with a b in the ith position. Then C is normal if there exists an i∈[n] such that for any v∈Q_n, the sum of the Hamming distances from v to and is at most 2R+1. We newly define what it means for an asymmetric covering code to be normal, and consider the worst-case asymptotic densities ν^*(R) and of constant radius R symmetric and asymmetric normal covering codes, respectively. Using a probabilistic deletion method, and analysis adapted from previous work by Krivelevich, Sudakov, and Vu, we show that and , giving evidence that minimum size constant radius covering codes could still be normal.     

A new class of superregular matrices and MDP convolutional codes

This paper deals with the problem of constructing superregular matrices that lead to MDP convolutional codes. These matrices are a type of lower block triangular Toeplitz matrices with the property that all the square submatrices that can possibly be nonsingular due to the lower block triangular structure are nonsingular. We present a new class of matrices that are superregular over a sufficiently large finite field F$\mathbb{F}$. Such construction works for any given choice of characteristic of the field F$\mathbb{F}$ and code parameters (n,k,δ)$(n,k,\delta )$ such that (n−k)|δ$(n-k)|\delta$. We also discuss the size of F$\mathbb{F}$ needed so that the proposed matrices are superregular.     

On the non-existence of linear codes attaining the Griesmer bound

A lower bound on the size of a set K in PG(3, q) satisfying for any plane of PG(3, q), q4 is given. It induces the non-existence of linear [n,4,n + 1 – q ²]-codes over GF(q) attaining the Griesmer bound for .     

Characterizations of pseudo-codewords of (low-density) parity-check codes

An important property of low-density parity-check codes is the existence of highly efficient algorithms for their decoding. Many of the most efficient, recent graph-based algorithms, e.g. message-passing iterative decoding and linear programming decoding, crucially depend on the efficient representation of a code in a graphical model. In order to understand the performance of these algorithms, we argue for the characterization of codes in terms of a so-called fundamental cone in Euclidean space. This cone depends upon a given parity-check matrix of a code, rather than on the code itself. We give a number of properties of this fundamental cone derived from its connection to unramified covers of the graphical models on which the decoding algorithms operate. For the class of cycle codes, these developments naturally lead to a characterization of the fundamental cone as the Newton polyhedron of the Hashimoto edge zeta function of the underlying graph.     

An upper bound for the minimum weight of dual codes of Figueroa planes

In this note we give an explicit construction for words of weight 2q³ - q² - q in the dual p-ary code of the Figueroa plane of order q³, where q > 2 is any power of the prime p. When p is odd this then allows us, for the Figueroa planes, to improve on the previously known upper bound of 2q³ for the minimum weight of the dual p-ary code of any plane of order q³. The construction is the same as one that applies to desarguesian planes of order q³ as described in [3].     

Classification of convolutional codes

Convolutional codes have the structure of an F[z]-module. To study their properties it is desirable to classify them as the points of a certain algebraic variety. By considering the correspondence of submodules and the points of certain quotient schemes, and the inclusion of these as subvarieties of certain Grassmannians, one has a one-to-one correspondence of convolutional codes and the points of these subvarieties. This classification of convolutional codes sheds light on their structure and proves to be helpful to give bounds on their free distance and to define convolutional codes with good parameters.     

Further improvements on the designed minimum distance of algebraic geometry codes

In the literature about algebraic geometry codes one finds a lot of results improving Goppa’s minimum distance bound. These improvements often use the idea of “shrinking” or “growing” the defining divisors of the codes under certain technical conditions. The main contribution of this article is to show that most of these improvements can be obtained in a unified way from one (rather simple) theorem. Our result does not only simplify previous results but it also improves them further.     

A Characterization of Designs Related to an Extremal Doubly-Even Self-Dual Code of Length 48

The uniqueness of a binary doubly-even self-dual [48, 24, 12] code is used to prove that a self-orthogonal 5-(48, 12, 8) design, as well as some of its derived and residual designs, including a quasi-symmetric 2-(45, 9, 8) design, are all unique up to isomorphism.Received November 5, 2003     

Partial permutation decoding for codes from affine geometry designs

We find explicit PD-sets for partial permutation decoding of the generalized Reed-Muller codes from the affine geometry designs of points and lines in dimension 3 over the prime field of order p, using the information sets found in [8]. This work was supported by the DoD Multidisciplinary University Research Initiative (MURI) program administered by the Office of Naval Research under Grant N00014-00-1-0565.     

Explicit constructions of graphs without short cycles and low density codes

We give an explicit construction of regular graphs of degree 2r withn vertices and girth ≧c logn/logr. We use Cayley graphs of factor groups of free subgroups of the modular group. An application to low density codes is given.     

Weight distribution of translates of MDS codes

The following is a particular case of a theorem of Delsarte: the weight distribution of a translate of an MDS code is uniquely determined by its firstn–k terms. Here an explicit formula is derived from a completely different approach.     

Riemann-Roch spaces of the Hermitian function field with applications to algebraic geometry codes and low-discrepancy sequences

This paper is concerned with two applications of bases of Riemann-Roch spaces. In the first application, we define the floor of a divisor and obtain improved bounds on the parameters of algebraic geometry codes. These bounds apply to a larger class of codes than that of Homma and Kim (J. Pure Appl. Algebra 162 (2001) 273). Then we determine explicit bases for large classes of Riemann-Roch spaces of the Hermitian function field. These bases give better estimates on the parameters of a large class of m-point Hermitian codes. In the second application, these bases are used for fast implementation of Xing and Niederreiter's method (Acta. Arith. 72 (1995) 281) for the construction of low-discrepancy sequences.     

The classification of self-dual modular codes

A classification method of self-dual codes over Zm is given. If m=rs with relatively prime integers r and s, then the classification can be accomplished by double coset decompositions of Sn by automorphism groups of self-dual codes over Zr and Zs. We classify self-dual codes of length 4 over Zp for all primes p in terms of their automorphism groups and then apply our method to classify self-dual codes over Zm for arbitrary integer m. Self-dual codes of length 8 are also classified over Zpq for p,q=2,3,5,7.     

Maximal order codes over number fields

We present constructions of codes obtained from maximal orders over number fields. Particular cases include codes from algebraic number fields by Lenstra and Guruswami, codes from units of the ring of integers of number fields, and codes from both additive and multiplicative structures of maximal orders in central simple division algebras. The parameters of interest are the code rate and the minimum Hamming distance. An asymptotic study reveals several families of asymptotically good codes.