跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.21888 · v1

A polynomial-time decoding algorithm up to half the square-root bound for quadratic residue and generalized quadratic residue codes

首次提交 2026-11-17 04:58
版本更新 2026-11-17 04:58
雷达观测 2026-11-18 19:44
arXiv ↗PDF ↗

摘要

Binary quadratic residue (QR) codes, introduced by Prange in 1958, are cyclic codes of prime length p≡±1(mod8)p\equiv\pm1\pmod 8 and dimension (p+1)/2(p+1)/2 whose minimum distance satisfies the square-root bound d≥pd\ge\sqrt p. They include the Hamming code [7,4,3][7,4,3] and the Golay code [23,12,7][23,12,7], and were generalized by van Lint and MacWilliams to generalized quadratic residue (GQR) codes of prime-power length qq, for which the bound d≥qd\ge\sqrt q still holds and is attained when qq is a square. In coding theory, one usually first finds a lower bound on the minimum distance of a family of codes, and then a polynomial-time algorithm decoding up to half of this bound, as for BCH, Reed--Muller or Gabidulin codes. Until now, GQR codes had resisted this approach: no such algorithm was known, apart from individual short lengths. We give a deterministic algorithm which, for every odd prime power q≡±1(mod8)q\equiv\pm1\pmod 8, corrects every error pattern of weight at most ⌊(q−1)/2⌋\lfloor(\sqrt q-1)/2\rfloor in the binary GQR code of length qq, in O(q9/2)O(q^{9/2}) operations in $\F_q$. We start from a description of QR codes due to Helleseth, which we extend to GQR codes, and in which the syndrome gives the values of the quadratic character of the error-locator polynomial. We then recover this polynomial by adapting to GQR codes the tools that Kopparty developed for recovering polynomials from noisy character values, with the decoding of dual BCH codes as an application. Since the square-root bound is attained when qq is a square, this radius is the largest that can be guaranteed uniformly on the class of GQR codes.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-17 04:58 · 最新观测版本

A polynomial-time decoding algorithm up to half the square-root bound for quadratic residue and generalized quadratic residue codes

Binary quadratic residue (QR) codes, introduced by Prange in 1958, are cyclic codes of prime length p≡±1(mod8)p\equiv\pm1\pmod 8 and dimension (p+1)/2(p+1)/2 whose minimum distance satisfies the square-root bound d≥pd\ge\sqrt p. They include the Hamming code [7,4,3][7,4,3] and the Golay code [23,12,7][23,12,7], and were generalized by van Lint and MacWilliams to generalized quadratic residue (GQR) codes of prime-power length qq, for which the bound d≥qd\ge\sqrt q still holds and is attained when qq is a square. In coding theory, one usually first finds a lower bound on the minimum distance of a family of codes, and then a polynomial-time algorithm decoding up to half of this bound, as for BCH, Reed--Muller or Gabidulin codes. Until now, GQR codes had resisted this approach: no such algorithm was known, apart from individual short lengths. We give a deterministic algorithm which, for every odd prime power q≡±1(mod8)q\equiv\pm1\pmod 8, corrects every error pattern of weight at most ⌊(q−1)/2⌋\lfloor(\sqrt q-1)/2\rfloor in the binary GQR code of length qq, in O(q9/2)O(q^{9/2}) operations in $\F_q$. We start from a description of QR codes due to Helleseth, which we extend to GQR codes, and in which the syndrome gives the values of the quadratic character of the error-locator polynomial. We then recover this polynomial by adapting to GQR codes the tools that Kopparty developed for recovering polynomials from noisy character values, with the decoding of dual BCH codes as an application. Since the square-root bound is attained when qq is a square, this radius is the largest that can be guaranteed uniformly on the class of GQR codes.

查看此版本解读 →查看此版本原文 ↗