Fast Encoding and Decoding Algorithms for Arbitrary $(n,k)$ Reed-Solomon Codes Over $\mathbb{F}_{2^m}$

Recently, a new polynomial basis over finite fields was proposed such that the computational complexity of the fast Fourier transform (FFT) is O(n log n). Based on FFTs, the encoding and decoding algorithms for Reed-Solomon (RS) codes were proposed, which are shown to have the lowest computational complexity in the literature. However, these algorithms require that the code length and the number of parity symbols must be power of two. In this letter, we present the encoding and decoding algorithms for arbitrary RS codes based on FFTs. Furthermore, these new algorithms also reach the best known complexity bound.