Identifying codewords in general Reed-Muller codes and determining their weights

Abstract

Determining the weight distribution of all Reed-Muller codes is a huge and exciting problem that has been around since the sixties. Some progress has been made very recently, but we are still far from a solution. In this paper, we addressed the subproblem of determining as many codeword weights as possible in Reed-Muller codes of any lengths and any orders, which is decisive for determining their weight spectra (i.e., the lists of all possible weights in these codes). New approaches seem necessary for both the main problem and the subproblem. We first studied the difficulties and the limits of the approach, which consisted of using the usual primary and secondary constructions of Boolean functions for the purpose of determining as many weights as possible in Reed-Muller codes. We then introduced a way, different from the usual constructions, to generate Boolean functions in $ n $ variables having an algebraic degree bounded from above, without any restriction on $ n $, and whose Hamming weights can be determined. This provided weights in Reed-Muller codes of any lengths $ 2^n $ and any orders, allowing us to reach potentially new values in the weight spectra of Reed-Muller codes (as we illustrate with all Reed-Muller codes of lengths up to $ 2^{21} $), with the related codewords being given with their supports and their algebraic normal forms being mathematically derived.

Keywords

• reed-muller codes
• weight spectrum