← 研踪 PaperTrailarXiv: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
摘要
Binary quadratic residue (QR) codes, introduced by Prange in 1958, are cyclic codes of prime length and dimension whose minimum distance satisfies the square-root bound . They include the Hamming code and the Golay code , and were generalized by van Lint and MacWilliams to generalized quadratic residue (GQR) codes of prime-power length , for which the bound still holds and is attained when 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 , corrects every error pattern of weight at most in the binary GQR code of length , in 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 is a square, this radius is the largest that can be guaranteed uniformly on the class of GQR codes.
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 and dimension whose minimum distance satisfies the square-root bound . They include the Hamming code and the Golay code , and were generalized by van Lint and MacWilliams to generalized quadratic residue (GQR) codes of prime-power length , for which the bound still holds and is attained when 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 , corrects every error pattern of weight at most in the binary GQR code of length , in 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 is a square, this radius is the largest that can be guaranteed uniformly on the class of GQR codes.
查看此版本解读 →查看此版本原文 ↗