vix.ing · top · new · best · stats · spec

Tables, bounds and graphics of short linear codes with covering radius 3\n and codimension 4 and 5

2017/12/19 by Daniele Bartoli, Alexander A. Davydov, Bartoli, Daniele +5
Computer Science · Engineering · Medicine · #Cancer Mechanisms and Therapy #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1712.07078

openalex publication_date 2017/12/19 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28

Abstract

The length function \ℓq(r,R) is the smallest length of a q-ary linear\ncode of codimension (redundancy) r and covering radius R. The d-length\nfunction \ℓq(r,R,d) is the smallest length of a q-ary linear code with\ncodimension r, covering radius R, and minimum distance d. By computer\nsearch in wide regions of q, we obtained following short codes of covering\nradius R=3: [n,n-4,5]q3 quasi-perfect MDS codes, [n,n-5,5]q3\nquasi-perfect Almost MDS codes, and [n,n-5,3]q3 codes. In computer search,\nwe use the step-by-step leximatrix and inverse leximatrix algorithms to obtain\nparity check matrices of codes. The new codes imply the following new upper\nbounds (called lexi-bounds) on the length and d-length functions:\n
ellq(4,3)
le
ellq(4,3,5)lt;2.8
sqrt[3]
ln q
cdot\nq(4-3)/3=2.8
sqrt[3]
ln q
cdot
sqrt[3]q=2.8
sqrt[3]q
ln\nq~
textfor~11
le q
le7057;
ellq(5,3)
le
ellq(5,3,5)lt;3
sqrt[3]
ln\nq
cdot q(5-3)/3=3
sqrt[3]
ln q
cdot
sqrt[3]q2=3
sqrt[3]q2
ln\nq~~
text for ~37
le q
le839. Moreover, we improve the lexi-bounds,\napplying randomized greedy algorithms, and show that
ellq(4,3)
le\n
ellq(4,3,5)lt; 2.61
sqrt[3]q
ln q~
text if ~13
le q
le4373;\n
ellq(4,3)
le
ellq(4,3,5)lt; 2.65
sqrt[3]q
ln q~
text if\n~4373lt;q
le7057;
ellq(5,3)lt;2.785
sqrt[3]q2
ln q~
text if ~11
le\nq
le401;
ellq(5,3)
le
ellq(5,3,5)lt;2.884
sqrt[3]q2
ln q~
text if\n~401lt;q
le839. The codes, obtained in this paper by leximatrix and inverse\nleximatrix algorithms, provide new upper bounds (called density lexi-bounds) on\nthe smallest covering density \μq(r,R) of a q-ary linear code of\ncodimension r and covering radius R:
muq(4,3)lt;3.3
cdot
ln q~~
text for\n~11
le q
le7057;
muq(5,3)lt;4.2
cdot
ln q~~
text for ~37
le q
le839.\n

Related