Fast Error and Erasure Decoding Algorithm for Reed-Solomon Codes
Nianqi Tang, Chao Chen, Yunghsiang Sam Han · IEEE Communications Letters · 2024
Reed-Solomon (RS) codes are widely used to correct errors and erasures. This paper proposes a fast error and erasure decoding algorithm for RS codes. It achieves the best-known complexityO(nlog(n-k)+(n-k) log2(n-k)), wheren,kare the code length and dimension, respectively. Furthermore, the proposed method is efficient for practical codes. For decoding RS(255, 223), compared with the existing method, the new algorithm saves 32% field operations.