On the Weight Distributions of Optimal Cosets
of the First-Order Reed-Muller Codes

Anne Canteaut

BP 105
78153 Le Chesnay Cedex, France

IEEE Transactions on Information Theory, 47(1):407-413, January 2001.


We study the weight distributions of cosets of the first-order Reed-Muller code R(1,m) for odd m, whose minimum weight is greater than or equal to the so-called quadratic bound. Some general restrictions on the weight distribution of a coset of R(1,m) are obtained by partitioning its words according to their weight divisibility. Most notably, we show that there are exactly five weight distributions for optimal cosets of R(1,7) in R(5,7) and that these distributions are related to the degree of the function generating the coset. Moreover, for any odd m >= 9, we exhibit optimal cubic cosets of R(1,m) whose weights take on exactly five values.


Boolean function, covering radius, nonlinearity, Reed-Muller code, weight distribution.