Fast Decoding of Projective Reed-Muller Codes by Dividing a Projective Space into Affine Spaces.
Norihiro Nakashima, Hajime Matsui · arXiv (Cornell University) · 2014
A projective Reed-Muller (PRM) code, obtained by modifying a (classical) Reed-Muller code with respect to a projective space, is a doubly extended Reed-Solomon code when the dimension of the related projective space is equal to 1. The minimum distance and dual code of a PRM code are known, and some decoding examples have been represented for the case of a low-dimensional projective space. In this study, we construct an efficient decoding algorithm for all PRM codes. For this purpose, we divide a projective space into a union of affine spaces. In addition, we evaluate the computational complexity and number of correctable errors of our algorithm. Finally, we compare the codeword error rate of our algorithm with that of minimum distance decoding.