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

arXiv:1411.3545 · Contemporary mathematics - American Mathematical Society

Error-correction capability of Reed-Muller codes

Stéphanie Dib, François Rodier

Published Jan 1, 2017• 0 citations
arXivHTMLPDF

Abstract

We present an asymptotic limit between correctable and uncorrectable errors on the Reed-Muller codes of any order and give its value. This limit is theoretical and does not depend on any decoding algorithm.
DOI
10.1090/conm/686/13775

Related papers

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

Kenji Yasunaga, Toru Fujiwara

IEEE International Symposium on Information Theory (ISIT)•Nov 28, 2006•1 citation

Recursive error correction for general Reed–Muller codes

Ilya I. Dumer, Kirill Shabunov

Discrete Applied Mathematics•Sep 20, 2005•17 citations

Quantum Reed-Muller codes

Andrew M. Steane

A set of quantum error-correcting codes based on classical Reed-Muller codes is described. The codes have parameters [[n,k,d]]=[[2/sup r/,s/sup r/-C(r,t)-2/spl Sigma//sub i=0//sup t-1/C(r,i),2/sup t/+2/sup t-1/]].

arXiv:quant-ph/9608026•IEEE Transactions on Information Theory•Jul 1, 1999•175 citations

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

Optimum 1-Step Majority-Logic Decoding of Binary Reed–Muller Codes

Hoang Ly, Emina Soljanin

The classical majority-logic decoder proposed by Reed for Reed-Muller codes RM(r, m) of order r and length 2^m, unfolds in r+1 sequential steps, decoding message symbols from highest to lowest degree. Several follow-up decoding algorithms reduced the number of steps, but for a limited set of parameters, or at the expense of reduced performance, or relying on the existence of some combinatorial structures. We show that any one-step majority-logic decoder-that is, a decoder performing all majority votes in one step simultaneously without sequential processing-can correct at most d_min/4 errors for all values of r and m, where d_min denotes the code's minimum distance. We then introduce a new hard-decision decoder that completes the decoding in a single step and attains this error-correction limit. It applies to all r and m, and can be viewed as a parallel realization of Reed's original algorithm, decoding all message symbols simultaneously. Remarkably, we also prove that the decoder is optimum in the erasure setting: it recovers the message from any erasure pattern of up to d_min-1 symbols-the theoretical limit. To our knowledge, this is the first 1-step decoder for RM codes that achieves both optimal erasure correction and the maximum one-step error correction capability.

arXiv:2508.08736•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•5 citations

Quantum Reed-Muller Codes

Zhang, Lin, Ian Fuss

This paper presents a set of quantum Reed-Muller codes which are typically 100 times more effective than existing quantum Reed-Muller codes.

arXiv:quant-ph/9703045•Mar 24, 1997•10 citations
The classical majority-logic decoder proposed by Reed for Reed-Muller codes RM(r, m) of order r and length 2^m, unfolds in r+1 sequential steps, decoding message symbols from highest to lowest degree. Several follow-up decoding algorithms reduced the number of steps, but for a limited set of parameters, or at the expense of reduced performance, or relying on the existence of some combinatorial structures. We show that any one-step majority-logic decoder-that is, a decoder performing all majority votes in one step simultaneously without sequential processing-can correct at most d_min/4 errors for all values of r and m, where d_min denotes the code's minimum distance. We then introduce a new hard-decision decoder that completes the decoding in a single step and attains this error-correction limit. It applies to all r and m, and can be viewed as a parallel realization of Reed's original algorithm, decoding all message symbols simultaneously. Remarkably, we also prove that the decoder is optimum in the erasure setting: it recovers the message from any erasure pattern of up to d_min-1 symbols-the theoretical limit. To our knowledge, this is the first 1-step decoder for RM codes that achieves both optimal erasure correction and the maximum one-step error correction capability.