Two Fast Erasure Decoding Algorithms for Reed–Solomon Codes Based on LCH-FFT
- 20 April 2026
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (6) , 3784-3798
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.Keywords
Funding Information
- Yunnan Key Research and Development Program (2021YFA1000500)
This publication has 36 references indexed in Scilit:
- The Discrete Fourier Transform Over the Binary Finite FieldIEEE Access, 2023
- Fast Algorithms for Signal Processing2010
- FNT-Based Reed-Solomon Erasure Codes2010
- FFT-based fast Reed–Solomon codes with arbitrary block lengths and ratesIEE Proceedings - Communications, 2005
- A Method for Fast Computation of the Fourier Transform over a Finite FieldProblems of Information Transmission, 2003
- Simple algorithms for BCH decodingIEEE Transactions on Communications, 1995
- On arithmetical algorithms over finite fieldsJournal of Combinatorial Theory, Series A, 1989
- Holographic dispersal and recovery of informationIEEE Transactions on Information Theory, 1989
- A fast algorithm for the Fourier transform over finite fields and its VLSI implementationIEEE Journal on Selected Areas in Communications, 1988
- On a special class of polynomialsTransactions of the American Mathematical Society, 1933