On codes with covering radius 1 and minimum distance 2

We show that a code C of length n over an alphabet Q of size q with minimum distance 2 and covering radius 1 satisfies |C| ≥ qⁿ⁻¹/(n − 1). For the special case n = q = 4 the smallest known example has |C| = 31. We give a construction for such a code C with |C| = 28.     

Linear codes with covering radius 3

The shortest possible length of a q-ary linear code of covering radius R and codimension r is called the length function and is denoted by ℓ _q (r, R). Constructions of codes with covering radius 3 are here developed, which improve best known upper bounds on ℓ _q (r, 3). General constructions are given and upper bounds on ℓ _q (r, 3) for q = 3, 4, 5, 7 and r ≤ 24 are tabulated.     

On the covering radius of long binary BCH codes

It is proved that the covering radius of long binary BCH codes with designed distance 2t + 1 is at most 2t.     

The covering radius of extreme binary 2-surjective codes

The covering radius of binary 2-surjective codes of maximum length is studied in the paper. It is shown that any binary 2-surjective code of M codewords and of length has covering radius if M − 1 is a power of 2, otherwise . Two different combinatorial proofs of this assertion were found by the author. The first proof, which is written in the paper, is based on an existence theorem for k-uniform hypergraphs where the degrees of its vertices are limited by a given upper bound. The second proof, which is omitted for the sake of conciseness, is based on Baranyai’s theorem on l-factorization of a complete k-uniform hypergraph.      

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.     

On a class of binary linear completely transitive codes with arbitrary covering radius

An infinite class of new binary linear completely transitive (and so, completely regular) codes is given. The covering radius of these codes is growing with the length of the code. In particular, for any integer ρ≥2, there exist two codes in the constructed class with d=3, covering radius ρ and lengths and , respectively. The corresponding distance-transitive graphs, which can be defined as coset graphs of these completely transitive codes are described.     

The covering radius of PGL2(q)

The covering radius of a subset $C$ of the symmetric group ${\mathrm{S}}_n$ is the maximal Hamming distance of an element of ${\mathrm{S}}_n$ from $C$. This note determines the covering radii of the finite $2$-dimensional projective general linear groups. It turns out that the covering radius of ${\mathrm{PGL}}_2\left(q\right)$ is $q?2$ if $q$ is even, and is $q?3$ if $q$ is odd.     

On the minimum average distance of binary constant weight codes

Let β(n,M,w) denote the minimum average Hamming distance of a binary constant weight code with length n, size M and weight w. In this paper, we study the problem of determining β(n,M,w). Using the methods from coding theory and linear programming, we derive several lower bounds on the average Hamming distance of a binary constant weight code. These lower bounds enable us to determine the exact value for β(n,M,w) in several cases.     

A family of constacyclic ternary quasi-perfect codes with covering radius 3

In this paper a family of constacyclic ternary quasi-perfect linear block codes is presented. This family extends the result presented in a previous work by the first two authors, where the existence of codes with the presented parameters was stated as an open question. The codes have a minimum distance 5 and covering radius 3.     

Quantum MDS codes with relatively large minimum distance from Hermitian self-orthogonal codes

It has become common knowledge that constructing q-ary quantum MDS codes with minimum distance bigger than \(q/2+1\) is significantly more difficult than constructing those with minimum distance less than or equal to \(q/2+1\). Despite of various constructions of q-ary quantum MDS codes, all known q-ary quantum MDS codes have minimum distance bounded by \(q/2+1\) except for some lengths. The purpose of the current paper is to provide some new q-ary quantum MDS codes with minimum distance bigger than \(q/2+1\). In this paper, we provide several classes of quantum MDS codes with minimum distance bigger than \(q/2+1\). For instance, some examples in these classes include q-ary \([n,n-2k, k+1]\)-quantum MDS codes for cases: (i) \(q\equiv -1\bmod {5}, n=(q^2+4)/5\) and \(1\le k\le (3q-2)/5\); (ii) \(q\equiv -1\bmod {7}, n=(q^2+6)/7\) and \(1\le k\le (4q-3)/7\); (iii) \(2|q, q\equiv -1\bmod {3}, n=2(q^2-1)/3\) and \(1\le k\le (2q-1)/3\); and (iv) \(2|q, q\equiv -1\bmod {5}, n=2(q^2-1)/5\) and \(1\le k\le (3q-2)/5\).     

On the minimum distance graph of an extended Preparata code

The minimum distance graph of an extended Preparata code P(m) has vertices corresponding to codewords and edges corresponding to pairs of codewords that are distance 6 apart. The clique structure of this graph is investigated and it is established that the minimum distance graphs of two extended Preparata codes are isomorphic if and only if the codes are equivalent.     

Quantum MDS codes with new length and large minimum distance

According to the well-known CSS construction, constructing quantum MDS codes are extensively investigated via Hermitian self-orthogonal generalized Reed-Solomon (GRS) codes. In this paper, given two Hermitian self-orthogonal GRS codes $GR{S}_{k_1}(A,{\mathit{v}}_A)$ and $GR{S}_{k_2}(B,{\mathit{v}}_B)$, we propose a sufficient condition to ensure that $GR{S}_k(A\cup B,{\mathit{v}}_{A\cup B})$ is still a Hermitian self-orthogonal code. Consequently, we first present a new general construction of infinitely families of quantum MDS codes from known ones. Moreover, applying the trace function and norm function over finite fields, we give another two new constructions of quantum MDS codes with flexible parameters. It turns out that the forms of the lengths of our quantum MDS codes are quite different from previous known results in the literature. Meanwhile, the minimum distances of all the q-ary quantum MDS codes are bigger than $q/2+1$.     

A random construction for permutation codes and the covering radius

We analyse a probabilistic argument that gives a semi-random construction for a permutation code on n symbols with distance n − s and size Θ(s!(log n)^1/2), and a bound on the covering radius for sets of permutations in terms of a certain frequency parameter.