CS Paper Radar

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

Minjia Shi, Shitao Li, Yuhong Xia, Tor Helleseth, Ferruh Ozbudak

cs.IT math.CO ·submitted 2026-09-17 13:49 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.IT ·2026-11-19 ·Ketong Ren, Bing Liu, Cuiling Fan, Haode Yan
similarity 0.69
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\).

0.15

Maximum-Likelihood Decoding of Gabidulin Codes Is NP-Hard Even in Dimension One

cs.CR cs.IT ·2026-10-25 ·Philippe Gaborit
theoryhot direction similarity 0.67
Abstract · in submission

Fix a prime power q. We prove that deciding whether a received word y in Fnqm lies at rank distance at most n-2 from the one-dimensional Gabidulin code {{λ.g : λ in Fqm } is NP-complete. Thus maximum-likelihood decoding of Gabidulin codes is NP-hard even for k = 1, an analogue of the Guruswami-Vardy theorem for Reed-Solomon codes. In the Hamming metric, by contrast, hardness at this radius requires the dimension to grow with the length, as in the Guruswami-Vardy theorem. The reduction is deterministic; consequently Rank Syndrome Decoding (RSD) and Rank Minimum Distance (RMD) for Fqm -linear codes are NP-complete under deterministic polynomial reductions, whereas the previously known reduction was randomized. The proof goes through a pivot problem that we introduce, Twisted Square Membership (TSM): given Fq-subspaces U, W in FqN , decide whether some non-zero a in U satisfies a^(q+1) in W . Quadratic systems in d unknowns are encoded into TSM, then TSM into Gabidulin decoding. The last step views the received word as an Fq-linear map and decoding at radius n - 2 as the search for an Fq-plane on which it acts as a scalar. With support U + τ W in a cubic extension and map a + τ b to a^(q^2) + τ bq^q , two Frobenius twists force solution planes to encode the relation a^(q+1) in W . All constructions are explicit and polynomial, with N = O(qd^2 ), n less than N + d, and m = 3N .

0.50

Asymptotic Bounds for Codes in Toroidal Distance

cs.IT ·2026-11-19 ·Pengjie Zhong, Jinquan Luo
theory similarity 0.67
Abstract

The toroidal distance naturally describes the geometry of codes over \(\mathbb Z_q\), where distances are measured modulo \(q\). In this paper, we study asymptotic bounds for codes in \(\mathbb Z_q^n\) under the toroidal metric. We first derive an explicit asymptotic lower bound from the classical Gilbert--Varshamov bounds for the Hamming and Lee metrics, which serves as a baseline for comparison. We then develop a saddle-point approach for the toroidal metric, which yields an asymptotic Gilbert--Varshamov lower bound and an asymptotic Hamming-type upper bound. For \(3\mid q\), we embed ternary Hamming codes into \(\mathbb Z_q^n\) and obtain another asymptotic lower bound for the toroidal metric. In addition, we derive an asymptotic lower bound for Maximum Toroidal Distance (MTD) codes. We compare these lower bounds with the baseline and prove that they are nontrivial in the corresponding parameter ranges. Finally, we compare the asymptotic bounds numerically.

0.15

Cyclically covering subspaces and additive perfect codes

cs.IT math.COmath.NT ·2026-11-09 ·Yangcheng Li, Pingzhi Yuan
theory similarity 0.66
Abstract · 20 pages

Let $h_q(n)$ be the largest codimension of a subspace of $\mathbb{F}_q^n$ whose cyclic shifts cover the whole space. For $r>0$, we characterize the inequality $h_q(n)\ge r$ in terms of cyclic $\mathbb{F}_q$-linear codes over vector alphabets with covering radius one, no nonzero word of block weight one, and a scalar dual generated by the shifts of one word. For $k,m\ge2$, let $I_q(j)$ count the monic irreducible polynomials of degree $j$ over $\mathbb{F}_q$. If $k$ is prime or $m\ge2\sum_{j=1}^{k-1}I_q(j)+2$, we prove that a cyclic $\mathbb{F}_q$ linear perfect code of length $\frac{q^{km}-1}{q^k-1}$ over $\mathbb{F}_q^k$ exists if and only if $\gcd(m,q-1)=1$. When this condition holds, we also obtain \(h_q\!\left(\frac{q^{km}-1}{q^k-1}\right)=k(m-1).\) Restriction of scalars gives the same criterion for every $m\ge2$ when $q$ is odd, $q+1$ is a power of two, and $k=2p$ with $p$ prime. We also show that $h_q(q^k+1)=k$ exactly when $q$ is even, for every $k\ge1$.

0.12

NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes

cs.CC ·2026-09-24 ·Daqing Wan, Jun Zhang
theory similarity 0.66
Abstract · 31 pages

For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding radius is $d$ below the covering radius for every $1\le d\le c\log n/\log\log n$, where $c>0$ is an absolute constant. We prove that, for every fixed rational $0<α<1/2$, bounded-distance decoding is NP-complete under deterministic polynomial-time many-one reductions over explicitly represented finite extension fields for the additive gap $d=\lfloor n^α\rfloor$ below the covering radius. The hard codes have odd block length~$n$, dimension $K=(n+1)/2-d$, decoding radius $(n-1)/2$, and rate tending to $1/2$. The alphabet size is subexponential in the evaluation set size: for a fixed $0<η<1$ depending only on $α$, it is $2^{Θ(n^η\log n)}=2^{o(n)}$. The proof passes through moments subset sum on $n-1$ nonzero field elements, with required subset size $(n-1)/2$ and $d$ prescribed moments. The arithmetic ingredient is a uniform positive-completion theorem over prime fields $\mathbb{F}_q$ with $q\ge d^{2+ρ}$, for any fixed $ρ>0$. A sharper form follows from a higher-dimensional point-count estimate based on Deligne's theorem; the weaker form used in our reduction is proved more elementarily using additive-character orthogonality, the one-variable Weil bound, a moment identity of order $2d$, and Newton identities. A universal completion pool, an extension-field quotient construction, and a deterministic linear-size simultaneous power condenser complete the reduction.

0.10

Breaking linearity in the sum-rank metric: MSRD codes from switched $σ$-rational normal curves

cs.IT math.CO ·2026-10-08 ·Daniele Bartoli, Giovanni Giuseppe Grimaldi, Giovanni Longobardi
similarity 0.66
Abstract

We construct a family of scalar-closed, non-additive maximum sum-rank distance codes (MSRD) by switching norm components of a $σ$-rational normal curve and lifting the resulting point set through a linearized Reed--Solomon syndrome map. We characterize the admissible switches by a multiplicative stability condition on the norm classes. In particular, for $1 \leq n_i \leq m$, $N=n_1+\ldots+n_{\ell}$ and $2\leqδ\leq N-1$, every partition of $\mathbb{F}_q^*$ satisfying a specific condition, referred to as Condition $(\diamond)$, yields a code in $\mathbb{F}_{q^m}^{N}$ of size $q^{m(N-δ+1)}$ and minimum sum-rank distance $δ$; the code is non-additive whenever a curve component is retained. For $\ell\geq2$ these appear to be the first non-additive MSRD codes in the literature, all previously known families with more than one block being $\mathbb{F}_q$-linear. Moreover, every code of the family has the same sum-rank weight distribution as an $\mathbb{F}_{q^m}$-linear MSRD code with the same parameters, although the geometry of the switched set distinguishes it from linearized Reed--Solomon codes. In the single-block case, an explicit rank isometry identifies the construction with the cone codes of Durante, Grimaldi and Longobardi.

0.36

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.66
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.36

Minimum distances of primitive narrow-sense BCH codes via good zero-sets

cs.IT ·2026-09-18 ·Run Zheng
similarity 0.65
Abstract

Determining the exact minimum distances of BCH codes remains a open problem. We establish the minimum distances of several families of primitive narrow-sense BCH codes, showing that they attain their designed distances. Our approach centers on $\mathbb{F}_q$-good zero-sets, which we introduce through a derivative condition on their vanishing polynomials. We show that a $q$-ary primitive narrow-sense BCH code of length $q^m-1$ and designed distance $2\leqδ\leq q^m-1$ has minimum distance $δ$ if and only if there exists an $\mathbb{F}_q$-good zero-set of cardinality $δ+1$ in the finite field $\mathbb{F}_{q^m}$ with $q^m$ elements. To construct $\mathbb{F}_q$-good zero-sets, we develop several methods based on polynomial substitutions, power maps, and shifted inverses, as well as direct constructions using polynomials of special forms. Together with suitable initial $\mathbb{F}_q$-good zero-sets, including those arising from known minimum-distance results, these methods yield new good zero-sets of various cardinalities and hence families of primitive narrow-sense BCH codes whose minimum distances equal their designed distances. These families cover a broad range of designed distances, with several known minimum-distance results recovered as special cases.

0.38