Polynomial matrix-chain interpolation in Sudan-type Reed-Solomon decoders

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, 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 [2] 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.