A commutative algebra approach to linear codes

Recently some methods have been proposed to find the distance and weight distribution of cyclic codes using Gröbner bases. We identify a class of codes for which these methods can be generalized. We show that this class contains all interesting linear codes and we provide variants and improvements. This approach sometimes reveals an unexpected algebraic structure in the code. We also investigate the decoding for a subclass, proving the existence of general error locator polynomials.     

A note on the Newton radius

The Newton radius of a code is the largest weight of a uniquely correctable error. We establish a lower bound for the Newton radius in terms of the rate. In particular we show that in any family of linear codes of rate below one half, the Newton radius increases linearly with the codeword length.     

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.      

Robust locally testable codes and products of codes

We continue the investigation of locally testable codes, i.e., error‐correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations. We give two general results on local testability: First, motivated by the recently proposed notion of robust probabilistically checkable proofs, we introduce the notion of robust local testability of codes. We relate this notion to a product of codes introduced by Tanner and show a very simple composition lemma for this notion. Next, we show that codes built by tensor products can be tested robustly and somewhat locally by applying a variant of a test and proof technique introduced by Raz and Safra in the context of testing low‐degree multivariate polynomials (which are a special case of tensor codes). Combining these two results gives us a generic construction of codes of inverse polynomial rate that are testable with poly‐logarithmically many queries. We note that these locally testable tensor codes can be obtained from any linear error correcting code with good distance. Previous results on local testability, albeit much stronger quantitatively, rely heavily on algebraic properties of the underlying codes. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

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.

     

On the computation of coset leaders with high Hamming weight

The Newton radius of a code is the largest weight of a uniquely correctable error. The covering radius is the largest distance between a vector and the code. In this paper, we use the modular representation of a linear code to give an efficient algorithm for computing coset leaders of relatively high Hamming weight. The weights of these coset leaders serve as lower bounds on the Newton radius and the covering radius for linear codes.     

The generalized Goertzel algorithm and its parallel hardware implementation

Reed-Solomon (RS) and Bose-Chaudhuri-Hocquenghem (BCH) error correcting codes are widely used in digital technology. An important problem in the implementation of RS and BCH decoding is the fast finding of the error positions (the roots of error locator polynomials). Several fast root-finding algorithms for polynomials over finite fields have been proposed. In this paper we give a generalization of the Goertzel algorithm. Our algorithm is suitable for the parallel hardware implementation and the time of multiplications used is restricted by a constant.     

Every Banach ideal of polynomials is compatible with an operator ideal

We show that for each Banach ideal of homogeneous polynomials, there exists a (necessarily unique) Banach operator ideal compatible with it. Analogously, we prove that any ideal of n-homogeneous polynomials belongs to a coherent sequence of ideals of k-homogeneous polynomials.     

Every Banach ideal of polynomials is compatible with an operator ideal

We show that for each Banach ideal of homogeneous polynomials, there exists a (necessarily unique) Banach operator ideal compatible with it. Analogously, we prove that any ideal of n-homogeneous polynomials belongs to a coherent sequence of ideals of k-homogeneous polynomials.     

An abundance of invariant polynomials satisfying the Riemann hypothesis

In 1999, Iwan Duursma defined the zeta function for a linear code as a generating function of its Hamming weight enumerator. It can also be defined for other homogeneous polynomials not corresponding to existing codes. If the homogeneous polynomial is invariant under the MacWilliams transform, then its zeta function satisfies a functional equation and we can formulate an analogue of the Riemann hypothesis. As far as existing codes are concerned, the Riemann hypothesis is believed to be closely related to the extremal property.In this article, we show there are abundant polynomials invariant by the MacWilliams transform which satisfy the Riemann hypothesis. The proof is carried out by explicit construction of such polynomials. To prove the Riemann hypothesis for a certain class of invariant polynomials, we establish an analogue of the Eneström-Kakeya theorem.     

Some results on linear codes over the ring $$\mathbb {Z}_4+u\mathbb {Z}_4+v\mathbb {Z}_4+uv\mathbb {Z}_4$$

In this paper, we mainly study the theory of linear codes over the ring \(R =\mathbb {Z}_4+u\mathbb {Z}_4+v\mathbb {Z}_4+uv\mathbb {Z}_4\). By using the Chinese Remainder Theorem, we prove that R is isomorphic to a direct sum of four rings. We define a Gray map \(\Phi \) from \(R^{n}\) to \(\mathbb {Z}_4^{4n}\), which is a distance preserving map. The Gray image of a cyclic code over R is a linear code over \(\mathbb {Z}_4\). We also discuss some properties of MDS codes over R. Furthermore, we study the MacWilliams identities of linear codes over R and give the generator polynomials of cyclic codes over R.     

Linearly representable codes over chain rings

In this paper, we consider linear codes over finite chain rings. We present a general mapping which produces codes over smaller alphabets. Under special conditions, these codes are linear over a finite field. We introduce the notion of a linearly representable code and prove that certain MacDonald codes are linearly representable. Finally, we give examples for good linear codes over finite fields obtained from special multisets in projective Hjelmslev planes.     

On Harmonic Weight Enumerators of Binary Codes

We define some new polynomials associated to a linear binary code and a harmonic function of degree k. The case k=0 is the usual weight enumerator of the code. When divided by (xy) ^k , they satisfy a MacWilliams type equality. When applied to certain harmonic functions constructed from Hahn polynomials, they can compute some information on the intersection numbers of the code. As an application, we classify the extremal even formally self-dual codes of length 12.     

Constructible Ideals

Based on the study of simplicial complexes, one may naturally define the constructible monomial ideals. We connect the square-free constructible ideal with the Stanley–Reisner ideal of the Alexander dual associated to a constructible simplicial complex. We give some properties of constructible ideals, and we compute the Betti numbers. We prove that all monomial ideals with linear quotients are constructible ideals. We also show that all constructible ideals have a linear resolution.     

Differential standard bases under composition

We generalize Hoon Hong’s theorem on Gröbner bases under composition to the case of differential standard bases in the ordinary ring of differential polynomials {ie4152-01}. In particular, we prove that some ideals have finite differential standard bases. We construct special orderings on differential monomials such that ideals generated by some power of a quasi-linear polynomial acquire finite differential standard bases.     

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.     

Binomial Moments of the Distance Distribution and the Probability of Undetected Error

In [1] K. A. S. Abdel-Ghaffar derives a lower bound on the probability of undetected error for unrestricted codes. The proof relies implicitly on the binomial moments of the distance distribution of the code. We use the fact that these moments count the size of subcodes of the code to give a very simple proof of the bound in Abdel by showing that it is essentially equivalent to the Singleton bound. This proof reveals connections of the probability of undetected error to the rank generating function of the code and to related polynomials (Whitney function, Tutte polynomial, and higher weight enumerators). We also discuss some improvements of this bound.Finally, we analyze asymptotics. We show that an upper bound on the undetected error exponent that corresponds to the bound of Abdel improves known bounds on this function.