A displacement structure approach to decoding algebraic geometric codes

Using methods originating in numerical analysis, we will develop a unified framework for derivation of efficient list decoding algorithms for algebraicgeometric codes. We will demonstrate our method by accelerating Sudan's list decoding algorithm for Reed-Solomon codes [22], its generalization to algebraic-geometric codes by Shokrollahi and Wasserman [21], and the recent improvement of Guruswami and Sudan [8] in the case of ReedSolomon codes. The basic problem we attack in this paper is that of efficiently finding nonzero elements in the kernel of a structured matrix. The structure of such an n x n-matrix allows it to be "compressed" to ? n parameters for some ? which is usually a constant in applications. The concept of structure is formalized using the displacement operator. The displacement operator allows to perform matrix operations on the compressed version of the matrix. In particular, we can find a PLU- decomposition of the original matrix in time O(? n2), which is quadratic in n for constant ?. We will derive appropriate displacement operators for matrices that occur in the context of list decoding, and apply our general algorithm to them. For example, we will obtain algorithms that use O(n2 l) and O(n7/3 l) operations over the base field for list decoding of Reed-Solomon codes and algebraic-geometric codes from certain plane curves, respectively, where l is the length of the list. Assuming that l is constant, this gives algorithms of running time O(n2) and O(n7/3), which is the same as the running time of conventional decoding algorithms. We will also sketch methods to parallelize our algorithms