Efficient Interpolation-Based Decoding of Reed-Solomon Codes
Wrya K. Kadir, Hsuan-Yin Lin, Eirik Rosnes · 2023
We propose a new interpolation-based error decoding algorithm for (n,k) Reed-Solomon (RS) codes over a finite field of size q, where n = q − 1 is the length and k is the dimension. In particular, we employ the fast Fourier transform (FFT) together with properties of a circulant matrix associated with the error interpolation polynomial and some known results from elimination theory in the decoding process. The asymptotic computational complexity of the proposed algorithm for correcting any $t \leq \left\lfloor {\frac{{n - k}}{2}} \right\rfloor$ errors in an (n,k) RS code is of order ${\mathcal{O}}\left( {t{{\log }^2}t} \right)$ and ${\mathcal{O}}\left( {n{{\log }^2}n\log \log n} \right)$ over FFT-friendly and arbitrary finite fields, respectively, achieving the best currently known asymptotic decoding complexity, proposed for the same set of parameters.