Spherically Punctured Reed-Muller Codes
Ilya I. Dumer, Olga Kapralova · IEEE Transactions on Information Theory · 2017
Consider a binary Reed-Muller code RM(r, m) defined on the m-dimensional hypercube F2m. In this paper, we study punctured Reed-Muller codes Pr(m, b), whose positions are restricted to the m-tuples of a given Hamming weight b. In combinatorial terms, this paper concerns m-variate Boolean polynomials of any degree r, which are evaluated on a Hamming sphere of some radius b in F2m. Codes Pr(m, b) inherit some recursive properties of RM codes. In particular, they can be built from the shorter codes, by decomposing a spherical b-layer into sub-layers of smaller dimensions. However, these sub-layers have different sizes and do not form the classical Plotkin construction. We analyze recursive properties of the spherically punctured codes Pr(m, b) and find their distances for the arbitrary values of parameters r, m, and b. Finally, we describe recursive (successive cancellation) decoding of these codes.