On the weight structure of Reed-Muller codes
Tadao Kasami, N. Tokura · IEEE Transactions on Information Theory · 1970
The following theorem is proved. Letf(x_1,\cdots, x_m)be a binary nonzero polynomial ofmvariables of degree u. H the number of binarym-tuples(a_1,\cdots, a_m)withf(a_1, \cdots, a_m)= 1 is less than2^{m- u+1}, thenfcan be reduced by an invertible affme transformation of its variables to one of the following forms. \begin{equation} f = y_1 \cdots y_{ u - \mu} (y_{ u-\mu+1} \cdots y_{ u} + y_{ u+1} \cdots y_{ u+\mu}), \end{equation} wherem \geq u+\muand u \geq \mu \geq 3. \begin{equation} f = y_1 \cdots y_{ u-2}(y_{ u-1} y_{ u} + y_{ u+1} y_{ u+2} + \cdots + y_{ u+2\mu -3} y_{ u+2\mu-2}), \end{equation} This theorem completely characterizes the codewords of the uth-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.