Multiplicity assignments for algebraic soft-decoding of Reed-Solomon codes

Abstract

A soft-decision decoding algorithm for Reed-Solomon codes was recently proposed in [2]. This algorithm converts probabilities observed at the channel output into algebraic interpolation conditions, specified in terms of a multiplicity matrix M. Koetter-Vardy [2] show that the probability of decoding failure is given by Pr{SM ≤ Δ(M)}, where SM is a random variable and Δ(M) is a known function of M. They then compute the multiplicity matrix M that maximizes the expected value of SM. Here, we attempt to directly minimize the overall probability of decoding failure Pr{SM ≤ Δ(M)}. First, we recast this optimization problem into a geometrical framework. Using this framework, we derive a simple modification to the KV algorithm which results in a provably better multiplicity assignment. Alternatively, we approximate the distribution of SM by a Gaussian distribution, and develop an iterative algorithm to minimize Pr{SM ≤ Δ(M)} under this approximation. This leads to coding gains of about 0.20 dB for RS codes of length 255 and up to 0.75 dB for RS codes of length 15, as compared to the Koetter-Vardy algorithm.