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:2501.05748 · IEEE International Symposium on Information Theory (ISIT)

From Bit to Block: Decoding on Erasure Channels

Henry D. Pfister, Oscar Sprumont, Gilles Zémor

Published Jun 22, 2025• 5 citations
arXivHTMLPDF

Abstract

We provide a general framework for bounding the block error threshold of a linear code$C \subseteq \mathbb{F}_{2}^{N}$over the erasure channel in terms of its bit error threshold. Our approach relies on understanding the minimum support weight of any$r$-dimensional subcode of$C$, for all small values of$r$. As a proof of concept, we use our machinery to obtain a new proof of the celebrated result that Reed-Muller codes achieve capacity on the erasure channel with respect to block error probability.

DOI
10.1109/isit63088.2025.11195698

Related papers

Comparing the bit-MAP and block-MAP decoding thresholds of reed-muller codes on BMS channels

Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli +2 more

The question whether RM codes are capacity-achieving is a long-standing open problem in coding theory that was recently answered in the affirmative for transmission over erasure channels [1], [2]. Remarkably, the proof does not rely on specific properties of RM codes, apart from their symmetry. Indeed, the main technical result consists in showing that any sequence of linear codes, with doubly-transitive permutation groups, achieves capacity on the memoryless erasure channel under bit-MAP decoding. Thus, a natural question is what happens under block-MAP decoding. In [1], [2], by exploiting further symmetries of the code, the bit-MAP threshold was shown to be sharp enough so that the block erasure probability also converges to 0. However, this technique relies heavily on the fact that the transmission is over an erasure channel. We present an alternative approach to strengthen results regarding the bit-MAP threshold to block-MAP thresholds. This approach is based on a careful analysis of the weight distribution of RM codes. In particular, the flavor of the main result is the following: assume that the bit-MAP error probability decays as N−δ, for some δ > 0. Then, the block-MAP error probability also converges to 0. This technique applies to transmission over any binary memoryless symmetric channel. Thus, it can be thought of as a first step in extending the proof that RM codes are capacity-achieving to the general case.

arXiv:1601.06048•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•28 citations

An Efficient Block Error Probability Estimation of Reed-Muller Codes under Permutation Decoding

Mikhail Kamenev

A method for estimating the block error probability of Reed-Muller codes on a binary erasure channel and a binary symmetric channel under a permutation decoding algorithm is proposed. This method is based on an analysis of the block error probability under a recursive decoding algorithm for a fixed number of input erasures or errors. Simulation results demonstrate that the proposed method allows to effectively predict the block error rate performance of Reed-Muller codes under permutation decoding with a different number of permutations used.

IEEE Information Theory Workshop (ITW)•Apr 11, 2021•0 citations

Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels

Or Ordentlich, Yury Polyanskiy

Consider a binary linear code of length N, minimum distance d-{\min}, transmission over the binary erasure channel with parameter 0 < \epsilon < 1 or the binary symmetric channel with parameter 0 < \epsilon < \frac{1}{2}, and block-MAP decoding. It was shown by Tillich and Zemor that in this case the error probability of the block-MAP decoder transitions 'quickly' from \delta to 1-\delta for any \delta > 0 if the minimum distance is large. In particular the width of the transition is of order O(1/\sqrt{d-{\min}}). We strengthen this result by showing that under suitable conditions on the weight distribution of the code, the transition width can be as small as \Theta(1/N^{\frac{1}{2}-\kappa}), for any \kappa > 0, even if the minimum distance of the code is not linear. This condition applies e.g., to Reed-Mueller codes. Since \Theta(1/N^{\frac{1}{2}}) is the smallest transition possible for any code, we speak of 'almost' optimal scaling. We emphasize that the width of the transition says nothing about the location of the transition. Therefore this result has no bearing on whether a code is capacity-achieving or not. As a second contribution, we present a new estimate on the derivative of the EXIT function, the proof of which is based on the Blowing-Up Lemma.

•Jun 1, 2018•16 citations

Reed–Muller Codes on CQ Channels via a New Correlation Bound for Quantum Observables

Avijit Mandal, Henry D. Pfister

