Decoding of Projective Reed-Muller Codes by Dividing a Projective Space into Affine Spaces

Norihiro NAKASHIMA  Hajime MATSUI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.3   pp.733-741
Publication Date: 2016/03/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.733
Type of Manuscript: PAPER
Category: Coding Theory
Keyword: 
error-correcting codes,  affine variety codes,  Gröbner basis,  Berlekamp-Massey-Sakata algorithm,  discrete Fourier transform,  

Full Text: PDF(740.2KB)>>
Buy this Article




Summary: 
A projective Reed-Muller (PRM) code, obtained by modifying a 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 the dual code of a PRM code are known, and some decoding examples have been presented for low-dimensional projective spaces. In this study, we construct a decoding algorithm for all PRM codes by dividing a projective space into a union of affine spaces. In addition, we determine the computational complexity and the number of correctable errors of our algorithm. Finally, we compare the codeword error rate of our algorithm with that of the minimum distance decoding.