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

Abstract

The length function ${\ell }_q(r,R)$ is the smallest length of a $q$-ary linear code of codimension (redundancy) $r$ and covering radius $R$. The $d$-length function ${\ell }_q(r,R,d)$ is the smallest length of a $q$-ary linear code with codimension $r$, covering radius $R$, and minimum distance $d$. By computer search in wide regions of $q$, we obtained following short codes of covering radius $R=3$: $[n,n-4,5{]}_{q}3$ quasi-perfect MDS codes, $[n,n-5,5{]}_{q}3$ quasi-perfect Almost MDS codes, and $[n,n-5,3{]}_{q}3$ codes. In computer search, we use the step-by-step leximatrix and inverse leximatrix algorithms to obtain parity check matrices of codes. The new codes imply the following new upper bounds (called lexi-bounds) on the length and $d$-length functions: $${\ell }_q(4,3)\le {\ell }_q(4,3,5)<2.8\sqrt[3]{\ln q}\cdot q^{(4-3)/3}=2.8\sqrt[3]{\ln q}\cdot \sqrt[3]{q}=2.8\sqrt[3]{q\ln q}\text{for}11\le q\le 7057;$$ $${\ell }_q(5,3)\le {\ell }_q(5,3,5)<3\sqrt[3]{\ln q}\cdot q^{(5-3)/3}=3\sqrt[3]{\ln q}\cdot \sqrt[3]{q^2}=3\sqrt[3]{q^2\ln q}\text{ for }37\le q\le 839.$$ Moreover, we improve the lexi-bounds, applying randomized greedy algorithms, and show that $${\ell }_q(4,3)\le {\ell }_q(4,3,5)<2.61\sqrt[3]{q\ln q}\text{ if }13\le q\le 4373;$$ $${\ell }_q(4,3)\le {\ell }_q(4,3,5)<2.65\sqrt[3]{q\ln q}\text{ if }4373<q\le 7057;$$ $${\ell }_q(5,3)<2.785\sqrt[3]{q^2\ln q}\text{ if }11\le q\le 401;$$ $${\ell }_q(5,3)\le {\ell }_q(5,3,5)<2.884\sqrt[3]{q^2\ln q}\text{ if }401<q\le 839.$$ The codes, obtained in this paper by leximatrix and inverse leximatrix algorithms, provide new upper bounds (called density lexi-bounds) on the smallest covering density ${\mu }_q(r,R)$ of a $q$-ary linear code of codimension $r$ and covering radius $R$: $${\mu }_q(4,3)<3.3\cdot \ln q\text{ for }11\le q\le 7057;$$ $${\mu }_q(5,3)<4.2\cdot \ln q\text{ for }37\le q\le 839.$$

51 pages, 14 figures, 5 tables, 35 references; new results of computer search are added

Cited by in corpus (1)

• List-decodable Codes and Covering Codes