The question of whether Reed-Muller (RM) codes achieve capacity on binary memoryless symmetric (BMS) channels has drawn attention since it was resolved positively for the binary erasure channel by Kudekar et al. in 2016. In 2021, Reeves and Pfister extended this to prove the bit-error probability vanishes on BMS channels when the code rate is less than capacity. In 2023, Abbe and Sandon improved this to show the block-error probability also goes to zero. These results analyze decoding functions using symmetry and the nested structure of RM codes. In this work, we focus on binary-input symmetric classicalquantum (BSCQ) channels and the Holevo capacity. For a BSCQ, we consider observables that estimate the channel input in the sense of minimizing the mean-squared error (MSE). Using the orthogonal decomposition of these observables under a weighted inner product, we establish a recursive relation for the minimum MSE estimate of a single bit in the RM code. Our results show that any set of$2^{o(\sqrt{\log N})}$bits can be decoded with high probability when the code rate is less than the Holevo capacity.

arXiv:2502.03785•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•2 citations

On codes decoding a constant fraction of errors on the BSC

Jan Hązła, Alex Samorodnitsky, Ori Sberlo

We strengthen the results from a recent work by the second author, achieving bounds on the weight distribution of binary linear codes that are successful under block-MAP (as well as bit-MAP) decoding on the BEC. We conclude that a linear code that is successful on the BEC can also decode over a range of binary memoryless symmetric (BMS) channels. In particular, applying the result of Kudekar, Kumar, Mondelli, Pfister, Şaşoğlu and Urbanke from STOC 2016, we prove that a Reed–Muller code of positive rate R decodes errors on the p with high probability if p < 1/2 − √2−R(1−2−R).

ACM Symposium on Theory of Computing (STOC)•Jun 15, 2021•15 citations

Efficiently Decoding Reed–Muller Codes From Random Errors

Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Reed-Muller (RM) codes encode an m-variate polynomial of degree at most r by evaluating it on all points in {0,1}m. We denote this code by RM(r,m). The minimum distance of RM(r,m) is 2m-rand 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. In this paper we give an efficient algorithm (in the block length n=2m) for decoding random errors in RM codes far beyond the minimum distance. Specifically, for low-rate codes (of degree r=o(√m)), we can correct a random set of (1/2-o(1))n errors with high probability. For high rate codes (of degree m-r for r=o(√m/log m)), we can correct roughly mr/2errors. More generally, for any integer r, our algorithm can correct any error pattern in RM(m-(2r+2),m), for which the same erasure pattern can be corrected in RM(m-(r+1),m). The results above are obtained by applying recent results of Abbe, Shpilka, and Wigderson (STOC, 2015) and Kudekar et al. (STOC, 2016) regarding the ability of RM codes to correct random erasures. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding RM codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the error-locating pair method of Pellikaan, Duursma, and Kötter that generalizes the Berlekamp-Welch algorithm for decoding Reed-Solomon codes.

