Quaternary quasi-cyclic codes

Quasi-cyclic codes of length mn over Z4 are shown to be equivalent to A-submodules of A^n, where A = Z4[x]/（x^m - 1）. In the case of m being odd, all quasi-cyclic codes are shown to be decomposable into the direct sum of a fixed number of cyclic irreducible A-submodules. Finally the distinct quasi-cyclic codes as well as some specific subclasses are enumerated.     

On Lagrangian–Grassmannian codes

Using the Lagrangian–Grassmannian, a smooth algebraic variety of dimension n(n + 1)/2 that parametrizes isotropic subspaces of dimension n in a symplectic vector space of dimension 2n, we construct a new class of linear codes generated by this variety, the Lagrangian–Grassmannian codes. We explicitly compute their word length, give a formula for their dimension and an upper bound for the minimum distance in terms of the dimension of the Lagrangian–Grassmannian variety.     

Type Ⅱ codes over finite rings

In this paper,we generalize the concept of Type Ⅱ codes to arbitrary finite rings. We focus on Type Ⅱ codes over finite chain rings and use the Chinese Remainder Theorem on these codes to study Type Ⅱ codes over principal ideal rings.     

Complete variable-length “fix-free” codes

A set of codewords isfix-free if it is both prefix-free and suffix-free: no codeword in the set is a prefix or a suffix of any other. A set of codewords {x ₁,x ₂,...,x _n } over at-letter alphabet is said to becomplete if it satisfies the Kraft inequality with equality, so that

Weighted Reed–Muller codes revisited

We consider weighted Reed–Muller codes over point ensemble S ₁ × · · · × S _m where S _i needs not be of the same size as S _j . For m = 2 we determine optimal weights and analyze in detail what is the impact of the ratio |S ₁|/|S ₂| on the minimum distance. In conclusion the weighted Reed–Muller code construction is much better than its reputation. For a class of affine variety codes that contains the weighted Reed–Muller codes we then present two list decoding algorithms. With a small modification one of these algorithms is able to correct up to 31 errors of the [49,11,28] Joyner code.     

Difference packing arrays and systematic authentication codes

In this paper, a type of combinatorial design (called difference packing array) is proposed and used to give a construction of systematic authentication codes. Taking advantage of this construction, some new series of systematic authentication codes are obtainable in terms of existing difference packing arrays.     

Minimal codewords in Reed–Muller codes

Minimal codewords were introduced by Massey (Proceedings of the 6th Joint Swedish-Russian International Workshop on Information Theory, pp 276–279, 1993) for cryptographical purposes. They are used in particular secret sharing schemes, to model the access structures. We study minimal codewords of weight smaller than 3 · 2 ^m−r in binary Reed–Muller codes RM(r, m) and translate our problem into a geometrical one, using a classification result of Kasami and Tokura (IEEE Trans Inf Theory 16:752–759, 1970) and Kasami et al. (Inf Control 30(4):380–395, 1976) on Boolean functions. In this geometrical setting, we calculate numbers of non-minimal codewords. So we obtain the number of minimal codewords in the cases where we have information about the weight distribution of the code RM(r, m). The presented results improve previous results obtained theoretically by Borissov et al. (Discrete Appl Math 128(1), 65–74, 2003), and computer aided results of Borissov and Manev (Serdica Math J 30(2-3), 303–324, 2004). This paper is in fact an extended abstract. Full proofs can be found on the arXiv.     

Solid codes and the uniform density of fd-domains

By means of further investigation of solid codes,the problem“Is every fd-domain uni- formly dense”proposed by Yuqi Guo,C.M.Reis and G.Thierrin in 1988 is solved in this paper.     

Hasse–Weil bound for additive cyclic codes

We obtain a bound on the minimum distance of additive cyclic codes via the number of rational points on certain algebraic curves over finite fields. This is an extension of the analogous bound in the case of classical cyclic codes. Our result is the only general bound on such codes aside from Bierbrauer’s BCH bound. We compare our bounds’ performance against the BCH bound for additive cyclic codes in a special case and provide examples where it yields better results.     

On puncturing of codes from Norm–Trace curves

Constructing new codes from existing ones by puncturing is in this paper viewed in the context of order domains R where puncturing can be seen as redefinition of the evaluation map $\varphi :R\to {\mathbb{F}}_q^n$. The order domains considered here are of the form $R=\mathbb{F}[x_1,x_2,\dots ,x_m]/I$ where redefining $\varphi$ can be done by adding one or more polynomials to the basis of the defining ideal I to form a new ideal J in such a way that the number of points in the variety $\mathbb{V}(I)$ is reduced by t to form $\mathbb{V}(J)$ and puncturing in t coordinates is achieved. An explicit construction of such polynomials is given in the case of codes defined by Norm–Trace curves and examples are given of both evaluation codes and dual codes. Finally, it is demonstrated that the improvement in minimum distance can be significant when compared to the lower bound obtained by ordinary puncturing.     

