A displacement approach to decoding algebraic codes

Using methods originating in numerical analysis, we will develop a unied framework for derivation of eÆcient algorithms for decoding several classes of algebraic codes. We will demon-strate 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 im-provement of Guruswami and Sudan [9] in the case of Reed-Solomon codes. The basic problem we attack in this paper is that of eÆciently nding nonzero elements in the kernel of a structured matrix. The structure of such an n 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. It allows to perform matrix operations on the compressed version of the matrix. In particular, we can nd a nontrivial element in the kernel of such a matrix in time O(n 2), if it exists. 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(