مرکز منطقه ای اطلاع رساني علوم و فناوري - On the weight structure of Reed-Muller codes

Abstract :

The following theorem is proved. Let $f(x_1,\\cdots , x_m)$ be a binary nonzero polynomial of $m$ variables of degree $\\nu$ . H the number of binary $m$ -tuples $(a_1,\\cdots , a_m)$ with $f(a_1, \\cdots , a_m)$ = 1 is less than $2^{m-\\nu+1}$ , then $f$ can be reduced by an invertible affme transformation of its variables to one of the following forms. begin{equation} f = y_1 cdots y_{nu - mu} (y_{nu-mu+1} cdots y_{nu} + y_{nu+1} cdots y_{nu+mu}), end{equation} where $m \\geq \\nu+\\mu$ and $\\nu \\geq \\mu \\geq 3$ . begin{equation} f = y_1 cdots y_{nu-2}(y_{nu-1} y_{nu} + y_{nu+1} y_{nu+2} + cdots + y_{nu+2mu -3} y_{nu+2mu-2}), end{equation} This theorem completely characterizes the codewords of the $\\nu$ th-order Reed-Muller code whose weights are less than twice the minimum weight and leads to the weight enumerators for those codewords. These weight formulas are extensions of Berlekamp and Sloane\´s results.