Reduced-Complexity Erasure Decoding of Low-Rate Reed–Solomon Codes Based on LCH-FFT

This paper presents a new erasure decoding algorithm for low-rate Reed–Solomon codes (rate ≤ 0.5) based on a recently proposed FFT known as LCH-FFT. The algorithm requires O(n log k) finite field operations, where n and k are the code’s length and dimension, respectively. Experiments based on the Intel AVX2 Instructions show that notable improvements in the throughput are achieved compared with the best-known algorithm with complexity O(n log n) (also based on LCH-FFT), and new speed records are created.