Linear nonbinary covering codes and saturating sets in projective spaces

Blocking sets, ovals, (k)-arcs (51E21) Linear codes and caps in Galois spaces (51E22) Linear codes (general theory) (94B05) Combinatorial codes (94B25) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Bounds on codes (94B65)

Abstract: Let A_{R,q} denote a family of covering codes, in which the covering radius R and the size q of the underlying Galois field are fixed, while the code length tends to infinity. In this paper, infinite sets of families A_{R,q}, where R is fixed but q ranges over an infinite set of prime powers are considered, and the dependence on q of the asymptotic covering densities of A_{R,q} is investigated. It turns out that for the upper limit of the covering density of A_{R,q}, the best possibility is O(q). The main achievement of the present paper is the construction of asymptotic optimal infinite sets of families A_{R,q} for any covering radius R >= 2. We first showed that for a given R, to obtain optimal infinite sets of families it is enough to construct R infinite families A_{R,q}^{(0)},A_{R,q}^{(1)},...,A_{R,q}^{(R-1)} such that, for all u >= u_{0}, the family A_{R,q}^{(v)} contains codes of codimension r_{u}=Ru+v and length f_{q}^{v}(r_{u}) where f_{q}^{v}(r)=O(q^{(r-R)/R) and u_{0} is a constant. Then, we were able to construct the needed families A_{R,q}^{(v)} for any covering radius R >= 2, with q ranging over the (infinite) set of R-th powers. For each of these families A_{R,q}^{(v)}, the lower limit of the covering density is bounded from above by a constant independent of q.

Review text

The covering radius of an \([n,n-r]_q\) code is the smallest integer \(R\) such that the space \(\mathbb F_q^n\) is covered by the spheres of radius \(R\) centered at the codewords of the code. The covering problem for linear codes is the problem of finding linear codes with small covering radius with respect to their length and dimension. Linear codes investigated from the point of view of the covering problem are called covering codes. The covering problem for linear codes is closely related to the problem of saturating sets in finite projective spaces. This link is used by the authors. They concentrate on finding families \({\mathcal A}_{R,q}\) of covering codes in which the covering radius \(R\) and the size \(q\) of the underlying finite field are fixed while the code length tends to infinity, and which have small asymptotic covering densities. The key method of the authors is the design of new small saturating sets in finite projective spaces, which are then used as the starting point for the \(q^m\)-concatenating constructions of covering codes. In particular, the concept of \(N\)-fold strong blocking sets is introduced in this study. The authors also provide new tables of the upper bounds on the covering radius of linear codes.

Recommendations

Cited in

(49)

This page was built for publication: Linear nonbinary covering codes and saturating sets in projective spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q534526)