On repeated-root multivariable codes over a finite chain ring

In this work we consider repeated-root multivariable codes over a finite chain ring. We show conditions for these codes to be principally generated. We consider a suitable set of generators of the code and compute its minimum distance. As an application we study the relevant example of the generalized Kerdock code in its r-dimensional cyclic version.      

Codes of Small Defect

The parameters of a linear code C over GF(q) are given by [n,k,d], where n denotes the length, k the dimension and d the minimum distance of C. The code C is called MDS, or maximum distance separable, if the minimum distance d meets the Singleton bound, i.e. d = n-k+1 Unfortunately, the parameters of an MDS code are severely limited by the size of the field. Thus we look for codes which have minimum distance close to the Singleton bound. Of particular interest is the class of almost MDS codes, i.e. codes for which d=n-k. We will present a condition on the minimum distance of a code to guarantee that the orthogonal code is an almost MDS code. This extends a result of Dodunekov and Landgev Dodunekov. Evaluation of the MacWilliams identities leads to a closed formula for the weight distribution which turns out to be completely determined for almost MDS codes up to one parameter. As a consequence we obtain surprising combinatorial relations in such codes. This leads, among other things, to an answer to a question of Assmus and Mattson 5 on the existence of self-dual [2d,d,d]-codes which have no code words of weight d+1. Actually there are more codes than Assmus and Mattson expected, but the examples which we know are related to the expected ones.     

A Lower Bound on the Greedy Weights of Product Codes

A greedy 1-subcode is a one-dimensional subcode of minimum (support) weight. A greedy r-subcode is an r-dimensional subcode with minimum support weight under the constraint that it contain a greedy (r - 1)-subcode. The r-th greedy weight e _r is the support weight of a greedy r-subcode. The greedy weights are related to the weight hierarchy. We use recent results on the weight hierarchy of product codes to develop a lower bound on the greedy weights of product codes.     

Binary linear codes from vectorial boolean functions and their weight distribution

Binary linear codes with good parameters have important applications in secret sharing schemes, authentication codes, association schemes, and consumer electronics and communications. In this paper, we construct several classes of binary linear codes from vectorial Boolean functions and determine their parameters, by further studying a generic construction developed by Ding et al. recently. First, by employing perfect nonlinear functions and almost bent functions, we obtain several classes of six-weight linear codes which contain the all-one codeword, and determine their weight distribution. Second, we investigate a subcode of any linear code mentioned above and consider its parameters. When the vectorial Boolean function is a perfect nonlinear function or a Gold function in odd dimension, we can completely determine the weight distribution of this subcode. Besides, our linear codes have larger dimensions than the ones by Ding et al.’s generic construction.     

A restriction on the weight enumerator of a self-dual code

Gleason's theorem gives the general form of the weight enumerator of a linear binary self-dual code; it is a linear combination with integral coefficients of certain polynomials. When the subcode of words whose weights are multiples of 4 is not the whole code, the MacWilliams identities applied to that subcode yield divisibility conditions on those coefficients. The conditions show that there are no further extremal codes, for Case 1 in the sense of Mallows and Sloane, than the ones known.     

Testing algebraic geometric codes

Property testing was initially studied from various motivations in 1990’s. A code C  GF (r)n is locally testable if there is a randomized algorithm which can distinguish with high possibility the codewords from a vector essentially far from the code by only accessing a very small (typically constant) number of the vector’s coordinates. The problem of testing codes was firstly studied by Blum, Luby and Rubinfeld and closely related to probabilistically checkable proofs (PCPs). How to characterize locally te...     

The Structure of 1-Generator Quasi-Twisted Codes and New Linear Codes

One of the most important problems of coding theory is to construct codes with best possible minimum distances. Recently, quasi-cyclic (QC) codes have been proven to contain many such codes. In this paper, we consider quasi-twisted (QT) codes, which are generalizations of QC codes, and their structural properties and obtain new codes which improve minimum distances of best known linear codes over the finite fields GF(3) and GF(5). Moreover, we give a BCH-type bound on minimum distance for QT codes and give a sufficient condition for a QT code to be equivalent to a QC code.     

Relative generalized Hamming weights of cyclic codes

