A progressive interpolation approach for Guruswami-Sudan algorithm

In this paper, we present a progressive interpolation approach in Guruswami-Sudan (GS) decoding of Reed-Solomon (RS) codes. The objective of the interpolation is to construct the minimal polynomial Q(x, y) by the progressive approach with increasing multiplicities until the roots of Q(x, y) give the correct message. Then the error-correction capability can be adaptively obtained by assigning a suitable multiplicity according to the number of errors occurred in the channel. We present an efficient way to update the polynomial set utilizing the previous computational results in the interpolation step. It enables the decoder to adjust its decoding complexity to the needed level. Simulation results suggest that the average decoding complexity of GS algorithm can be significantly reduced by the progressive approach for RS codes.