CS Paper Radar

Generalized Covering radii and Deep Holes of a Family of Antiprimitive Narrow-Sense BCH Codes in Even Characteristic

Ketong Ren, Bing Liu, Cuiling Fan, Haode Yan

cs.IT ·submitted 2026-11-19 02:02 UTC · v1

Abstract

This paper determines the generalized covering radii, deep holes, and complete coset leader weight distribution of the antiprimitive narrow-sense BCH code of length \(q+1\) and designed distance \(3\) over \(\mathbb{F}_q\), where \(q=2^m\) and \(m\geq 2\). We establish the complete generalized covering-radius hierarchy: the covering radius is \(3\), whereas the \(t\)-th generalized covering radius is \(4\) for every \(t\geq 2\). Using the covering radius, we then derive necessary and sufficient conditions for a received word to be a deep hole by reducing the syndrome representations to conditions involving roots of an associated cubic polynomial. An explicit parametrization yields complete, nonredundant representatives of all deep-hole cosets. Enumerating these representatives gives closed-form expressions for the numbers of deep holes and determines the complete coset leader weight distribution, with distinct formulas according to the parity of \(m\).

Closest papers

Nearest neighbours by meaning across the whole index.

Covering Radius and Deep Holes of Hyperderivative Reed-Solomon Codes under the NRT Metric

cs.IT ·2026-10-12 ·Zhihao Zhu, Haojie Gu, Jun Zhang, Yu Li
similarity 0.70
Abstract

The deep hole problem is a fundamental problem in coding theory, and it has many important applications in code constructions and cryptography. The deep hole problem of Reed-Solomon codes has gained a lot of attention. As a generalization of Reed-Solomon codes under Hamming metric, we study the covering radius and deep holes of Hyperderivative Reed-Solomon (HRS) codes under the Niederreiter-Rosenbloom-Tsfasman (NRT) metric. We determine the NRT covering radius of HRS code and characterize its NRT deep holes via Maximum Distance Separable (MDS) extensions and polynomial remainder conditions. We further relate the enumeration of NRT deep holes to the characteristic polynomial of an associated hyperplane arrangement. We also provide three classes of explicit NRT deep-hole constructions, propose a Cheng-Murray type conjecture for HRS codes under the NRT metric and obtain a conditional low-layer description. Using these characterizations, we derive exact enumeration formulas in several special cases.

0.19

Auxiliary Codes and the Generalized Packing-Covering Conjecture

cs.IT ·2026-09-16 ·Isaac Barouch Essayag, Aryeh Lev Zabokritskiy
theory similarity 0.70
Abstract · 10 pages, 2 tables. Revised exposition and references; clarified the auxiliary-code method and improved presentation

The generalized packing--covering conjecture asks whether, at every order, the packing radius of a linear code is at most its covering radius. We prove the conjecture for every linear code of redundancy at most fourteen over every finite field, extending the previously established range of redundancies at most seven. We also prove the bound on generalized Hamming weights $d_t(C)\le2R_t(C)+1$ whenever the alphabet size $q$ satisfies $q\ge R_t(C)$. Both results use an auxiliary-code criterion that converts a covering property in the syndrome space into a weight bound. For binary primitive BCH codes, the packing radius is strictly smaller than the covering radius for every fixed error parameter and order, both at least two, once the extension degree is sufficiently large; this follows from existing covering bounds.

0.37

Norm-One Torus Decompositions and Decoding of Gashkov-Sidel'nikov Codes

cs.IT math.CO ·2026-09-17 ·Minjia Shi, Shitao Li, Yuhong Xia, Tor Helleseth, Ferruh Ozbudak
similarity 0.69
Abstract

Let $q=3^m$, let $K=\mathbb F_{q^2}$, and let \[\mathcal T=\{x\in K^*:\operatorname{N}_{K/\mathbb F_q}(x)=1\}.\] For both cyclic and constacyclic Gashkov-Sidel'nikov codes, we show that the set of signed parity-check column labels is precisely $\mathcal T$. Consequently, the decoding problem separates into two stages: determining the minimum error weight associated with a syndrome $S$ and constructing an error vector attaining this minimum. We identify the former quantity with the minimum additive length of $S$ with respect to $\mathcal T$ and determine it exactly by the norm and the quadratic character of $\mathbb F_q$. We also determine the complete coset-weight distribution and recover the known covering radius $3$. For the constructive part, we use quadratic-character sums and Weil bounds to construct a coset leader for every syndrome of coset weight three. The resulting procedures give complete maximum-likelihood decoders.

0.23

The generalized covering radii of Melas codes

cs.IT ·2026-08-30 ·Shuxing Li, Maosheng Xiong
theory similarity 0.68
Abstract · We have updated the references to reflect recent literature on this topic. In addition, we have clarified the relationship between our work …

The generalized covering radii have recently emerged as fundamental parameters of linear codes with applications to database linear querying. In this paper, we study the generalized covering radii $ρ_t(M(m,q))$ of Melas codes $M(m,q)$ over any finite field $\mathbb{F}_q$. We determine $ρ_2(M(m,q))$ for all $q$, and for a general $t \ge 3$, we prove that $ρ_t(M(m,q)) \in \left\{2t,2t+1\right\}$ for $q \in \{2,3\}$ and $ρ_t(M(m,q))=2t$ for $q \ge 4$ whenever $m$ is sufficiently large. These results extend recent work on the covering radius of Melas codes.

