Most traditional bivariate polynomial interpolation algorithms need to construct the Gröbner basis of a module for the interpolation result. In this paper, we present an algorithm that constructs the basis for a gradually extending submodule to save computation, based on a partial order of the elements of the submodule's Gröbner basis. It also can be generalized for negative weighted interpolation and multivariate interpolation.

The algebraic soft-decision decoding (ASD) algorithm is a polynomial-time soft decoding algorithm for Reed-Solomon (RS) codes. It outperforms both the algebraic hard-decision decoding (AHD) and the conventional unique decoding algorithms, but with a high computational cost. This paper proposes a progressive ASD (PASD) algorithm that enables the conventional ASD algorithm to perform decoding with an adjustable designed factorization output list size (OLS). The OLS is enlarged progressively leading to an incremental computation for the interpolation and an enhanced error-correction capability. Multiple factorizations are performed in order to find out the intended message polynomial which will be validated by a cyclic redundant check (CRC) code. The incremental interpolation constraints are introduced to characterize the progressive decoding. The validity analysis of the algorithm shows the PASD algorithm is a natural and computationally saving generalization of the ASD algorithm, delivering the same interpolation solution. The average decoding complexity of the algorithm is further theoretically characterized, revealing its dependence on the channel condition. The simulation results further validate the analysis by showing that the average decoding complexity can be converged to the minimal level in a good channel condition. Finally, performance evaluation shows the PASD algorithm preserves the error-correction capability of the ASD algorithm.

We correct two errors that appeared in the paper by Kaneko