Algebraic soft decoding of reed-solomon codes

Abstract

An algorithmic soft-decision decoding method for Reed-Solomon codes proceeds as follows. Given the reliability matrix Π showing the probability that a code symbol of a particular value was transmitted at each position, computing a multiplicity matrix M which determines the interpolation points and their multiplicities. Given this multiplicity matrix M, soft interpolation is performed to find the non-trivial polynomial Q (X,Y) of the lowest (weighted) degree whose zeros and their multiplicities are as specified by the matrix M. Given this non-trivial polynomial Q (X,Y), all factors of Q (X,Y) of type Y−ƒ(X) are found, where ƒ(X) is a polynomial in X whose degree is less than the dimension k of the Reed-Solomon code. Given these polynomials ƒ(X), a codeword is reconstructed from each of them, and the most likely of these codewords selected as the output of the algorithm. The algorithmic method is algebraic, operates in polynomial time, and significantly outperforms conventional hard-decision decoding, generalized minimum distance decoding, and Guruswami-Sudan decoding of Reed-Solomon codes. By varying the total number of interpolation points recorded in the multiplicity matrix M, the complexity of decoding can be adjusted in real time to any feasible level of performance. The algorithmic method extends to algebraic soft-decision decoding of Bose-Chaudhuri-Hocquenghem codes and algebraic-geometry codes.