Improved decoding of Reed-Solomon and algebraic-geometric codes

Cir En an error-correcting code over strings of length n and an arbitrary input string also of length n. the list decoding problem is that of finding all codewords within a specified Hamming distance from the input string. We present an improved list decoding algorithm for decoding Reed-Solomon codes. The list decoding problem for Reed-Solomon codes reduces to the following "curve-fitting" problem over a field F: Given n points {(x(i).y(i))}(i=1)(n), x(i),y(i) is an element of F and a degree parameter k and error parameter F, find all univariate polynomials p of degree at most k such that y(i) = p(x(i)) for all but at most e values of i is an element of ( 1...., n). We give an algorithm that soh es this problem for e < n - root kn, which improves ar er the previous best result [22], for every choice of k and n. Of particular interest is the case of k/n > 1/3. Ic here the result yields the first asymptotic improvement irt four decades [15]. The algorithm generalizes to solve the list decoding problem for other algebraic codes. specifically alternant codes (a class of codes including BCH codes) and algebraic-geometric cones. In both cases, we obtain a list decoding algorithm that corrects Icp to n - root n(n - d') errors, where n is the block length and d' is the designed distance of the code. The improvement for the case of algebraic-geometric codes extends the methods of [19] and improves upon their bound for ever? choice of n and d'. We also present some other consequences of our algorithm including a solution to a weighted curve fitting problem, which is of use in soft-decision decoding algorithms for Reed-Solomon codes.