Relative generalized Hamming weights (RGHWs) of a linear code with respect to a linear subcode determine the security of the linear ramp secret sharing scheme based on the linear codes. They can be used to express the information leakage of the secret when some keepers of shares are corrupted. Cyclic codes are an interesting type of linear codes and have wide applications in communication and storage systems. In this paper, we investigate the RGHWs of cyclic codes of two nonzeros with respect to its irreducible cyclic subcodes. We give two formulae for RGHWs of the cyclic codes. As applications of the formulae, explicit examples are computed. Moreover, RGHWs of cyclic codes in the examples are very large, comparing with the generalized Plotkin bound of RGHWs. So it guarantees very high security for the secret sharing scheme based on the dual codes.     

A result on the weight distributions of binary quadratic residue codes

Truong et al. [7]proved that the weight distribution of a binary quadratic residue code C with length congruent to −1 modulo 8 can be determined by the weight distribution of a certain subcode of C containing only one-eighth of the codewords of C. In this paper, we prove that the same conclusion holds for any binary quadratic residue 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.     

A Gap in GRM Code Weight Distributions

The weight distribution of GRM (generalized Reed-Muller) codes is unknown in general. This article describes and applies some new techniques to the codes over F3. Specifically, we decompose GRM codewords into words from smaller codes and use this decomposition, along with a projective geometry technique, to relate weights occurring in one code with weights occurring in simpler codes. In doing so, we discover a new gap in the weight distribution of many codes. In particular, we show there is no word of weight 3^m–2 in GRM₃(4,m) for m>6, and for even-order codes over the ternary field, we show that under certain conditions, there is no word of weight d+, where d is the minimum distance and is the largest integer dividing all weights occurring in the code.     

Minimum Weight and Dimension Formulas for Some Geometric Codes

The geometric codes are the duals of the codes defined by the designs associated with finite geometries. The latter are generalized Reed–Muller codes, but the geometric codes are, in general, not. We obtain values for the minimum weight of these codes in the binary case, using geometric constructions in the associated geometries, and the BCH bound from coding theory. Using Hamada's formula, we also show that the dimension of the dual of the code of a projective geometry design is a polynomial function in the dimension of the geometry.     

Upper and Lower Bounds on Maximum Nonlinearity of n-input m-output Boolean Function

The paper presents lower and upper bounds on the maximumnonlinearity for an n-input m-output Booleanfunction. We show a systematic construction method for a highlynonlinear Boolean function based on binary linear codes whichcontain the first order Reed-Muller code as a subcode. We alsopresent a method to prove the nonexistence of some nonlinearBoolean functions by using nonexistence results on binary linearcodes. Such construction and nonexistence results can be regardedas lower and upper bounds on the maximum nonlinearity. For somen and m, these bounds are tighter than theconventional bounds. The techniques employed here indicate astrong connection between binary linear codes and nonlinear n-input m-output Boolean functions.     

On the relative profiles of a linear code and a subcode

Relative dimension/length profile (RDLP), inverse relative dimension/length profile (IRDLP) and relative length/dimension profile (RLDP) are equivalent sequences of a linear code and a subcode. The concepts were applied to protect messages from an adversary in the wiretap channel of type II with illegitimate parties. The equivocation to the adversary is described by IRDLP and upper-bounded by the generalized Singleton bound on IRDLP. Recently, RLDP was also extended in wiretap network II for secrecy control of network coding. In this paper, we introduce new relations and bounds about the sequences. They not only reveal new connections among known results but also find applications in trellis complexities of linear codes. The state complexity profile of a linear code and that of a subcode can be bounded from each other, which is particularly useful when a tradeoff among coding rate, error-correcting capability and decoding complexity is considered. Furthermore, a unified framework is proposed to derive bounds on RDLP and IRDLP from an upper bound on RLDP. We introduce three new upper bounds on RLDP and use some of them to tighten the generalized Singleton bounds by applying the framework. The approach is useful to improve equivocation estimation in the wiretap channel of type II with illegitimate parties.     

GOPPA CODES FROMARTIN-SCHREIER FUNCTION FIELDS

ＧＯＰＰＡＣＯＤＥＳＦＲＯＭＡＲＴＩＮ－ＳＣＨＲＥＩＥＲＦＵＮＣＴＩＯＮＦＩＥＬＤＳ￥ＨＡＮＷＥＮＢＡＯ（ＤｅｐａｔｍｅｌｌｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＳｉｃｈｕａｎＵｎｉｖｅｒｓｉｔｙｔＣｈｅｎｇｄｕ６１００６４，Ｓｉｃｈｕａｎ，Ｃｈｉｎａ．）Ａ...     

On the second greedy weight for linear codes of dimension 3

