  Recently, a number of authors have proposed decoding schemes for Reed-Solomon
(RS) codes based on multiple trials of a simple RS decoding algorithm. In this
paper, we present a rate-distortion (R-D) approach to analyze these
multiple-decoding algorithms for RS codes. This approach is first used to
understand the asymptotic performance-versus-complexity trade-off of multiple
error-and-erasure decoding of RS codes. By defining an appropriate distortion
measure between an error pattern and an erasure pattern, the condition for a
single error-and-erasure decoding to succeed reduces to a form where the
distortion is compared to a fixed threshold. Finding the best set of erasure
patterns for multiple decoding trials then turns out to be a covering problem
which can be solved asymptotically by rate-distortion theory. Next, this
approach is extended to analyze multiple algebraic soft-decision (ASD) decoding
of RS codes. Both analytical and numerical computations of the R-D functions
for the corresponding distortion measures are discussed. Simulation results
show that proposed algorithms using this approach perform better than other
algorithms with the same complexity.
