We investigate the decoding region for algebraic soft-decision decoding (ASD) of Reed-Solomon (RS) codes in a discrete, memoryless, additive-noise channel. An expression is derived for the error correction radius within which the soft-decision decoder produces a list that contains the transmitted codeword. The error radius for ASD is shown to be larger than that of Guruswami-Sudan (GS) hard-decision decoding for a subset of low and medium-rate codes. These results are also extended to multivariable interpolation in the sense of Parvaresh and Vardy.

We bound the probability of error of Algebraic Soft-Decision Decoding (ASD) of Reed-Solomon codes in a discrete, memoryless, additive-noise channel. First, we derive an exponential error bound on the probability of list-decoding error that improves on the bound presented in [9]. However, our previous work [1] has shown that list-decoding error is not sufficient to adequately characterize ASD's performance. Thus, we redefine an error as the event that the decoder selects an erroneous codeword from its list, and we derive an exponential error bound for the probability of selection error.