TR98-043 Authors: Venkatesan Guruswami, Madhu Sudan

Publication: 31st July 1998 10:24

Downloads: 2910

Keywords:

We present an improved list decoding algorithm for decoding

Reed-Solomon codes. Given an arbitrary string of length n, the

list decoding problem is that of finding all codewords within a

specified Hamming distance from the input string.

It is well-known that this 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 in F, and a

degree parameter k and error parameter e, 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 in {1 .. n}. Our algorithm solves this

problem for e < n - sqrt{kn}, which improves over the previous

best result due to Sudan [FOCS '96], for every choice of k and n.

Previously it was known how to correct approximately max {n -

sqrt{2kn}, (n-k)/2} errors. Of particular interest is the case of

k/n > 1/3, where the result yields the first asymptotic

improvement over the classical Berlekamp-Massey algorithm.

The algorithm generalizes to decode other codes as well. In

particular it immediately yields a list decoding problem for

alternant codes that corrects up to n - sqrt{n(n-d')} errors,

where $n$ is the block length and $d'$ is the designed distance

of the code. Using the methods of Shokrollahi and Wasserman,

[STOC '98], we also extend our algorithm to the case of

algebraic-geometric codes, and solve the list decoding problem

for up to n-sqrt{n(n-d')} errors, where n and d' are as above.

This improves over the previous bound of n-sqrt{2n(n-d')}-g+1

where $g$ denotes the genus of the algebraic curve underlying the

code. We also present some other consequences of our algorithm

including a solution to a weighted curve fitting problem, which

may be of use in soft-decision decoding algorithms for Reed-

Solomon codes.