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:2202.00240

A Criterion for Decoding on the BSC

Anup Rao, Oscar Sprumont

Published Feb 1, 2022• 2 citations
arXivHTMLPDF

Abstract

We present an approach to showing that a linear code is resilient to random errors. We use this approach to obtain decoding results for both transitive codes and Reed-Muller codes. We give three kinds of results about linear codes in general, and transitive linear codes in particular. 1) We give a tight bound on the weight distribution of every transitive linear code $C \subseteq \mathbb{F}_2^N$: $\Pr_{c \in C}[|c| = αN] \leq 2^{-(1-h(α)) \mathsf{dim}(C)}$. 2) We give a criterion that certifies that a linear code $C$ can be decoded on the binary symmetric channel. Let $K_s(x)$ denote the Krawtchouk polynomial of degree $s$, and let $C^\perp$ denote the dual code of $C$. We show that bounds on $\mathbb{E}_{c \in C^{\perp}}[ K_{εN}(|c|)^2]$ imply that $C$ recovers from errors on the binary symmetric channel with parameter $ε$. Weaker bounds can be used to obtain list-decoding results using similar methods. One consequence of our criterion is that whenever the weight distribution of $C^\perp$ is sufficiently close to the binomial distribution in some interval around $\frac{N}{2}$, $C$ is resilient to $ε$-errors. 3) We combine known estimates for the Krawtchouk polynomials with our weight bound for transitive codes, and with known weight bounds for Reed-Muller codes, to obtain list-decoding results for both these families of codes. In some regimes, our bounds for Reed-Muller codes achieve the information-theoretic optimal trade-off between rate and list size.

DOI
10.48550/arxiv.2202.00240

Related papers

A criterion for decoding on the binary symmetric channel

Anup Rao, Oscar Sprumont

We present an approach to showing that a linear code is resilient to random errors. We use this approach to obtain decoding results for both transitive and doubly transitive codes. We give three kinds of results about linear codes in general, and transitive linear codes in particular.1. We give a tight bound on the weight distribution of every transitive linear code $ C \subseteq \mathbb{F}_2^N $:$ \mathop {\Pr }\limits_{c \in C}[ \text{wt}(c) = \alpha N] \leq 2^{-(1-h(\alpha)) \mathsf{dim}(C)}. $2. We give a criterion that certifies that a linear code $ C $ can be decoded on the binary symmetric channel. Let $ K_s(x) $ denote the Krawtchouk polynomial of degree $ s $, and let $ C^\perp $ denote the dual code of $ C $. We show that bounds on $ \mathbb{E}_{c \in C^{\perp}}[ K_{\epsilon N}( \text{wt}(c))^2] $ imply that $ C $ recovers from errors on the binary symmetric channel with parameter $ \epsilon $. Weaker bounds can be used to obtain list-decoding results using similar methods. One consequence of our criterion is that whenever the weight distribution of $ C^\perp $ is sufficiently close to the binomial distribution in some interval around $ \frac{N}{2} $, $ C $ is resilient to $ \epsilon $-errors.3. We combine known estimates for the Krawtchouk polynomials with our weight bound for transitive codes, and with known weight bounds for doubly transitive codes, to obtain list-decoding results for both these families of codes. In some regimes, our bounds for doubly transitive codes achieve the information-theoretic optimal trade-off between rate and list size.

Advances in Mathematics of Communications•Feb 28, 2024•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

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

Efficiently decoding Reed-Muller codes from random errors

