Efficiently decoding Reed-Muller codes from random errors

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 (√ 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 m r /2 errors. More generally, for any integer r , our algorithm can correct any error pattern in RM ( m , m −(2 r +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.

Authors

• Ramprasad Saptharishi
• Amir Shpilka
• Ben Lee Volk

Keywords

• Error Correcting Codes
• Random Errors
• Reed-Muller