A generalized Gleason–Pierce–Ward theorem

The Gleason–Pierce–Ward theorem gives constraints on the divisor and field size of a linear divisible code over a finite field whose dimension is half of the code length. This result is a departure point for the study of self-dual codes. In recent years, additive codes have been studied intensively because of their use in additive quantum codes. In this work, we generalize the Gleason–Pierce–Ward theorem on linear codes over GF(q), q = p ^m , to additive codes over GF(q). The first step of our proof is an application of a generalized upper bound on the dimension of a divisible code determined by its weight spectrum. The bound is proved by Ward for linear codes over GF(q), and is generalized by Liu to any code as long as the MacWilliams identities are satisfied. The trace map and an analogous homomorphism on GF(q) are used to complete our proof.      

A family of 2-weight codes related to BCH-codes

For every prime-power q and every pair of natural numbers m ≤ n′, we construct a q-ary linear code of length q^m (q^n′ − 1)(q^n′ − q^n′−m + 1)/(q − 1) and dimension 3n′, whose only nonzero weights are and . These code parameters and those of the corresponding family of strongly regular graphs are new in odd characteristic. © 1997 John Wiley & Sons, Inc. J Combin Designs 5: 391–396, 1997     

The weight distributions of irreducible cyclic codes of length

Let m be a positive integer and q be an odd prime power. In this paper, the weight distributions of all the irreducible cyclic codes of length 2^m over F_q are determined explicitly.     

Schubert unions in Grassmann varieties

We study subsets of Grassmann varieties G(l,m) over a field F, such that these subsets are unions of Schubert cycles, with respect to a fixed flag. We study unions of Schubert cycles of Grassmann varieties G(l,m) over a field F. We compute their linear span and, in positive characteristic, their number of F_q-rational points. Moreover, we study a geometric duality of such unions, and give a combinatorial interpretation of this duality. We discuss the maximum number of F_q-rational points for Schubert unions of a given spanning dimension, and as an application to coding theory, we study the parameters and support weights of the well-known Grassmann codes. Moreover, we determine the maximum Krull dimension of components in the intersection of G(l,m) and a linear space of given dimension in the Plücker space.     

Constructions and bounds on linear error-block codes

We obtain new bounds on the parameters and we give new constructions of linear error-block codes. We obtain a Gilbert–Varshamov type construction. Using our bounds and constructions we obtain some infinite families of optimal linear error-block codes over . We also study the asymptotic of linear error-block codes. We define the real valued function α _q,m,a (δ), which is an analog of the important real valued function α _q (δ) in the asymptotic theory of classical linear error-correcting codes. We obtain both Gilbert–Varshamov and algebraic geometry type lower bounds on α _q,m,a (δ). We compare these lower bounds in graphs.      

The Classification of Some Perfect Codes

Perfect 1-error correcting codes C in Z ₂ ⁿ , where n=2 ^m–1, are considered. Let ; denote the linear span of the words of C and let the rank of C be the dimension of the vector space . It is shown that if the rank of C is n–m+2 then C is equivalent to a code given by a construction of Phelps. These codes are, in case of rank n–m+2, described by a Hamming code H and a set of MDS-codes D _h , h H, over an alphabet with four symbols. The case of rank n–m+1 is much simpler: Any such code is a Vasil'ev code.     

Construction of a (64, 2 37, 12) Code via Galois Rings

Certain nonlinear binary codes contain more codewords than any comparable linear code presently known. These include the Kerdock and Preparata codes, which exist for all lengths 4^m 16. At length 16 they coincide to give the Nordstrom-Robinson code. This paper constructs a nonlinear (64, 2₃₇, 12) code as the binary image, under the Gray map, of an extended cyclic code defined over the integers modulo 4 using Galois rings. The Nordstrom-Robinson code is defined in this same way, and like the Nordstrom-Robinson code, the new code is better than any linear code that is presently known.     

A coding problem in steganography

