A modified Guruswami–Sudan algorithm for decoding Reed–Solomon codes

We tighten a key estimate, which dictates the computational complexity of Guruswami–Sudan algorithm, on the lower bound of the degrees of freedom, and then propose a modified decoding algorithm for Reed–Solomon codes beyond half the minimum distance. The computational complexity of the modified algorithm is lower than the Guruswami–Sudan algorithm for the medium to high rate Reed–Solomon codes, and has the same asymptotic complexity as the algorithm proposed by Wu. Besides we also claim that our modified algorithm outperforms Wu's algorithm to some extent.

Research highlights
► Tighten a key estimate in Guruswami–Sudan algorithm and propose a modified decoding algorithm for Reed–Solomon codes beyond half the minimum distance.
► Give the complexity analysis of the modified decoding algorithm.
► Compare the modified algorithm's computational complexity and the parameters to be chosen with Guruswami et al. and Wu's work.