Improved decoding of Reed-Solomon and algebraic-geometry codes
Improved decoding of Reed-Solomon and algebraic-geometry codes
复制标题
DOI：
10.1109/18.782097
复制
发表时间：
1999-09-01
影响因子：
2.5
通讯作者：
Sudan, M
中科院分区：
文献类型：
--
作者：
Guruswami, V;Sudan, M
给定一个长度为n的字符串的纠错码和一个长度为n的任意输入字符串，列表解码问题是在输入字符串的指定Ramming距离内找到所有码字。本文提出了一种改进的译码Reed-Solomon码的列表译码算法，将Reed-Solomon码的列表译码问题归结为域F上的曲线拟合问题：给定n个点{（x（i）.y（i））}（i=1）（n），x（i），y（i）是F中的元素，以及次数参数L和误差参数e，求出次数不超过I的所有一元多项式p;使得y（i）= p（x（i））对于i的所有但至多e个值是{1，.，n}，我们给出了一个算法，解决了这个问题的e < n -根kn，它改善了以前的最佳结果[27]，对于k和n的每一个选择，特别感兴趣的是k/n > 1/3的容易性，其中结果产生了四十年来的第一个渐近改进[21]，该算法推广到解决其他代数码的列表解码问题，特别是交替码（包括BCH码的一类码）和代数几何码。在这两种情况下，我们得到一个列表解码算法，纠正高达n -根n（n-d '）错误，其中n是块的长度和d'是设计的距离的代码。对代数几何码的改进扩展了[24]的方法，并改进了它们对n和d '的每一个选择的界。我们还提出了一些其他的后果，我们的算法，包括加权曲线拟合问题的解决方案，这可能是使用软判决解码算法的Reed-Solomon码。
Given an error-correcting code over strings of length n and an arbitrary input string also of length n, the List decoding problem is that of finding all codewords within a specified Ramming distance from the input string. me present an improved list decoding algorithm for decoding Reed-Solomon codes, The list decoding problem for Reed-Solomon codes reduces to the following "curve-fitting" problem over a field F: Given n points {(x(i).y(i))}(i=1)(n), x(i) ,y(i) is an element of F, and a degree parameter L and error parameter e, find all univariate polynomials p of degree at most I; such that y(i) = p(x(i)) for all but at most e values of i is an element of {1, ..., n}, We give an algorithm that solves this problem for e < n - root kn, which improves over the previous best result [27], for every choice of k and n, Of particular interest is the ease of k/n > 1/3, where the result yields the first asymptotic improvement in four decades [21], The algorithm generalizes to solve the list decoding problem for other algebraic codes, specifically alternant codes (a class of codes including BCH codes) and algebraic-geometry codes. In both cases, we obtain a list decoding algorithm that corrects up to n - root n(n - d') errors, where n is the block length and d' is the designed distance of the code. The improvement for the case of algebraic-geometry codes extends the methods of [24] and improves upon their bound for every choice of n and d'. We also present some other consequences of our algorithm including a solution to a weighted curve-fitting problem, which may be of use in soft-decision decoding algorithms for Reed-Solomon codes.