Inhomogenous quantum codes (Ⅰ):additive case

In this paper,the quantum error-correcting codes are generalized to the inhomogenous quantumstate space Cq1  Cq2 ··· Cqn,where qi(1 i n) are arbitrary positive integers.By attaching an abelian group Ai of order qi to the space Cqi(1 i n),we present the stabilizer construction of such inhomogenous quantum codes,called additive quantum codes,in term of the character theory of the abelian group A = A1⊕A2⊕···⊕An.As usual case,such construction opens a way to get inhomogenous quantum codes from the classical mixed linear codes.We also present Singleton bound for inhomogenous additive quantum codes and show several quantum codes to meet such bound by using classical mixed algebraic-geometric codes.     

Stanley–Reisner resolution of constant weight linear codes

Given a constant weight linear code, we investigate its weight hierarchy and the Stanley–Reisner resolution of its associated matroid regarded as a simplicial complex. We also exhibit conditions on the higher weights sufficient to conclude that the code is of constant weight.     

New binary self-dual codes of lengths 50–60

Using a method for constructing binary self-dual codes with an automorphism of odd prime order \(p\) , we give a full classification of all optimal binary self-dual \([50+2t,25+t]\) codes having an automorphism of order 5 for \(t=0,\dots ,5\) . As a consequence, we determine the weight enumerators for which there is an optimal binary self-dual \([52, 26, 10]\) code. Some of the constructed codes for lengths 52, 54, 58, and 60 have new values for the parameter in their weight enumerator. We also construct more than 3,000 new doubly-even \([56,28,12]\) self-dual codes.     

Cube-tilings of ℝ n and nonlinear codesand nonlinear codes

Families of nonlattice tilings of ℝ ⁿ by unit cubes are constructed. These tilings are specializations of certain families of nonlinear codes overGF(2). These cube-tilings provide building blocks for the construction of cube-tilings such that no two cubes have a high-dimensional face in common. We construct cube-tilings of ℝ ⁿ such that no two cubes have a common face of dimension exceeding .     

Simple algorithms for decoding systematic Reed–Solomon codes

A simple algorithm for decoding nonsystematic Reed–Solomon codewords was proposed by A. Shiozaki and independently by S. Gao. We first exhibit the companion algorithm for decoding systematic Reed–Solomon codes. Next, we improve this algorithm into one that is identical to traditional Reed–Solomon decoding. The algorithm will then be adjusted to work with nonstandard Reed–Solomon codes. Finally, we modify the algorithm into one that decodes Reed–Solomon codes with erasures that is slightly more efficient than existing techniques.     

Peterson–Gorenstein–Zierler algorithm for skew RS codes

We design a non-commutative version of the Peterson–Gorenstein–Zierler decoding algorithm for a class of codes that we call skew RS codes. These codes are left ideals of a quotient of a skew polynomial ring, which endow them of a sort of non-commutative cyclic structure. Since we work over an arbitrary field, our techniques may be applied both to linear block codes and convolutional codes. In particular, our decoding algorithm applies for block codes beyond the classical cyclic case.     

Distinguisher-based attacks on public-key cryptosystems using Reed–Solomon codes

Because of their interesting algebraic properties, several authors promote the use of generalized Reed–Solomon codes in cryptography. Niederreiter was the first to suggest an instantiation of his cryptosystem with them but Sidelnikov and Shestakov showed that this choice is insecure. Wieschebrink proposed a variant of the McEliece cryptosystem which consists in concatenating a few random columns to a generator matrix of a secretly chosen generalized Reed–Solomon code. More recently, new schemes appeared which are the homomorphic encryption scheme proposed by Bogdanov and Lee, and a variation of the McEliece cryptosystem proposed by Baldi et al. which hides the generalized Reed–Solomon code by means of matrices of very low rank. In this work, we show how to mount key-recovery attacks against these public-key encryption schemes. We use the concept of distinguisher which aims at detecting a behavior different from the one that one would expect from a random code. All the distinguishers we have built are based on the notion of component-wise product of codes. It results in a powerful tool that is able to recover the secret structure of codes when they are derived from generalized Reed–Solomon codes. Lastly, we give an alternative to Sidelnikov and Shestakov attack by building a filtration which enables to completely recover the support and the non-zero scalars defining the secret generalized Reed–Solomon code.     

Almost Euclidean subspaces of ℓ 1 N VIA expander codes

We give an explicit (in particular, deterministic polynomial time) construction of subspaces X⊆ℝ ^N of dimension (1−o(1))N such that for every x∈X,