Efficient decoding of Reed-Solomon codes beyond half the minimum distance

A list decoding algorithm-is presented for [n, k] Reed-Solomon (RS) codes o ver GF(q), which is capable of correcting more than right perpendicular(n-k )/2left perpendicular errors. Based on a previous work of Sudan, an extende d key equation (EKE) is derived for RS codes, which reduces to the classica l key equation when the number of errors is Limited to right perpendicular( n-k)/2left perpendicular. Generalizing Massey's algorithm that finds the sh ortest recurrence that generates a given sequence, an algorithm is obtained for solving the EKE in time complexity O(l.(n-k)(2)), where l is a design parameter, typically a small constant, which is an upper bound on the size of the list of decoded codewords. (The case l = 1 corresponds to classical decoding of up to right perpendicular(n-k)/2left perpendicular errors where the decoding ends with at most one codeword.) This improves on the time co mplexity O(n(3)) needed for solving the equations of Sudan's algorithm by a naive Gaussian elimination. The polynomials found by solving the ERE are t hen used for reconstructing the codewords in time complexity O((l log(2) l) k(n+l log q)) using root-finders of degree-l univariate polynomials.