To study how to design a steganographic algorithm more efficiently, a new coding problem—steganographic codes (abbreviated stego-codes)—is presented in this paper. The stego-codes are defined over the field with q(q ≥ 2) elements. A method of constructing linear stego-codes is proposed by using the direct sum of vector subspaces. And the problem of linear stego-codes is converted to an algebraic problem by introducing the concept of the tth dimension of a vector space. Some bounds on the length of stego-codes are obtained, from which the maximum length embeddable (MLE) code arises. It is shown that there is a corresponding relation between MLE codes and perfect error-correcting codes. Furthermore the classification of all MLE codes and a lower bound on the number of binary MLE codes are obtained based on the corresponding results on perfect codes. Finally hiding redundancy is defined to value the performance of stego-codes.      

Subcodes of the Projective Generalized Reed-Muller Codes Spanned by Minimum-Weight Vectors

We use methods of Mortimer [19] to examine the subcodes spanned by minimum-weight vectors of the projective generalized Reed-Muller codes and their duals. These methods provide a proof, alternative to a dimension argument, that neither the projective generalized Reed-Muller code of order r and of length over the finite field F _q of prime-power order q, nor its dual, is spanned by its minimum-weight vectors for 0<r<m–1 unless q is prime. The methods of proof are the projective analogue of those developed in [17], and show that the codes spanned by the minimum-weight vectors are spanned over F _q by monomial functions in the m variables. We examine the same question for the subfield subcodes and their duals, and make a conjecture for the generators of the dual of the binary subfield subcode when the order r of the code is 1.     

Reed-Muller codes and Barnes-Wall lattices: Generalized multilevel constructions and representation over GF(2<Superscript><Emphasis Type="Italic">q</Emphasis></Superscript>)

Generalized multilevel constructions for binary RM(r,m) codes using projections onto GF(2 ^q ) are presented. These constructions exploit component codes over GF(2), GF(4),..., GF(2 ^q ) that are based on shorter Reed-Muller codes and set partitioning using partition chains of length-2 ^l codes. Using these constructions we derive multilevel constructions for the Barnes-Wall Λ(r,m) family of lattices which also use component codes over GF(2), GF(4),..., GF(2 ^q ) and set partitioning based on partition chains of length-2 ^l lattices. These constructions of Reed-Muller codes and Barnes-Wall lattices are readily applicable for their efficient decoding.      

An Extension Theorem for Linear Codes

One of the first results one meets in coding theory is that a binary linear [n,k,d] code, whose minimum distance is odd, can be extended to an [n + 1, k, d + 1] code. This is one of the few elementary results about binary codes which does not obviously generalise to q-ary codes. The aim of this paper is to give a simple sufficient condition for a q-ary [n, k, d] code to be extendable to an [n + 1, k, d + 1] code. Applications will be given to the construction and classification of good codes, to proving the non- existence of certain codes, and also an application in finite geometry.     

On the reconstruction of linear codes

For a linear code over GF(q) we consider two kinds of “subcodes” called residuals and punctures. When does the collection of residuals or punctures determine the isomorphism class of the code? We call such a code residually or puncture reconstructible. We investigate these notions of reconstruction and show that, for instance, selfdual binary codes are puncture and residually reconstructible. A result akin to the edge reconstruction of graphs with sufficiently many edges shows that a code whose dimension is small in relation to its length is puncture reconstructible. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 285–291, 1998     

Negacyclic duadic codes

This paper extends the concepts from cyclic duadic codes to negacyclic codes over F_q (q an odd prime power) of oddly even length. Generalizations of defining sets, multipliers, splittings, even-like and odd-like codes are given. Necessary and sufficient conditions are given for the existence of self-dual negacyclic codes over F_q and the existence of splittings of 2N, where N is odd. Other negacyclic codes can be extended by two coordinates in a way to create self-dual codes with familiar parameters.     

Coding‐theoretic constructions for (t,m,s)‐nets and ordered orthogonal arrays

(t,m,s)‐nets are point sets in Euclidean s‐space satisfying certain uniformity conditions, for use in numerical integration. They can be equivalently described in terms of ordered orthogonal arrays, a class of finite geometrical structures generalizing orthogonal arrays. This establishes a link between quasi‐Monte Carlo methods and coding theory. The ambient space is a metric space generalizing the Hamming space of coding theory. We denote it by NRT space (named after Niederreiter, Rosenbloom and Tsfasman). Our main results are generalizations of coding‐theoretic constructions from Hamming space to NRT space. These comprise a version of the Gilbert‐Varshamov bound, the (u,u+υ)‐construction and concatenation. We present a table of the best known parameters of q‐ary (t,m,s)‐nets for qε{2,3,4,5} and dimension m≤50. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 403–418, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10015     

