Two Fast Erasure Decoding Algorithms for Reed–Solomon Codes Based on LCH-FFT

IEEE Transactions on Information Theory 2026

View at publisher
Authors: Chao Chen, Sian-Jheng Lin, Nianqi Tang, Yunghsiang Sam Han, Suihua Cai, Leilei Yu, Zhongwei Li, Baoming Bai, Bo Bob Bai
DOI: 10.1109/tit.2026.3685291
Cited by: 1
References: 36

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 lengthNand dimensionK. The first algorithm applies to low-rate RS codes (i.e.,K/N≤ 0:5) and achieves a complexity ofO(N log K). The second algorithm applies to high-rate RS codes (i.e.,K/N≥ 0:5) and achieves a complexity ofO(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.

Fields of Study & Subjects

Coding theory and cryptography Cryptography and Residue Arithmetic Error Correcting Code Techniques

Publication details

Journal / source
IEEE Transactions on Information Theory
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Volume
72
Issue
6
Pages
3784–3798
Publication date
20 April 2026