Weight distributions of a class of cyclic codes with arbitrary number of nonzeros in quadratic case

Cyclic codes are an important class of linear codes, whose weight distribution have been extensively studied. So far, most of previous results obtained were for cyclic codes with no more than three nonzeros. Recently, the authors of [37] constructed a class of cyclic codes with arbitrary number of nonzeros, and computed the weight distribution for several cases. In this paper, we determine the weight distribution for a new family of such codes. This is achieved by introducing certain new methods, such as the theory of Jacobi sums over finite fields and subtle treatment of some complicated combinatorial identities.     

A generalization of quasi-twisted codes: Multi-twisted codes

Cyclic codes and their various generalizations, such as quasi-twisted (QT) codes, have a special place in algebraic coding theory. Among other things, many of the best-known or optimal codes have been obtained from these classes. In this work we introduce a new generalization of QT codes that we call multi-twisted (MT) codes and study some of their basic properties. Presenting several methods of constructing codes in this class and obtaining bounds on the minimum distances, we show that there exist codes with good parameters in this class that cannot be obtained as QT or constacyclic codes. This suggests that considering this larger class in computer searches is promising for constructing codes with better parameters than currently best-known linear codes. Working with this new class of codes motivated us to consider a problem about binomials over finite fields and to discover a result that is interesting in its own right.     

On Z2Z4-additive complementary dual codes and related LCD codes

Linear complementary dual codes were defined by Massey in 1992, and were used to give an optimum linear coding solution for the two user binary adder channel. In this paper, we define the analog of LCD codes over fields in the ambient space with mixed binary and quaternary alphabets. These codes are additive, in the sense that they are additive subgroups, rather than linear as they are not vector spaces over some finite field. We study the structure of these codes and we use the canonical Gray map from this space to the Hamming space to construct binary LCD codes in certain cases. We give examples of such binary LCD codes which are distance-optimal, i.e., they have the largest minimum distance among all binary LCD codes with the same length and dimension.     

The structure of linear codes of constant weight

In this paper we determine completely the structure of linear codes over of constant weight. Namely, we determine exactly which modules underlie linear codes of constant weight, and we describe the coordinate functionals involved. The weight functions considered are: Hamming weight, Lee weight, two forms of Euclidean weight, and pre-homogeneous weights. We prove a general uniqueness theorem for virtual linear codes of constant weight. Existence is settled on a case by case basis.

     

On Hermitian LCD codes and their Gray image

We provide methods and algorithms to construct Hermitian linear complementary dual (LCD) codes over finite fields. We study existence of self-dual basis with respect to Hermitian inner product, and as an application, we construct Euclidean LCD codes by projecting the Hermitian codes over such a basis. Many optimal quaternary Hermitian and ternary Euclidean LCD codes are obtained. Comparisons with classical constructions are made.     

An efficient algorithm for constructing reversible quasi-cyclic codes via Chinese remainder theorem

Regarding quasi-cyclic codes as certain polynomial matrices, we show that all reversible quasi-cyclic codes are decomposed into reversible linear codes of shorter lengths corresponding to the coprime divisors of the polynomials with the form of one minus x to the power of m. This decomposition brings us an efficient method to construct reversible quasi-cyclic codes. We also investigate the reversibility and the self-duality of the linear codes corresponding to the coprime divisors of the polynomials. Specializing to the cases where the number of cyclic sections is not more than two, we give necessary and sufficient conditions for the divisors of the polynomials for which the self-dual codes are reversible and the reversible codes of half-length-dimension are self-dual. Our theorems are utilized to search reversible self-dual quasi-cyclic codes with two cyclic sections over binary and quaternary fields of lengths up to seventy and thirty-six, respectively, together with the maximums of their minimum weights.     

Latroids and their representation by codes over modules

It has been known for some time that there is a connection between linear codes over fields and matroids represented over fields. In fact a generator matrix for a linear code over a field is also a representation of a matroid over that field. There are intimately related operations of deletion, contraction, minors and duality on both the code and the matroid. The weight enumerator of the code is an evaluation of the Tutte polynomial of the matroid, and a standard identity relating the Tutte polynomials of dual matroids gives rise to a MacWilliams identity relating the weight enumerators of dual codes. More recently, codes over rings and modules have been considered, and MacWilliams type identities have been found in certain cases.

In this paper we consider codes over rings and modules with code duality based on a Morita duality of categories of modules. To these we associate latroids, defined here. We generalize notions of deletion, contraction, minors and duality, on both codes and latroids, and examine all natural relations among these.

We define generating functions associated with codes and latroids, and prove identities relating them, generalizing above-mentioned generating functions and identities.

     

Schubert varieties, linear codes and enumerative combinatorics

We consider linear error correcting codes associated to higher-dimensional projective varieties defined over a finite field. The problem of determining the basic parameters of such codes often leads to some interesting and difficult questions in combinatorics and algebraic geometry. This is illustrated by codes associated to Schubert varieties in Grassmannians, called Schubert codes, which have recently been studied. The basic parameters such as the length, dimension and minimum distance of these codes are known only in special cases. An upper bound for the minimum distance is known and it is conjectured that this bound is achieved. We give explicit formulae for the length and dimension of arbitrary Schubert codes and prove the minimum distance conjecture in the affirmative for codes associated to Schubert divisors.     

