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\ff_2[x_1,\ldots,x_m,y]$, a polynomial vanishing when evaluated at points in $\ff^m_2$ 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^{-\lambda}$ 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\begin{equation}\label{eq_cond}\tau\leq\max_{0\leq\rho\leq m}\,\min\left\{2^m-\sum_{i=0}^{r+\rho} \binom{m}{i}-\lambda,\sum_{i=0}^\rho\binom{m}{i}-1\right\}\end{equ ation}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 correctup to half the block length asymptotically for fixed $r$.