Title :
Polynomial matrix-chain interpolation in sudan-type reed-solomon decoders
Author :
Parvaresh, Farzad ; Vardy, Alexander
Author_Institution :
California Univ., San Diego, La Jolla, CA
Abstract :
The main computational steps in algebraic soft-decoding and/or Sudan-type list-decoding of Reed-Solomon codes are interpolation and factorization. The interpolation consists of computing a bivariate polynomial Q(X,Y) that passes through a prescribed set of points with prescribed multiplicities. Using the iterative algorithm of Koetter (1996), this computation can be accomplished in time O(N2), where N is the number of linear equations satisfied by the coefficients of Q(X,Y). Here, we recast the iterative interpolation procedure of (R. Koetter, 1996) as a computation of the product of a certain chain of polynomial matrices. We then derive a dynamic-programming algorithm which optimizes the multiplication order in computing this matrix chain. The resulting optimization reduces the number of finite-field operations required to compute Q(X,Y) by a factor of about two
Keywords :
Reed-Solomon codes; algebraic codes; dynamic programming; interpolation; iterative methods; optimisation; polynomial matrices; Sudan-type Reed-Solomon decoders; algebraic soft-decoding; bivariate polynomial matrices; dynamic-programming algorithm; iterative algorithm; optimization; polynomial matrix-chain interpolation; Cost function; Equations; Heuristic algorithms; Interpolation; Iterative algorithms; Iterative decoding; Polynomials; Reed-Solomon codes;
Conference_Titel :
Information Theory, 2004. ISIT 2004. Proceedings. International Symposium on
Conference_Location :
Chicago, IL
Print_ISBN :
0-7803-8280-3
DOI :
10.1109/ISIT.2004.1365424