Ramprasad Saptharishi, Shpilka, Amir, 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 $2^{m-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. In this work we give an efficient algorithm (in the block length $n=2^m$) for decoding random errors in Reed-Muller codes far beyond the minimal distance. Specifically, for low rate codes (of degree $r=o(\sqrt{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(\sqrt{m/\log m})$), we can correct roughly $m^{r/2}$ errors. More generally, for any integer $r$, our algorithm can correct any error pattern in $RM(m,m-(2r+2))$ for which the same erasure pattern can be corrected in $RM(m,m-(r+1))$. The results above are obtained by applying recent results of Abbe, Shpilka and Wigderson (STOC, 2015), Kumar and Pfister (2015) and Kudekar et al. (2015) regarding the ability of Reed-Muller 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 Reed-Muller 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 famous Berlekamp-Welch algorithm for decoding Reed-Solomon codes.

arXiv:1503.09092•Mar 31, 2015•2 citations

Reed-Muller Codes for Random Erasures and Errors

Emmanuel A. Abbe, Amir Shpilka, Avi Wigderson

This paper studies the parameters for which binary Reed-Muller (RM) codes can be decoded successfully on the BEC and BSC, and in particular when can they achieve capacity for these two classical channels. Necessarily, the paper also studies properties of evaluations of multi-variate GF(2) polynomials on random sets of inputs. For erasures, we prove that RM codes achieve capacity both for very high rate and very low rate regimes. For errors, we prove that RM codes achieve capacity for very low rate regimes, and for very high rates, we show that they can uniquely decode at about square root of the number of errors at capacity.

ACM Symposium on Theory of Computing (STOC)•Jun 3, 2015•18 citations

On polylogarithmic decoding complexity for reed-muller codes

Ilya I. Dumer

For Reed-Muller (RM) codes of length n and distance d, a recursive decoding algorithm is designed that has complexity of order nlogn for any fixed rate R, and corrects most error patterns of weight up to (dlnd)/2 on the binary symmetric channels (BSC) and up to (2dlnd)/pi on the AWGN channels. For long RM codes of fixed order r, a vanishing decoding error probability and polylogarithmic decoding complexity of order (logn)r+1are obtained on the BSC given any transition probability p that is bounded away from 1/2

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•1 citation
We present an approach to showing that a linear code is resilient to random errors. We use this approach to obtain decoding results for both transitive codes and Reed-Muller codes. We give three kinds of results about linear codes in general, and transitive linear codes in particular. 1) We give a tight bound on the weight distribution of every transitive linear code C⊆F2NC \subseteq \mathbb{F}_2^NC⊆F2N​: Pr⁡c∈C[∣c∣=αN]≤2−(1−h(α))dim(C)\Pr_{c \in C}[|c| = αN] \leq 2^{-(1-h(α)) \mathsf{dim}(C)}Prc∈C​[∣c∣=αN]≤2−(1−h(α))dim(C). 2) We give a criterion that certifies that a linear code CCC can be decoded on the binary symmetric channel. Let Ks(x)K_s(x)Ks​(x) denote the Krawtchouk polynomial of degree sss, and let C⊥C^\perpC⊥ denote the dual code of CCC. We show that bounds on Ec∈C⊥[KεN(∣c∣)2]\mathbb{E}_{c \in C^{\perp}}[ K_{εN}(|c|)^2]Ec∈C⊥​[KεN​(∣c∣)2] imply that CCC recovers from errors on the binary symmetric channel with parameter εεε. Weaker bounds can be used to obtain list-decoding results using similar methods. One consequence of our criterion is that whenever the weight distribution of C⊥C^\perpC⊥ is sufficiently close to the binomial distribution in some interval around N2\frac{N}{2}2N​, CCC is resilient to εεε-errors. 3) We combine known estimates for the Krawtchouk polynomials with our weight bound for transitive codes, and with known weight bounds for Reed-Muller codes, to obtain list-decoding results for both these families of codes. In some regimes, our bounds for Reed-Muller codes achieve the information-theoretic optimal trade-off between rate and list size.
We present an approach to showing that a linear code is resilient to random errors. We use this approach to obtain decoding results for both transitive and doubly transitive codes. We give three kinds of results about linear codes in general, and transitive linear codes in particular.1. We give a tight bound on the weight distribution of every transitive linear code $ C \subseteq \mathbb{F}_2^N ::: \mathop {\Pr }\limits_{c \in C}[ \text{wt}(c) = \alpha N] \leq 2^{-(1-h(\alpha)) \mathsf{dim}(C)}. $2. We give a criterion that certifies that a linear code $ C $ can be decoded on the binary symmetric channel. Let $ K_s(x) $ denote the Krawtchouk polynomial of degree $ s $, and let $ C^\perp $ denote the dual code of $ C $. We show that bounds on $ \mathbb{E}_{c \in C^{\perp}}[ K_{\epsilon N}( \text{wt}(c))^2] $ imply that $ C $ recovers from errors on the binary symmetric channel with parameter $ \epsilon $. Weaker bounds can be used to obtain list-decoding results using similar methods. One consequence of our criterion is that whenever the weight distribution of $ C^\perp $ is sufficiently close to the binomial distribution in some interval around $ \frac{N}{2} $, $ C $ is resilient to $ \epsilon $-errors.3. We combine known estimates for the Krawtchouk polynomials with our weight bound for transitive codes, and with known weight bounds for doubly transitive codes, to obtain list-decoding results for both these families of codes. In some regimes, our bounds for doubly transitive codes achieve the information-theoretic optimal trade-off between rate and list size.
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).
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.
Reed-Muller codes encode an mmm-variate polynomial of degree rrr by evaluating it on all points in {0,1}m\{0,1\}^m{0,1}m. We denote this code by RM(m,r)RM(m,r)RM(m,r). The minimal distance of RM(m,r)RM(m,r)RM(m,r) is 2m−r2^{m-r}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. In this work we give an efficient algorithm (in the block length n=2mn=2^mn=2m) for decoding random errors in Reed-Muller codes far beyond the minimal distance. Specifically, for low rate codes (of degree r=o(m)r=o(\sqrt{m})r=o(m​)) we can correct a random set of (1/2−o(1))n(1/2-o(1))n(1/2−o(1))n errors with high probability. For high rate codes (of degree m−rm-rm−r for r=o(m/log⁡m)r=o(\sqrt{m/\log m})r=o(m/logm​)), we can correct roughly mr/2m^{r/2}mr/2 errors. More generally, for any integer rrr, our algorithm can correct any error pattern in RM(m,m−(2r+2))RM(m,m-(2r+2))RM(m,m−(2r+2)) for which the same erasure pattern can be corrected in RM(m,m−(r+1))RM(m,m-(r+1))RM(m,m−(r+1)). The results above are obtained by applying recent results of Abbe, Shpilka and Wigderson (STOC, 2015), Kumar and Pfister (2015) and Kudekar et al. (2015) regarding the ability of Reed-Muller 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 Reed-Muller 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 famous Berlekamp-Welch algorithm for decoding Reed-Solomon codes.
This paper studies the parameters for which binary Reed-Muller (RM) codes can be decoded successfully on the BEC and BSC, and in particular when can they achieve capacity for these two classical channels. Necessarily, the paper also studies properties of evaluations of multi-variate GF(2) polynomials on random sets of inputs. For erasures, we prove that RM codes achieve capacity both for very high rate and very low rate regimes. For errors, we prove that RM codes achieve capacity for very low rate regimes, and for very high rates, we show that they can uniquely decode at about square root of the number of errors at capacity.
For Reed-Muller (RM) codes of length n and distance d, a recursive decoding algorithm is designed that has complexity of order nlogn for any fixed rate R, and corrects most error patterns of weight up to (dlnd)/2 on the binary symmetric channels (BSC) and up to (2dlnd)/pi on the AWGN channels. For long RM codes of fixed order r, a vanishing decoding error probability and polylogarithmic decoding complexity of order (logn)r+1are obtained on the BSC given any transition probability p that is bounded away from 1/2