Algebraic soft decoding of Reed–Solomon codes with improved progressive interpolation

The algebraic soft decoding (ASD) algorithm for Reed–Solomon (RS) codes can correct errors beyond the half distance bound with a polynomial time complexity. However, the decoding complexity remains high due to the computationally expensive interpolation that is an iterative polynomial construction process. By performing the interpolation progressively, the progressive ASD (PASD) algorithm can adapt the decoding computation to the need, leveraging the average complexity of multiple decoding events. But the complexity reduction is realised at the expense of system memory, since the intermediate interpolation information needs to be memorised. Addressing this challenge, this paper proposes an improved PASD (I-PASD) algorithm that can alleviate the memory requirement and further reduce the decoding complexity. A condition on expanding the set of interpolated polynomials will be introduced, which excepts the need of performing iterative updates for the newly introduced polynomial. Further incorporating the re-encoding transform, the I-PASD algorithm can reduce the decoding complexity over the PASD algorithm by a factor of 1/31/3 and its memory requirement is at most half of the PASD algorithm. The complexity and memory requirement will be theoretically analysed and validated by numerical results. Finally, we will confirm that the complexity and memory reductions are realised with preserving the error-correction capability of the ASD algorithm.