Decoding of Reed?Muller Codes with a Large Number of Errors

New $O(n^{r-1}N^2)$, $r\geq 2$, soft-decoding algorithms are constructed for $RM_r$ codes of order $r$ and length $N=2^n$. Although the complexity of these algorithms is somewhat higher than that of known algorithms, they almost always correct a corrupted codeword for $r=\mathrm{const}$, $n\to\infty$ when the number of errors $(1-\varepsilon)N/2$, is much greater than half the code distance. Bounds on the number of almost always corrected errors are obtained for the proposed algorithm and the minimum-distance correlation decoding algorithm. In particular, it is shown that for $r=2$ and $n\to\infty$ the proposed decoding algorithm corrects almost all errors of multiplicity $t\leq(N-Cn^{1/4}N^{3/4})/2$, $C>\ln 4$. Experimental results on decoding of $RM_r$ codes for $r=2,3$ and $N\leq 2^{10}$ indicate that the proposed algorithms are effective for a much greater number of errors than the standard majority algorithms for these codes.