TY - RPRT

T1 - Decoding Reed-Muller Codes beyond Half the Minimum Distance

AU - Heydtmann, Agnes Eileen

AU - Jakobsen, Thomas

PY - 1999

Y1 - 1999

N2 - 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$.

AB - 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$.

M3 - Report

BT - Decoding Reed-Muller Codes beyond Half the Minimum Distance

ER -