Resolution of a Conjecture on the Covering Radius of Linear Codes

The covering radius of a q-ary block code C of length n is defined as the smallest integer \(R=R(C)\) such that all vectors in \(\mathbb {F}_{q}^n\) are within Hamming distance R of some codeword of C. By [n, k, d]R code, we mean an [n, k, d] code having covering radius R. The covering radius of a code is one of the fundamental parameters of a code and gives its suitability for data compression, list decoding radius, and has many other applications. The upper bound of Janwa (1986) relates all the fundamental parameters as \(R(C)\le \mathscr {H}(C):=n-\sum _{i=1}^{k}\lceil \frac{d}{2^i} \rceil \) . Which can be expressed as \(n-g_{q}+d-\lceil d/q^{k}\rceil \) . If \(n_{q}(k,d)\) denotes the minimum length of any code of dimension k and distance over \(\mathbb {F}_{q}\) it was conjectured by Janwa that under certain conditions \(g_{q}(k,d)\) (the Griesmer length) can be replaced by \(n_{q}(k,d)\) . Janwa (1989) and Janwa and Mattson (1999), proved three of the four cases and conjectured that the final case is true. In this article, we give a resolution of this conjecture. These bounds have helped us in determing the exact covering radius of codes from Hermitian curves in most cases, and yielding close bounds in the rest of them.