Abstract
Based on a recently proposed fast Fourier transform by Lin, Chung, and Han, this paper presents two fast erasure decoding algorithms for Reed–Solomon (RS) codes over binary extension fields of length $N$ and dimension $K$ . The first algorithm applies to low-rate RS codes (i.e., $\frac {K}{N} \leq 0.5$ ) and achieves a complexity of $O(N \log K)$ . The second algorithm applies to high-rate RS codes (i.e., $\frac {K}{N} \geq 0.5$ ) and achieves a complexity of $O(N \log (N-K))$ . Compared to recent state-of-the-art algorithms, both proposed algorithms achieve the best complexity, resulting in significant throughput improvements in Single Instruction Multiple Data (SIMD) based simulations. Besides yielding new fast algorithms for RS codes, this paper also presents a new interpolation formula, as well as related results, which may be of independent interest.
Funding Information
  • Yunnan Key Research and Development Program (2021YFA1000500)

This publication has 36 references indexed in Scilit: