Efficiently decoding Reed-Muller codes from random errors

DOI10.1145/2897518.2897526MaRDI QIDQ5361832zbMATH OpenOpenAlexFDO

Authors Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.09092

zbMATH Keywords

error correcting codesrandom errorsReed-Muller codes

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Decoding (94B35)

Abstract: 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(sqrtm)$) 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(sqrtm/logm)$), 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.

Recommendations

• scientific article; zbMATH DE number 1594297
• List Decoding of<tex>$q$</tex>-ary Reed–Muller Codes
• Reed-Muller codes for random erasures and errors
• Decoding of Reed-Muller codes with a large number of errors
• On the performance of Reed-Muller codes with respect to random errors and erasures

Cited in

(14)

• Reinforcement learning for optimal error correction of toric codes
• Decoding of Reed-Muller codes with a large number of errors
• Recursive error correction for general Reed--Muller codes
• Extractors from Reed-Muller codes
• scientific article; zbMATH DE number 1594297 (Why is no real title available?)
• Reed-Muller codes for random erasures and errors
• Reed–Muller Codes for Random Erasures and Errors
• Recursive Decoding and Its Performance for Low-Rate Reed–Muller Codes
• Using Reed–Muller ${\hbox{RM}}\,(1, m)$ Codes Over Channels With Synchronization and Substitution Errors
• Decoding Reed-Muller codes over product sets
• Syndrome decoding of Reed-Muller codes and tensor decomposition over finite fields
• On the performance of Reed-Muller codes with respect to random errors and erasures
• Decoding Reed-Muller codes over product sets
• Decoding variants of Reed-Muller codes over finite grids

This page was built for publication: Efficiently decoding Reed-Muller codes from random errors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361832)