Multiplicity Assignments for Algebraic Soft-Decoding of Reed-Solomon Codes using the Method of Types

The probability of error in the Koetter-Vardy algebraic soft-decoding algorithm for Reed-Solomon codes is determined by the multiplicity assignment scheme used. A multiplicity assignment scheme converts the reliability matrix Pi, consisting of the probabilities observed at the channel output, into a multiplicity matrix M that specifies the algebraic interpolation conditions. Using the method of types, Sanov's theorem in particular, we obtain tight exponential bounds on the probability of decoding error for a given multiplicity matrix. These bounds turn out to be essentially the same as the Chernoff bound. We establish several interesting properties of the multiplicity matrix M-dagger which minimizes the exponent of the probability of error. Based on these observations, we develop a low-complexity multiplicity assignment scheme which uses nested bisection to solve for M-dagger. This scheme provides the same probability of error as a known scheme based upon the Chernoff bound, but with much lower complexity. We also derive a simple condition on the reliability matrix Pi which guarantees an exponentially small probability of error. This condition is akin to an error-correction radius, and can be used to study the performance of algebraic soft-decoding.