The triple distribution of codes and ordered codes

We study the distribution of triples of codewords of codes and ordered codes. Schrijver [A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (8) (2005) 2859–2866] used the triple distribution of a code to establish a bound on the number of codewords based on semidefinite programming. In the first part of this work, we generalize this approach for ordered codes. In the second part, we consider linear codes and linear ordered codes and present a MacWilliams-type identity for the triple distribution of their dual code. Based on the non-negativity of this linear transform, we establish a linear programming bound and conclude with a table of parameters for which this bound yields better results than the standard linear programming bound.     

Two-weight or three-weight binary linear codes from cyclotomic mappings

Recently, linear codes with few weights have been studied extensively. These linear codes have wide applications in secret sharing schemes and authentication codes. In this paper, we introduce a new construction of defining sets using cyclotomic mappings and construct three new classes of binary linear codes with two or three weights. We also explicitly determine the weight distributions of these codes.     

Hamming weight enumerators of multi-twisted codes with at most two non-zero constituents

In this paper, we explicitly determine Hamming weight enumerators of several classes of multi-twisted codes over finite fields with at most two non-zero constituents, where each non-zero constituent has dimension 1. Among these classes of multi-twisted codes, we further identify two classes of optimal equidistant linear codes that have nice connections with the theory of combinatorial designs and several other classes of minimal linear codes that are useful in constructing secret sharing schemes with nice access structures. We also illustrate our results with some examples.     

Binary permutation sequences as subsets of Levenshtein codes,spectral null codes,run-length limited codes and constant weight codes

We investigate binary sequences which can be obtained by concatenating the columns of (0,1)-matrices derived from permutation sequences. We then prove that these binary sequences are subsets of a surprisingly diverse ensemble of codes, namely the Levenshtein codes, capable of correcting insertion/deletion errors; spectral null codes, with spectral nulls at certain frequencies; as well as being subsets of run-length limited codes, Nyquist null codes and constant weight codes. This paper was presented in part at the IEEE Information Theory Workshop, Chengdu, China, October, 2006.     

Quasi-cyclic codes as cyclic codes over a family of local rings

We give an algebraic structure for a large family of binary quasi-cyclic codes. We construct a family of commutative rings and a canonical Gray map such that cyclic codes over this family of rings produce quasi-cyclic codes of arbitrary index in the Hamming space via the Gray map. We use the Gray map to produce optimal linear codes that are quasi-cyclic.     

Improved decoding of affine-variety codes

General error locator polynomials are polynomials able to decode any correctable syndrome for a given linear code. Such polynomials are known to exist for all cyclic codes and for a large class of linear codes. We provide some decoding techniques for affine-variety codes using some multidimensional extensions of general error locator polynomials. We prove the existence of such polynomials for any correctable affine-variety code and hence for any linear code. We propose two main different approaches, that depend on the underlying geometry. We compute some interesting cases, including Hermitian codes. To prove our coding theory results, we develop a theory for special classes of zero-dimensional ideals, that can be considered generalizations of stratified ideals. Our improvement with respect to stratified ideals is twofold: we generalize from one variable to many variables and we introduce points with multiplicities.     

Doubly and triply extended MSRD codes

In this work, doubly extended linearized Reed–Solomon codes and triply extended Reed–Solomon codes are generalized. We obtain a general result in which we characterize when a multiply extended code for a general metric attains the Singleton bound. We then use this result to obtain several families of doubly extended and triply extended maximum sum-rank distance (MSRD) codes that include doubly extended linearized Reed–Solomon codes and triply extended Reed–Solomon codes as particular cases. To conclude, we discuss when these codes are one-weight codes.     

Linear codes for high payload steganography

Steganography is concerned with communicating hidden messages in such a way that no one apart from the sender and the intended recipient can detect the very existence of the message. We study the syndrome coding method (sometimes also called the “matrix embedding method”), which uses a linear code as an ingredient. Among all codes of a fixed block length and fixed dimension (and thus of a fixed information rate), an optimal code is one that makes it most difficult for an eavesdropper to detect the presence of the hidden message. We show that the average distance to code is the appropriate concept that replaces the covering radius for this particular application. We completely classify the optimal codes in the cases when the linear code used in the syndrome coding method is a one- or two-dimensional code over . In the steganography application this translates to cases when the code carries a high payload (has a high information rate).     

Linear transformations on codes

This paper studies and classifies linear transformations that connect Hamming distances of codes. These include irreducible linear transformations and their concatenations. Their effect on the Hamming weights of codewords is investigated. Both linear and non-linear codes over fields are considered. We construct optimal linear codes and a family of pure binary quantum codes using these transformations.     

Perfect codes as isomorphic spaces

Linear equivalence between perfect codes is defined. This definition gives the concept of general perfect 1-error correcting binary codes. These are defined as 1-error correcting perfect binary codes, with the difference that the set of errors is not the set of weight one words, instead any set with cardinality n and full rank is allowed. The side class structure defines the restrictions on the subspace of any general 1-error correcting perfect binary code. Every linear equivalence class will contain all codes with the same length, rank and dimension of kernel and all codes in the linear equivalence class will have isomorphic side class structures.     

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).