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 .     

Classification of Griesmer codes and dual transform

In this work, we consider a classification of infinite families of linear codes which achieve the Griesmer bound, using the projective dual transform. We investigate the correspondence between families of linear codes with given properties via dual transform.     

The non-existence of some perfect codes over non-prime power alphabets

Let denote the number of times the prime number p appears in the prime factorization of the integer q. The following result is proved: If there is a perfect 1-error correcting code of length n over an alphabet with q symbols then, for every prime number .This condition is stronger than both the packing condition and the necessary condition given by the Lloyd theorem, as it for example excludes the existence of a perfect code with the parameters (n,q,e)=(19,6,1).     

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

On the non-existence of perfect and nearly perfect codes

The main result of the paper is the proof of the non-existence of a class of completely regular codes in certain distance-regular graphs. Corollaries of this result establish the non-existence of perfect and nearly perfect codes in the infinite families of distance-regular graphs J(2b + 1, b) and J(2b+2,b).     

Multiple blocking sets in finite projective spaces and improvements to the Griesmer bound for linear codes

Belov, Logachev and Sandimirov construct linear codes of minimum distance d for roughly 1/q ^k/2 of the values of d < q ^k-1. In this article we shall prove that, for q = p prime and roughly \frac38{\frac{3}{8}}-th’s of the values of d < q ^k-1, there is no linear code meeting the Griesmer bound. This result uses Blokhuis’ theorem on the size of a t-fold blocking set in PG(2, p), p prime, which we generalise to higher dimensions. We also give more general lower bounds on the size of a t-fold blocking set in PG(δ, q), for arbitrary q and δ ≥ 3. It is known that from a linear code of dimension k with minimum distance d < q ^k-1 that meets the Griesmer bound one can construct a t-fold blocking set of PG(k−1, q). Here, we calculate explicit formulas relating t and d. Finally we show, using the generalised version of Blokhuis’ theorem, that nearly all linear codes over \mathbb F_p{{\mathbb F}_p} of dimension k with minimum distance d < q ^k-1, which meet the Griesmer bound, have codewords of weight at least d + p in subcodes, which contain codewords satisfying certain hypotheses on their supports.     

A class of optimal linear codes of length one above the Griesmer bound

In this paper, we determine the smallest lengths of linear codes with some minimum distances. We construct a [g _q (k, d) + 1, k, d] _q code for sq ^k-1 − sq ^k-2 − q ^s  − q ² + 1 ≤ d ≤ sq ^k-1 − sq ^k-2 − q ^s with 3 ≤ s ≤ k − 2 and q ≥ s + 1. Then we get n _q (k, d) = g _q (k, d) + 1 for (k − 2)q ^k-1 − (k − 1)q ^k-2 − q ² + 1 ≤ d ≤ (k − 2)q ^k-1 − (k − 1)q ^k-2, k ≥ 6, q ≥ 2k − 3; and sq ^k-1 − sq ^k-2 − q ^s  − q + 1 ≤ d ≤ sq ^k-1 − sq ^k-2 − q ^s , s ≥ 2, k ≥ 2s + 1 and q ≥ 2s − 1. This work was partially supported by the Com²MaC-SRC/ERC program of MOST/KOSEF (grant ^# R11-1999-054) and was partially supported by the Korea Research Foundation Grant funded by the Korean Government(MOEHRD)(KRF-2005-214-C00175).     

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.     

On the non-existence of certain M.D.S. codes and projective planes

Mathematische Zeitschrift -     

Unrestricted codes with the golay parameters are unique

The paper contains a proof of the uniqueness of both binary and ternary Golay codes, without assumption of linearity. Similar results are obtained about the extended and expurgated Golay codes. The method consists in proving the linearity, which, according to Pless' results, implies the uniqueness.