arXiv:1503.09092•IEEE Transactions on Information Theory•Feb 17, 2017•30 citations
We provide a general framework for bounding the block error threshold of a linear codeC⊆F2NC \subseteq \mathbb{F}_{2}^{N}C⊆F2N​over the erasure channel in terms of its bit error threshold. Our approach relies on understanding the minimum support weight of anyrrr-dimensional subcode ofCCC, for all small values ofrrr. As a proof of concept, we use our machinery to obtain a new proof of the celebrated result that Reed-Muller codes achieve capacity on the erasure channel with respect to block error probability.
The question whether RM codes are capacity-achieving is a long-standing open problem in coding theory that was recently answered in the affirmative for transmission over erasure channels [1], [2]. Remarkably, the proof does not rely on specific properties of RM codes, apart from their symmetry. Indeed, the main technical result consists in showing that any sequence of linear codes, with doubly-transitive permutation groups, achieves capacity on the memoryless erasure channel under bit-MAP decoding. Thus, a natural question is what happens under block-MAP decoding. In [1], [2], by exploiting further symmetries of the code, the bit-MAP threshold was shown to be sharp enough so that the block erasure probability also converges to 0. However, this technique relies heavily on the fact that the transmission is over an erasure channel. We present an alternative approach to strengthen results regarding the bit-MAP threshold to block-MAP thresholds. This approach is based on a careful analysis of the weight distribution of RM codes. In particular, the flavor of the main result is the following: assume that the bit-MAP error probability decays as N−δ, for some δ > 0. Then, the block-MAP error probability also converges to 0. This technique applies to transmission over any binary memoryless symmetric channel. Thus, it can be thought of as a first step in extending the proof that RM codes are capacity-achieving to the general case.
A method for estimating the block error probability of Reed-Muller codes on a binary erasure channel and a binary symmetric channel under a permutation decoding algorithm is proposed. This method is based on an analysis of the block error probability under a recursive decoding algorithm for a fixed number of input erasures or errors. Simulation results demonstrate that the proposed method allows to effectively predict the block error rate performance of Reed-Muller codes under permutation decoding with a different number of permutations used.
Consider a binary linear code of length N, minimum distance d-{\min}, transmission over the binary erasure channel with parameter 0 < \epsilon < 1 or the binary symmetric channel with parameter 0 < \epsilon < \frac{1}{2}, and block-MAP decoding. It was shown by Tillich and Zemor that in this case the error probability of the block-MAP decoder transitions 'quickly' from \delta to 1-\delta for any \delta > 0 if the minimum distance is large. In particular the width of the transition is of order O(1/\sqrt{d-{\min}}). We strengthen this result by showing that under suitable conditions on the weight distribution of the code, the transition width can be as small as \Theta(1/N^{\frac{1}{2}-\kappa}), for any \kappa > 0, even if the minimum distance of the code is not linear. This condition applies e.g., to Reed-Mueller codes. Since \Theta(1/N^{\frac{1}{2}}) is the smallest transition possible for any code, we speak of 'almost' optimal scaling. We emphasize that the width of the transition says nothing about the location of the transition. Therefore this result has no bearing on whether a code is capacity-achieving or not. As a second contribution, we present a new estimate on the derivative of the EXIT function, the proof of which is based on the Blowing-Up Lemma.
The question of whether Reed-Muller (RM) codes achieve capacity on binary memoryless symmetric (BMS) channels has drawn attention since it was resolved positively for the binary erasure channel by Kudekar et al. in 2016. In 2021, Reeves and Pfister extended this to prove the bit-error probability vanishes on BMS channels when the code rate is less than capacity. In 2023, Abbe and Sandon improved this to show the block-error probability also goes to zero. These results analyze decoding functions using symmetry and the nested structure of RM codes. In this work, we focus on binary-input symmetric classicalquantum (BSCQ) channels and the Holevo capacity. For a BSCQ, we consider observables that estimate the channel input in the sense of minimizing the mean-squared error (MSE). Using the orthogonal decomposition of these observables under a weighted inner product, we establish a recursive relation for the minimum MSE estimate of a single bit in the RM code. Our results show that any set of2o(log⁡N)2^{o(\sqrt{\log N})}2o(logN​)bits can be decoded with high probability when the code rate is less than the Holevo capacity.
We strengthen the results from a recent work by the second author, achieving bounds on the weight distribution of binary linear codes that are successful under block-MAP (as well as bit-MAP) decoding on the BEC. We conclude that a linear code that is successful on the BEC can also decode over a range of binary memoryless symmetric (BMS) channels. In particular, applying the result of Kudekar, Kumar, Mondelli, Pfister, Şaşoğlu and Urbanke from STOC 2016, we prove that a Reed–Muller code of positive rate R decodes errors on the p with high probability if p < 1/2 − √2−R(1−2−R).
Reed-Muller (RM) codes encode an m-variate polynomial of degree at most r by evaluating it on all points in {0,1}m. We denote this code by RM(r,m). The minimum distance of RM(r,m) is 2m-rand 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. In this paper we give an efficient algorithm (in the block length n=2m) for decoding random errors in RM codes far beyond the minimum distance. Specifically, for low-rate codes (of degree r=o(√m)), we can correct a random set of (1/2-o(1))n errors with high probability. For high rate codes (of degree m-r for r=o(√m/log m)), we can correct roughly mr/2errors. More generally, for any integer r, our algorithm can correct any error pattern in RM(m-(2r+2),m), for which the same erasure pattern can be corrected in RM(m-(r+1),m). The results above are obtained by applying recent results of Abbe, Shpilka, and Wigderson (STOC, 2015) and Kudekar et al. (STOC, 2016) regarding the ability of RM codes to correct random erasures. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding RM codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the error-locating pair method of Pellikaan, Duursma, and Kötter that generalizes the Berlekamp-Welch algorithm for decoding Reed-Solomon codes.