Abstract

In this paper, we present a new interpolation-based error-and-erasure decoding algorithm for \((n,k)\) Reed-Solomon (RS) codes over a finite field of arbitrary size \(q\), where \(n\), being a divisor of \(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 computational complexity of the proposed algorithm for correcting any \(t \leq \lfloor \frac{n-k}{2} \rfloor\) errors in an \((n,k)\) RS code is of order \(\mathcal{O}(n\log^2 n \log\log n)\) over an arbitrary finite field, achieving the best currently known asymptotic decoding complexity, proposed for the same set of parameters. When applying the proposed algorithm to RS codes over finite fields that support a (multiplicative) FFT, we achieve a complexity of order \(\mathcal{O}(n\log n)\), which is strictly better than that of any other decoding algorithm known in the literature. For a special family of twisted RS (TRS) codes with a single twist, the decoding complexity becomes \(\mathcal{O}(n\log^2 n \log\log n)\) which is strictly better than the best currently known decoding complexity \(\mathcal{O}(n^2)\). For decoding of RS codes beyond the unique decoding radius by a single unit, the decoding problem is reduced to the problem of solving a quadratic equation, and the resulting complexity becomes \(\mathcal{O}(n\log^2 n \log\log n)\). Finally, we compare the number of actual decoding operations of the proposed algorithm for two RS codes of length \(256\) and \(1152\) to those of known algorithms from the literature, showing that it outperforms state-of-art algorithms also for finite blocklengths.