AI & ML
A polynomial-time decoding algorithm up to half the square-root bound for quadratic residue and generalized quadratic residue codes
arXiv math.IT0 views
arXiv:2611.21888v1 Announce Type: new Abstract: Binary quadratic residue (QR) codes, introduced by Prange in 1958, are cyclic codes of prime length $p\equiv\pm1\pmod 8$ and dimension $(p+1)/2$ whose minimum distance satisfies the square-root bound $d\ge\sqrt p$. They include the Hamming code $[7,4,3]$ and the Golay code $[23,12,7]$, and were generalized by van Lint and MacWilliams to generalized quadratic residue (GQR) codes of prime-power length $q$, for which the bound $d\ge\sqrt q$ still holds and is attained when $q$ 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\equiv\pm1\pmod 8$, corrects every error pattern of weight at most $\lfloor(\sqrt q-1)/2\rfloor$ in the binary GQR code of length $q$, in $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 $q$ is a square, this radius is the largest that can be guaranteed uniformly on the class of GQR codes.
Source:https://arxiv.org/abs/2611.21888PreviousEE-Motion: An EEG-based Web Architecture for Live Affective Music RecommendationNextAn upper bound on non-overlapping codes
Related posts
BenchAudit – Auditing LLM benchmarks for leaks, data reuse, and harness gaps
0Hacker News New
Guillotine DJ – Announcement Trailer
0Hacker News New
Researchers hijack Hugging Face account for popular Kokoro AI model
0Hacker News New
Automated LLM Fine-Tuning: GPU Selection, Dataset Analysis and Feedback
0Hacker News New
Human-written Launch HN posts get more upvotes than AI-generated ones
0Hacker News New

Parallels Desktop review
0TechRadar