On the maximality of linear codes

We show that if a linear code admits an extension, then it necessarily admits a linear extension. There are many linear codes that are known to admit no linear extensions. Our result implies that these codes are in fact maximal. We are able to characterize maximal linear (n, k, d) _q -codes as complete (weighted) (n, n − d)-arcs in PG(k − 1, q). At the same time our results sharply limit the possibilities for constructing long non-linear codes. The central ideas to our approach are the Bruen-Silverman model of linear codes, and some well known results on the theory of directions determined by affine point-sets in PG(k, q).      

Skew codes of prescribed distance or rank

In this paper we generalize the notion of cyclic code and construct codes as ideals in finite quotients of non-commutative polynomial rings, so called skew polynomial rings of automorphism type. We propose a method to construct block codes of prescribed rank and a method to construct block codes of prescribed distance. Since there is no unique factorization in skew polynomial rings, there are much more ideals and therefore much more codes than in the commutative case. In particular we obtain a [40, 23, 10]₄ code by imposing a distance and a [42,14,21]₈ code by imposing a rank, which both improve by one the minimum distance of the previously best known linear codes of equal length and dimension over those fields. There is a strong connection with linear difference operators and with linearized polynomials (or q-polynomials) reviewed in the first section.      

On Intersection Problem for Perfect Binary Codes

The main result is that to any even integer q in the interval 0 ≤ q ≤ 2^{n+1-2log(n+1)}, there are two perfect codes C₁ and C₂ of length n = 2^m − 1, m ≥ 4, such that |C₁ ∩ C₂| = q.     

Kernels and <Emphasis Type="Italic">p</Emphasis>-Kernels of <Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">r</Emphasis></Superscript>-ary 1-Perfect Codes

The rank of a q-ary code C is the dimension of the subspace spanned by C. The kernel of a q-ary code C of length n can be defined as the set of all translations leaving C invariant. Some relations between the rank and the dimension of the kernel of q-ary 1-perfect codes, over as well as over the prime field , are established. Q-ary 1-perfect codes of length n=(q^m − 1)/(q − 1) with different kernel dimensions using switching constructions are constructed and some upper and lower bounds for the dimension of the kernel, once the rank is given, are established.Communicated by: I.F. Blake     

On nonsystematic perfect codes over finite fields

The nonsystematic perfect q-ary codes over finite field F _q of length n = (q ^m − 1)/(q − 1) are constructed in the case when m ≥ 4 and q ≥ 2 and also when m = 3 and q is not prime. For q ≠ 3, 5, these codes can be constructed by switching seven disjoint components of the Hamming code H _q ⁿ ; and, for q = 3, 5, eight disjoint components.     

Fq-linear Cyclic Codes over $$ F{_q^m}$$ : D FT Approach

Codes over that are closed under addition, and multiplication with elements from F_q are called F_q-linear codes over . For m 1, this class of codes is a subclass of nonlinear codes. Among F_q-linear codes, we consider only cyclic codes and call them F_q-linear cyclic codes (F_q LC codes) over The class of F_q LC codes includes as special cases (i) group cyclic codes over elementary abelian groups (q=p, a prime), (ii) subspace subcodes of Reed–Solomon codes (n=q^m–1) studied by Hattori, McEliece and Solomon, (iii) linear cyclic codes over F_q (m=1) and (iv) twisted BCH codes. Moreover, with respect to any particular F_q-basis of , any F_qLC code over can be viewed as an m-quasi-cyclic code of length mn over F_q. In this correspondence, we obtain transform domain characterization of F_q LC codes, using Discrete Fourier Transform (DFT) over an extension field of The characterization is in terms of any decomposition of the code into certain subcodes and linearized polynomials over . We show how one can use this transform domain characterization to obtain a minimum distance bound for the corresponding quasi-cyclic code. We also prove nonexistence of self dual F_q LC codes and self dual quasi-cyclic codes of certain parameters using the transform domain characterization.AMS classification 94B05