Efficient Interpolation-Based Decoding of Reed-Solomon Codes
share
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 ≤⌊n-k/2⌋ errors in an (n,k) RS code is of order 𝒪(tlog^2 t) and 𝒪(nlog^2 n loglog n) over FFT-friendly and arbitrary finite fields, respectively, achieving the best currently known asymptotic decoding complexity, proposed for the same set of parameters.
READ FULL TEXT