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 design
and analyze these multiple-decoding algorithms using tools from rate-distortion (R-D)
theory.  By defining an appropriate distortion measure between (generalized) error
patterns and (generalized) erasure patterns, one finds that errors-and-erasures RS
decoding succeeds if and only if the distortion is less than a fixed threshold.
Finding the best set of (generalized) erasure patterns turns out to be a covering
problem which is solved asymptotically by R-D theory.  The Blahut-Arimoto algorithm
is extended to handle independent non-identical sources and used to find the optimal
distribution for the erasure-pattern codebook.  Simulation results show that this
approach outperforms previous approaches for a fixed number of decoding trials.

Since this approach is asymptotic in the block length, it does not lead to precise
theoretical statements for any particular RS code.  An extension, based on the
rate-distortion exponent (RDE), allows one to directly minimize the exponential decay
rate of the error probability.  The RDE method enables rigorous bounds on the error
probability for finite-length RS codes and modest performance gains are observed via
simulation.  In this case, the Arimoto algorithm is modified to handle independent
non-identical sources and used to find the optimal codebook distribution.