0.39

Subspace coverings and generalized covering radii of generalized Zetterberg codes

cs.IT math.CO ·2026-09-20 ·Shitao Li, Yang Li, Gaojun Luo, Zhonghua Sun
theory similarity 0.68
Abstract

Generalized covering radii measure how many columns of a parity-check matrix are needed to generate several syndromes simultaneously. Their finite-geometric counterparts are $(ρ,t)$-saturating sets, for which every $t$-dimensional subspace is contained in a subspace generated by at most $ρ$ prescribed vectors. We investigate this covering problem for the norm-one configurations associated with generalized Zetterberg codes. We establish the upper bound $2t+1$ over every nonbinary finite field and in an explicit binary range, together with complementary lower bounds obtained by counting subspaces and constructing subfield obstructions. For an explicit range of large $t$, these configurations are $t$-strong blocking sets, and the $t^{\rm th}$ generalized covering radius attains its minimum possible value $t$. For binary Zetterberg codes, we determine the second generalized covering radius in every extension degree and prove that the third radius is seven for an infinite subfamily.

0.35

Asymptotic Bounds on Generalized Covering Radii of Binary Primitive BCH Codes

cs.IT math.CO ·2026-08-31 ·Maosheng Xiong, Chi Hoi Yip, Ferdinando Zullo
theoryhighly cited similarity 0.67
Abstract

Fix integers $e\ge2$ and $r\ge1$. In this paper we study the $r$-th generalized covering radius $ρ_r\left(BCH(e,m)\right)$ of the binary primitive $e$-error-correcting BCH code $BCH(e,m)$. By using an algebraic-geometric reformulation of the covering problem together with an explicit Lang-Weil estimate, we prove that \[ρ_r\bigl(\BCH(e,m)\bigr)\le(r+1)e-1\] for all sufficiently large $m$. For $e\ge7$, this improves a recent result of Belinsky--Zabokritskiy. Our proof gives a substantially simpler geometric approach to this upper bound. In particular it implies that \[ρ_2\bigl(BCH(e,m)\bigr)=3e-1\] for all sufficiently large $m$. Previously it was only known that \[ρ_2\bigl(\BCH(e,m)\bigr) \in \left\{3e-1,3e\right\}\] for all sufficiently large $m$.

0.44

Asymptotically Tight Bounds for Generalized Covering Radii of Binary Primitive BCH Codes at All Higher Orders

cs.IT ·2026-08-24 ·Zeev Vladimir Belinsky, Aryeh Lev Zabokritskiy
theoryhighly cited similarity 0.67
Abstract · 56 pages. Revised version with a componentwise degree bound improving the sufficient field-size threshold for the known common-core support …

We study the generalized covering radii of binary primitive BCH codes, which measure how many parity-check columns suffice to span several prescribed syndromes. For the four-error-correcting family of length $2^m-1$, the second radius is exactly $11$ for $m\geq55$, and it is either $11$ or $12$ for $m\geq16$. For every fixed error parameter at least two, we give an explicit stable bound with two adjacent possible values for the second radius and an arithmetic criterion for exactness. At every higher order, we obtain explicit lower and upper bounds whose additive gap is bounded independently of the order for each fixed error parameter, once explicit field-size conditions hold. The bounds are therefore asymptotically tight as the order grows. The higher-order upper bound retains the common-core support count established by Xiong, Yip, and Zullo; our refinement reduces its sufficient field-size threshold at large order. The refinement combines componentwise mixed degrees with the ordinary degree of a multicone. The upper bounds come from constructing syndrome representations with a common set of parity-check columns.

0.50

Quaternary Preparata codes are quasi-perfect covering codes in the Hamming metric

cs.IT ·2026-09-27 ·Tamal Maharaj
theory similarity 0.66
Abstract

The quaternary Preparata codes of Hammons, Kumar, Calderbank, Sloane and Solé are $\mathbb{Z}_4$-linear codes of length $2^m$ with $4^{2^m-m-1}$ codewords. They are usually studied through their binary Gray images, that is, in the Lee metric. We consider them instead as codes over a 4-letter alphabet with the Hamming metric. We show that for odd $m$ they have covering radius 2 and minimum distance 4, so they are quasi-perfect. For even $m$ the same construction has covering radius 3. The proof is a short computation with Teichmüller representatives in the Galois ring $\mathrm{GR}(4,m)$, and it also gives the coset weight distribution. The covering density of these codes tends to $9/8$. The best previously known infinite families of quaternary codes with covering radius 2 have covering density about 1.5. Consequently $K_4(n,2)\le 4^{n-m-1}$ for all $n\ge 2^m$ and odd $m$, which improves the best available bounds for a range of lengths above each $2^m$. For $m=3$ the code is the octacode, and it gives $K_4(8,2)\le 256$; the previous bound was 352, from 2005, and the best lower bound is 251. We also give a quaternary code showing $K_4(6,2)\le 48$, where the previous bound was 52, together with consequences for larger alphabets.

0.07