Efficient Encoding/Decoding Algorithms for Irreducible Polynomial Remainder Codes via Additive FFT

Polynomial remainder codes form a class of linear codes constructed based on the Chinese Remainder Theorem over polynomial rings, with Reed-Solomon codes as a special case. In particular, irreducible polynomial remainder codes are those where the moduli are pairwise coprime irreducible polynomials. This paper presents an efficient encoding and decoding method for irreducible polynomial remainder codes over F2m, leveraging the additive Fast Fourier Transform (additive FFT). The proposed approach achieves a computational complexity ofO(Nlog2(N−K)), whereNandKdenote the code length and dimension, with the additional requirement thatN−Km−1andN−Kis a power of 2. This substantially outperforms the best known algorithm for such codes, which has a complexity ofO(N2). Furthermore, we conduct a non-asymptotic complexity comparison under specific parameters, with numerical results demonstrating that the proposed algorithms effectively reduces computational complexity. For example, with code lengthN= 256 and dimensionK= 224, our method achieves an approximately 83% reduction in multiplicative complexity for encoding and a 50% reduction for decoding compared to the state-of-the-art approach for polynomial remainder codes.