Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

Correctable Errors of Weight Half the Minimum Distance for the First-Order Reed-Muller Codes

Kenji Yasunaga, Toru Fujiwara

Published Nov 28, 2006• 1 citation
OpenAlex

Related papers

On the Number of Errors Which Can Be Corrected by the Reed-Muller Code

R.E. Krichevskii

Soviet physics. Doklady•Sep 1, 1970•3 citations

Recursive error correction for general Reed–Muller codes

Ilya I. Dumer, Kirill Shabunov

Discrete Applied Mathematics•Sep 20, 2005•17 citations

Soft-Input Soft-Output Decoding Algorithm Based on Iterative Minimum Distance Search for Reed-Muller Codes

Jun Asatani, Takuya Koumoto, Toru Fujiwara +1 more

IEEE International Symposium on Information Theory (ISIT)•Dec 15, 2003•0 citations

Minimum Distance Decoding for Reed-Muller Codes using Projection-Aggregation

Bin Zhang, Qin Huang

This paper shows that projection-aggregation (PA) decoding of Reed-Muller (RM) codes can decode up to half the minimum distance d efficiently. By generalizing the false vote matrix from 1-dimensional to higher-dimensional subspaces, we prove that projecting onto disjoint subspaces, regardless of their dimensions, provides at most d/2 − 1 false votes for each codeword bit. Thus, d disjoint subspaces guarantee the correction for errors of d/2 − 1 or less. Moreover, the flexibility in subspace dimensions allows projecting into repetition codes directly, resulting in decoding efficiency. Finally, we prove that PA decoding with d disjoint subspaces decodes up to half the minimum distance in $O(n\sqrt n )$ for RM codes of length n and half rate or less.

IEEE Information Theory Workshop (ITW)•Sep 29, 2025•0 citations

Efficiently decoding Reed-Muller codes from random errors

Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Reed-Muller codes encode an m-variate polynomial of degree r by evaluating it on all points in {0,1}m. We denote this code by RM(m,r). The minimal distance of RM(m,r) is 2m−r and so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result.

ACM Symposium on Theory of Computing (STOC)•Jun 10, 2016•7 citations

A Note on Bounded-Weight Error-Correcting Codes

Gabriel Istrate, Lane A. Hemaspaandra, Michael Schear +1 more

•Jan 1, 1999•0 citations
This paper shows that projection-aggregation (PA) decoding of Reed-Muller (RM) codes can decode up to half the minimum distance d efficiently. By generalizing the false vote matrix from 1-dimensional to higher-dimensional subspaces, we prove that projecting onto disjoint subspaces, regardless of their dimensions, provides at most d/2 − 1 false votes for each codeword bit. Thus, d disjoint subspaces guarantee the correction for errors of d/2 − 1 or less. Moreover, the flexibility in subspace dimensions allows projecting into repetition codes directly, resulting in decoding efficiency. Finally, we prove that PA decoding with d disjoint subspaces decodes up to half the minimum distance in O(nn)O(n\sqrt n )O(nn​) for RM codes of length n and half rate or less.