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.
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.
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.
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. In this work we give an efficient algorithm (in the block length n=2m) for decoding random errors in Reed-Muller codes far beyond the minimal 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/logm)), we can correct roughly mr/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.
This paper considers the performance of long Reed-Muller (RM) codes transmitted over binary memoryless symmetric (BMS) channels under bitwise maximum-a-posteriori decoding. Its main result is that the family of binary RM codes achieves capacity on any BMS channel with respect to bit-error rate. This resolves a long-standing open problem that connects information theory and error-correcting codes. In contrast with the earlier result for the binary erasure channel, the new proof does not rely on hypercontractivity. Instead, it combines a nesting property of RM codes with new information inequalities relating the generalized extrinsic information transfer function and the extrinsic minimum mean-squared error.
This paper considers the performance of Reed–Muller (RM) codes transmitted over binary memoryless symmetric (BMS) channels under bitwise maximum-a-posteriori (bit-MAP) decoding. Its main result is that, for a fixed BMS channel, the family of binary RM codes can achieve a vanishing bit-error probability at rates approaching the channel capacity. This partially resolves a long-standing open problem that connects information theory and error-correcting codes. In contrast with the earlier result for the binary erasure channel, the new proof does not rely on hypercontractivity. Instead, it combines a nesting property of RM codes with new information inequalities relating the generalized extrinsic information transfer function and the extrinsic minimum mean-squared error.
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(logN)bits can be decoded with high probability when the code rate is less than the Holevo capacity.
In this paper, we consider the problem of decoding Reed-Muller (RM) codes in binary erasure channel. We propose a novel algorithm, which exploits several techniques, such as list recursive (successive cancellation) decoding based on Plotkin decomposition, permutations of encoding factor graph as well as the properties of erasure channels.We show that with properly selected number of random permutations, this algorithm considerably outperforms straightforward list decoding while maintaining the same asymptotic complexity. This also means that near-MAP decoding can be achieved with lower complexity cost.