Multiplicity assignments for algebraic soft-decoding of reed-solomon codes
Farzad Parvaresh, Alexander Vardy · 2003
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 h{SM 5 A(M)}, where SM is a random variable and A(M) is a known func- tion of M. They then compute the multiplicity matrix M that maximizes the eqected value of SM. Here, we attempt to directly minimize the overall probability of decoding fail- ure PT{SM < A(M)}. First, we recast this optimization problem into a geometrical framework. Using this frame- work, 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 5 A(M)} under this approximation. This leads to coding gains of about 0.20dB for RS codes of length 255 and up to 0.75dB for RS codes of length 15, as compared to the Koetter-Vardy algorithm.