2021/08/31 by Davydov, Alexander A., Marcugini, Stefano, Pambianco, Fernanda
#51E21 #51E22 #94B05 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2108.13609
The length function ℓq(r,R) is the smallest length of a q -ary linear code with codimension (redundancy) r and covering radius R. In this work, new upper bounds on ℓq(tR+1,R) are obtained in the following forms: \beginsplit amp;(a)~ℓq(r,R)≤ cq(r-R)/R⋅√[R]ln q,~ R≥3,~r=tR+1,~t≥1, amp;\phantom(a)~ q is an arbitrary prime power,~c is independent of q. \endsplit \beginsplit amp;(b)~ℓq(r,R)lt; 3.43Rq(r-R)/R⋅√[R]ln q,~ R≥3,~r=tR+1,~t≥1, amp;\phantom(b)~ q is an arbitrary prime power,~q is large enough. \endsplit In the literature, for q=(q')R with q' a prime power, smaller upper bounds are known; however, when q is an arbitrary prime power, the bounds of this paper are better than the known ones. For t=1, we use a one-to-one correspondence between [n,n-(R+1)]qR codes and (R-1)-saturating n-sets in the projective space PG(R,q). A new construction of such saturating sets providing sets of small size is proposed. Then the [n,n-(R+1)]qR codes, obtained by geometrical methods, are taken as the starting ones in the lift-constructions (so-called "qm-concatenating constructions") for covering codes to obtain infinite families of codes with growing codimension r=tR+1, t≥1.