A Displacement Structure Approach to Efficient Decoding of Algebraic Geometric Codes

Using methods originating in numerical analysis, we will develop a unified framework for derivation of efficient list decoding algorithms for algebraic-geometric codes. We will demonstrate our method by accelerating Sudan's list decoding algorithms for Reed Solomon codes as well as its generalization to algebraic geometric codes by Shokrollahi and Wasserman. The basic problem we attack in this paper is that of efficiently finding nonzero elements in the kernel of a structured matrix. The concept of structure is formalized using the so-called displacement operator. The structure of such an n x n- matrix allows it to be "compressed" to alpha n parameters for some alpha which is usually a constant. 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 (alpha n sup 2), which is quadratic in n for constant alpha.