On Codes Decoding a Constant Fraction of Errors on the BSC
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, Sasoglu and Urbanke from STOC 2016, we prove that a Reed-Muller code of positive rate R decodes errors on the BSC (p) with high probability if p < 1/2 - root 2(-R)(1 - 2(-R)).
WOS:000810492500126
2021-01-01
New York
978-1-4503-8053-9
Annual ACM Symposium on Theory of Computing
1479
1488
REVIEWED
EPFL
Event name | Event place | Event date |
ELECTR NETWORK | Jun 21-25, 2021 | |