  In this paper, a new approach for decoding low-rate Reed-Solomon codes beyond
half the minimum distance is considered and analyzed. Unlike the Sudan
algorithm published in 1997, this new approach is based on multi-sequence
shift-register synthesis, which makes it easy to understand and simple to
implement. The computational complexity of this shift-register based algorithm
is of the same order as the complexity of the well-known Berlekamp-Massey
algorithm. Moreover, the error correcting radius coincides with the error
correcting radius of the original Sudan algorithm, and the practical decoding
performance observed on a q-ary symmetric channel (QSC) is virtually identical
to the decoding performance of the Sudan algorithm. Bounds for the failure and
error probability as well as for the QSC decoding performance of the new
algorithm are derived, and the performance is illustrated by means of examples.
