Improved partial permutation decoding for Reed–Muller codes

It is shown that for n≥5 and r≤n−12, if an (n,M,2r+1) binary code exists, then the rth-order Reed–Muller code R(r,n) has s-PD-sets of the minimum size s+1 for 1≤s≤M−1, and these PD-sets correspond to sets of translations of the vector space F₂ ⁿ. In addition, for the first order Reed–Muller code R(1,n), s-PD-sets of size s+1 are constructed for s up to the bound ⌊2nn+1⌋−1. The results apply also to generalized Reed–Muller codes.