Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes
Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes
复制标题
多项式上的线性丢番图方程和 Reed-Solomon 码的软解码
DOI：
10.1109/sfcs.2002.1181968
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Michael Alekhnovich
中科院分区：
文献类型：
--
作者：
Michael Alekhnovich
本文推广了经典的Knuth-Schonhage算法，将其推广到求解任意多项式时间上的最大次拟线性丢番图方程组。作为应用，我们考虑以下加权曲线拟合问题：给定平面上的一组点，找到一条代数曲线（满足一定的度条件），通过每个点的规定次数。这个问题的主要动机来自于编码理论，即它最终与Reed-Solomon码的列表译码有关。基于显式构造Groebner基，提出了一种新的加权曲线拟合快速算法。这给出了一种不同于Feng（1999）提出的在时间（w/r）/sup O（1）/nlog/sup 2/nloglogn内工作的Reed-Solomon码软译码的快速算法，其中r是码的码率，w是分配给垂直线的最大权值。
We generalize the classical Knuth-Schonhage algorithm computing GCD of two polynomials for solving arbitrary linear Diophantine systems over polynomials in time, quasi-linear in the maximal degree. As an application, we consider the following weighted curve fitting problem: given a set of points in the plain, find an algebraic curve (satisfying certain degree conditions) that goes through each point the prescribed number of times. The main motivation for this problem comes from coding theory, namely it is ultimately related to the list decoding of Reed-Solomon codes. We present a new fast algorithm for the weighted curve fitting problem, based on the explicit construction of Groebner basis. This gives another fast algorithm for soft-decoding of Reed-Solomon codes different from the procedure proposed by Feng (1999), which works in time (w/r)/sup O(1)/ n log/sup 2/ n loglogn, where r is the rate of the code, and w is the maximal weight assigned to a vertical line.