Decoding Reed-Muller Codes beyond Half the Minimum Distance

Inspired by Sudan’s recent algorithm for Reed-Solomon codes we propose an efficient method for decoding r-th order Reed-Muller codes of length 2 m which can correct errors beyond half the minimum distance. This procedure involves interpolating $$ Q \in \mathbb{F}{_{2}}[{x_{1}},...,{x_{m}},y] $$ , a polynomial vanishing when evaluated at points in $$ \mathbb{F}_{2}^{m} $$ joint with the corresponding received bits. To obtain a list of codewords closest to the received word we need to factor Q considered as an element of the quotient ring of boolean polynomials which is not a unique factorization domain. Therefore we introduce a novel, yet simple polynomial-time factorization algorithm for multivariate boolean polynomials that produces generators for the coset of factors. Let p = 2−λ be the probability of algorithm failure and assume that the weights of a Reed-Muller code are approximately binomially distributed. This assumption is supported by known weight distributions for some short Reed-Muller codes. Then with probability at least 1 − p, the algorithm corrects $$ \tau \leqslant \mathop{{\max }}\limits_{{0 \leqslant \rho \leqslant m}} {\text{ min}}\left\{ {{2^{m}} - \sum\limits_{{i = 0}}^{{r + \rho }} {\left( {\begin{array}{*{20}{c}} m \\ i \\ \end{array} } \right) - \lambda ,\sum\limits_{{i = 0}}^{\rho } {\left( {\begin{array}{*{20}{c}} m \\ i \\ \end{array} } \right) - 1} } } \right\}{\text{ }} "$$ independently and uniformly distributed errors. For the RM(2, 9) code for example, the algorithm corrects up to 122 errors with probability at least 0.99 whereas half the minimum distance is 64. Under the above assumption, we can correct up to half the block length asymptotically for fixed r.