The periodicity transform in algebraic decoding of Reed-Solomon codes

The computationally most expensive part of the Guruswami-Sudan algorithm for list-decoding of Reed-Solomon codes beyond half their minimum distance is its interpolation step. The latter requires solving a linear system of equations whose size is a multiple of the code length n. This results in time complexity cubic in n. Using an interpretation due to Gemmell and Sudan, the Welch-Berlekamp algorithm can be considered as a special case of the Guruswami-Sudan algorithm. We propose a new transform (a special case of the re-encoding transform), prove that it allows to shrink the size of the linear system in this case to a factor of n, and provide the detailed steps of the corresponding decoding algorithm. It is hinted that the reduced coefficient matrix can easily be converted into block Hankel form, which allows for further improvements up to the time complexity of widely used decoding algorithms for Reed-Solomon codes, i.e., O [d²], where d is the minimum distance. We conjecture that these techniques can be applied to the linear system in the general Guruswami-Sudan case as well in order to derive an O [d²] decoding algorithm and give first results in this direction.