On the nonexistence of ternary linear codes attaining the Griesmer bound

Designs, Codes and Cryptography - An $$[n,k,d]_q$$ code is a linear code of length n, dimension k and minimum weight d over the field of order q. It is known that the Griesmer bound is attained for...     

Improvements on the Johnson bound for Reed-Solomon codes

For Reed-Solomon codes with block length n and dimension k, the Johnson theorem states that for a Hamming ball of radius smaller than , there can be at most O(n²) codewords. It was not known whether for larger radius, the number of codewords is polynomial. The best known list decoding algorithm for Reed-Solomon codes due to Guruswami and Sudan [Venkatesan Guruswami, Madhu Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Transactions on Information Theory 45 (6) (1999) 1757-1767] is also known to work in polynomial time only within this radius. In this paper we prove that when k<αn for any constant 0<α<1, we can overcome the barrier of the Johnson bound for list decoding of Reed-Solomon codes (even if the field size is exponential). More specifically in such a case, we prove that for Hamming ball of radius (for any c>0) there can be at most number of codewords. For any constant c, we describe a polynomial time algorithm for enumerating all of them, thereby also improving on the Guruswami-Sudan algorithm. Although the improvement is modest, this provides evidence for the first time that the bound is not sacrosanct for such a high rate.We apply our method to obtain sharper bounds on a list recovery problem introduced by Guruswami and Rudra [Venkatesan Guruswami, Atri Rudra, Limits to list decoding Reed-Solomon codes, IEEE Transactions on Information Theory 52 (8) (2006) 3642-3649] where they establish super-polynomial lower bounds on the output size when the list size exceeds . We show that even for larger list sizes the problem can be solved in polynomial time for certain values of k.     

A symmetric Roos bound for linear codes

The van Lint-Wilson AB-method yields a short proof of the Roos bound for the minimum distance of a cyclic code. We use the AB-method to obtain a different bound for the weights of a linear code. In contrast to the Roos bound, the role of the codes A and B in our bound is symmetric. We use the bound to prove the actual minimum distance for a class of dual BCH codes of length q²−1 over Fq. We give cyclic codes [63,38,16] and [65,40,16] over F₈ that are better than the known [63,38,15] and [65,40,15] codes.     

Classification and nonexistence results for linear codes with prescribed minimum distances

Starting from a linear [n, k, d] _q code with dual distance ${d^{\bot}}$ , we may construct an ${[n - d^\bot, k - d^\bot +1,\geq d]_q}$ code with dual distance at least ${\left\lceil\frac{d^\bot}{q}\right\rceil}$ using construction Y ₁. The inverse construction gives a rule for the classification of all [n, k, d] _q codes with dual distance ${d^{\bot}}$ by adding ${d^\bot}$ further columns to the parity check matrices of the smaller codes. Isomorph rejection is applied to guarantee a small search space for this iterative approach. Performing a complete search based on this observation, we are able to prove the nonexistence of linear codes for 16 open parameter sets [n, k, d] _q , q =  2, 3, 4, 5, 7, 8. These results imply 217 new upper bounds in the known tables for the minimum distance of linear codes and establish the exact value in 109 cases.     

On the binary codes with parameters of doubly-shortened 1-perfect codes

We show that any binary (n = 2 ^k − 3, 2 ^n−k , 3) code C ₁ is a cell of an equitable partition (perfect coloring) (C ₁, C ₂, C ₃, C ₄) of the n-cube with the quotient matrix ((0, 1, n−1, 0)(1, 0, n−1, 0)(1, 1, n−4, 2)(0, 0, n−1, 1)). Now the possibility to lengthen the code C ₁ to a 1-perfect code of length n + 2 is equivalent to the possibility to split the cell C ₄ into two distance-3 codes or, equivalently, to the biparticity of the graph of distances 1 and 2 of C ₄. In any case, C ₁ is uniquely embedable in a twofold 1-perfect code of length n + 2 with some structural restrictions, where by a twofold 1-perfect code we mean that any vertex of the space is within radius 1 from exactly two codewords. By one example, we briefly discuss 2 − (n, 3, 2) multidesigns with similar restrictions. We also show a connection of the problem with the problem of completing latin hypercuboids of order 4 to latin hypercubes.     

On the binary codes with parameters of triply-shortened 1-perfect codes

