Fast Erasure Decoding of Reed-Solomon Codes Based on Decomposition of Vandermonde Matrix
Zebing Lin, Jingjie Lv, Pingping Li, Linqi Song, Hui Ping Liang, Hanxu Hou · 2024
Reed-Solomon (RS) codes are widely applied in storage systems. The main bottleneck of RS codes is that the high decoding complexity defined as the number of multiplications and additions. In this paper, we propose a fast decoding algorithm for RS codes that requires fewer number of multiplications. Our fast decoding algorithm is designed by a decomposition of Vandermonde matrices. We show that our decoding algorithm requires fewer number of multiplications than the existing best known algorithm when the number of parities$T$is large. When the codeword length$N=16$, our decoding algorithm reduces the number of multiplications by 7% and 29% when$T=4$and$T=7$, respectively, compared with the best known decoding algorithm.