Fast Erasure Decoding of Reed-Solomon Codes Based on Decomposition of Vandermonde Matrix

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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T$</tex> is large. When the codeword length <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N=16$</tex>, our decoding algorithm reduces the number of multiplications by 7% and 29% when <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T=4$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T=7$</tex>, respectively, compared with the best known decoding algorithm.