A recursive algorithm for decoding some subsets of first-order Reed–Muller codes

A. S. Logachev

Diskretnaya Matematika, Tome 4 (1992) no. 2, pp. 130-135

Résumé

We give a recursive algorithm for decoding a binary code that is determined as the subset of words of a first-order Reed–Muller code given by linear Boolean functions in $n$ variables of fixed weight $r$ (the number of real variables). We show that the complexity of decoding these subsets of coded words can be estimated by the number $(r+1)\cdot2^n$ of operations of the type of the addition of two numbers, which improves the estimate $(2r+1)\cdot2^n$ already known. This algorithm for the case of decoding the subsets of even [odd] weight $r$ has complexity $n\cdot 2^{n-1}$.