The difference g₂−d₂ for a q-ary linear [n,3,d] code C is studied. Here d₂ is the second generalized Hamming weight, that is, the smallest size of the support of a 2-dimensional subcode of C; and g₂ is the second greedy weight, that is, the smallest size of the support of a 2-dimensional subcode of C which contains a codeword of weight d. For codes of dimension 3, it is shown that the problem is essentially equivalent to finding certain weighting of the points in the projective plane, and weighting which give the maximal value of g₂−d₂ are determined in almost all cases. In particular max(g₂−d₂) is determined in all cases for q⩽9.     

Cryptanalysis of Two McEliece Cryptosystems Based on Quasi-Cyclic Codes

We cryptanalyse here two variants of the McEliece cryptosystem based on quasi-cyclic codes. Both aim at reducing the key size by restricting the public and secret generator matrices to be in quasi-cyclic form. The first variant considers subcodes of a primitive BCH code. The aforementioned constraint on the public and secret keys implies to choose very structured permutations. We prove that this variant is not secure by producing many linear equations that the entries of the secret permutation matrix have to satisfy by using the fact that the secret code is a subcode of a known BCH code. This attack has been implemented and in all experiments we have performed the solution space of the linear system was of dimension one and revealed the permutation matrix. The other variant uses quasi-cyclic low density parity-check (LDPC) codes. This scheme was devised to be immune against general attacks working for McEliece type cryptosystems based on LDPC codes by choosing in the McEliece scheme more general one-to-one mappings than permutation matrices. We suggest here a structural attack exploiting the quasi-cyclic structure of the code and a certain weakness in the choice of the linear transformations that hide the generator matrix of the code. This cryptanalysis adopts a polynomial-oriented approach and basically consists in searching for two polynomials of low weight such that their product is a public polynomial. Our analysis shows that with high probability a parity-check matrix of a punctured version of the secret code can be recovered with time complexity O(n ³) where n is the length of the considered code. The complete reconstruction of the secret parity-check matrix of the quasi-cyclic LDPC codes requires the search of codewords of low weight which can be done with about 2³⁷ operations for the specific parameters proposed.     

MacWilliams Extension Theorem for MDS codes over a vector space alphabet

The MacWilliams Extension Theorem states that each linear isometry of a linear code extends to a monomial map. Unlike the linear codes, in general, nonlinear codes do not have the extension property. In our previous work, in the context of a vector space alphabet, the minimum code length, for which there exists an unextendable code isometry, was determined. In this paper an analogue of the extension theorem for MDS codes is proved. It is shown that for almost all, except 2-dimensional, linear MDS codes over a vector space alphabet the extension property holds. For the case of 2-dimensional MDS codes an improvement of our general result is presented. There are also observed extension properties of near-MDS codes. As an auxiliary result, a new bound on the minimum size of multi-fold partitions of a vector space is obtained.     

A Class of Perfect Ternary Constant-Weight Codes

We construct a class of perfect ternary constant-weight codes of length 2 ^r , weight 2 ^r -1 and minimum distance 3. The codes have codewords. The construction is based on combining cosets of binary Hamming codes. As a special case, for r=2 the construction gives the subcode of the tetracode consisting of its nonzero codewords. By shortening the perfect codes, we get further optimal codes.     

On the Cyclicity of Goppa Codes,Parity-Check Subcodes of Goppa Codes,and Extended Goppa Codes

Classical Goppa codes are a special case of Alternant codes. First we prove that the parity-check subcodes of Goppa codes and the extended Goppa codes are both Alternant codes. Before this paper, all known cyclic Goppa codes were some particular BCH codes. Many families of Goppa codes with a cyclic extension have been found. All these cyclic codes are in fact Alternant codes associated to a cyclic Generalized Reed–Solomon code. In (1989, J. Combin. Theory Ser. A 51, 205–220) H. Stichtenoth determined all cyclic extended Goppa codes with this property. In a recent paper (T. P. Berger, 1999, in “Finite Fields: Theory, Applications and Algorithms (R. Mullin and G. Mullen, Eds.), pp. 143–154, Amer. Math. Soc., Providence), we used some semi-linear transformations on GRS codes to construct cyclic Alternant codes that are not associated to cyclic GRS codes. In this paper, we use these results to construct cyclic Goppa codes that are not BCH codes, new families of Goppa codes with a cyclic extension, and some families of non-cyclic Goppa codes with a cyclic parity-check subcode.