Re-Encoding Reformulation and Application to Welch-Berlekamp Algorithm

The main decoding algorithms for Reed-Solomon codes are based on a bivariate interpolation step, which is expensive in time complexity. Lot of interpolation methods were proposed in order to decrease the complexity of this procedure but stay expensive. Then Koetter, Ma and Vardy proposed in 2010 a technique, called re-encoding, which permits to reduce the running time. However this trick is devoted for the Koetter interpolation algorithm. The authors propose a reformulation of the re-encoding for any interpolation methods. Finally, they apply it to the Welch-Berlekamp algorithm.