We study properties of binary codes with parameters close to the parameters of 1-perfect codes. An arbitrary binary (n?=?2 ^m ? 3, 2 ^n-m-1, 4) code C, i.e., a code with parameters of a triply-shortened extended Hamming code, is a cell of an equitable partition of the n-cube into six cells. An arbitrary binary (n?=?2 ^m ? 4, 2 ^n-m , 3) code D, i.e., a code with parameters of a triply-shortened Hamming code, is a cell of an equitable family (but not a partition) with six cells. As a corollary, the codes C and D are completely semiregular; i.e., the weight distribution of such codes depends only on the minimal and maximal codeword weights and the code parameters. Moreover, if D is self-complementary, then it is completely regular. As an intermediate result, we prove, in terms of distance distributions, a general criterion for a partition of the vertices of a graph (from rather general class of graphs, including the distance-regular graphs) to be equitable.     

Varieties of binary linear codes

Received October 9, 1998; accepted in final form May 13, 1999.     

On the general excess bound for binary codes with covering radius one

Let K(n,1)$K(n,1)$ denote the minimal cardinality of a binary code of length n$n$ and covering radius one. Fundamental for the theory of lower bounds for K(n,1)$K(n,1)$ is the covering excess method introduced by Johnson and van Wee. Let _δi${\delta }_i$ denote the covering excess on a sphere of radius i$i$, 0≤i≤n$0\le i\le n$. Generalizing an earlier result of van Wee, Habsieger and Honkala showed _δp−1≥p−1${\delta }_{p-1}\ge p-1$ whenever n≡−1$n\equiv -1$ (mod p$p$) for an odd prime p$p$ and _δ0=_δ1=?=_δp−2=0${\delta }_0={\delta }_1=?={\delta }_{p-2}=0$ holds. In the present paper we give the new estimation _δp−1≥(p−2)p−1${\delta }_{p-1}\ge (p-2)p-1$ instead. This answers a question of Habsieger and yields a “general improvement of the general excess bound” for binary codes with covering radius one. The proof uses a classification theorem for certain subset systems as well as new congruence properties for the δ$\delta$-function, which were conjectured by Habsieger.     

An upper bound for the number of uniformly packed binary codes

Under study are the binary codes uniformly packed (in the wide sense) of length n with minimum distance d and covering radius ρ. It is shown that every code of this kind is uniquely determined by the set of its codewords of weights ?n/2? ? ρ, …, ?n/2? + ρ. For odd d, the number of distinct codes is at most

$2^{2^{n - \tfrac{3}{2}\log n + o(log n)} } $

.

     

Improved lower bound for locating-dominating codes in binary Hamming spaces

Designs, Codes and Cryptography - In this article, we study locating-dominating codes in binary Hamming spaces $$mathbb {F}^n$$ . Locating-dominating codes have been widely studied since their...     

Construction of binary and ternary self-orthogonal linear codes

We construct new binary and ternary self-orthogonal linear codes. In order to do this we use an equivalence between the existence of a self-orthogonal linear code with a prescribed minimum distance and the existence of a solution of a certain system of Diophantine linear equations. To reduce the size of the system of equations we restrict the search for solutions to solutions with special symmetry given by matrix groups. Using this method we found at least six new distance-optimal codes, which are all self-orthogonal.     

On the weight distribution of random binary linear codes

We investigate the weight distribution of random binary linear codes. For 0 < λ < 1 and n→∞ pick uniformly at random λn vectors in and let be the orthogonal complement of their span. Given 0 < γ < 1/2 with 0 < λ < h(γ) let X be the random variable that counts the number of words in C of Hamming weight γn. In this paper we determine the asymptotics of the moments of X of all orders .     

On the non-existence of linear codes attaining the Griesmer bound

A lower bound on the size of a set K in PG(3, q) satisfying for any plane of PG(3, q), q4 is given. It induces the non-existence of linear [n,4,n + 1 – q ²]-codes over GF(q) attaining the Griesmer bound for .     

The linear programming bound for codes over finite Frobenius rings

In traditional algebraic coding theory the linear-programming bound is one of the most powerful and restrictive bounds for the existence of both linear and non-linear codes. This article develops a linear-programming bound for block codes on finite Frobenius rings. An erratum to this article can be found at