2023/10/04 by Alexander A. Davydov, Davydov, Alexander A., Stefano Marcugini +3
Computer Science · Engineering · #51E21 #51E22 #94B05 #Coding theory and cryptography #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2310.02715
openalex publication_date 2023/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The length function ℓq(r,R) is the smallest possible length n of a q -ary linear [n,n-r]qR code with codimension (redundancy) r and covering radius R. Let sq(N,ρ) be the smallest size of a ρ-saturating set in the projective space PG(N,q). There is a one-to-one correspondence between [n,n-r]qR codes and (R-1)-saturating n-sets in PG(r-1,q) that implies ℓq(r,R)=sq(r-1,R-1). In this work, for R≥3, new asymptotic upper bounds on ℓq(tR+1,R) are obtained in the following form: \hspace0.7cm \bullet~ℓq(tR+1,R) =sq(tR,R-1)≤ √[R]\fracR!RR-2⋅ q(r-R)/R⋅√[R]ln q+o(q(r-R)/R), \hspace0.3cmr=tR+1,~t≥1,~ q is an arbitrary prime power,~q is large enough; \hspace0.7cm \bullet~ if additionally R is large enough, then √[R]\fracR!RR-2\thicksim(1)/(e)\thickapprox0.3679. The new bounds are essentially better than the known ones. For t=1, a new construction of (R-1)-saturating sets in the projective space PG(R,q), providing sets of small sizes, is proposed. The [n,n-(R+1)]qR codes, obtained by the construction, have minimum distance R + 1, i.e. they are almost MDS (AMDS) codes. These codes 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.