Efficient decoding of Reed-Solomon codes beyond half the minimum distance
Efficient decoding of Reed-Solomon codes beyond half the minimum distance
复制标题
DOI：
10.1109/isit.1998.708637
复制
发表时间：
1998-08
期刊：
影响因子：
--
通讯作者：
R. Roth;G. Ruckenstein
中科院分区：
文献类型：
--
作者：
R. Roth;G. Ruckenstein
为广义的Reed-Solomon（GRS）代码的家族提供了一个列表解码算法，该算法能够纠正大于代码最小距离D的一半的错误。基于苏丹的先前工作（请参阅J. Comp。，第13卷，第180-93页，1997年），为GRS代码提供了扩展的密钥方程，当错误数量时，该方程将减小为经典键方程。仅限于[（D-1）/2]。使用Feng和Tzeng（1991）引起的技术，获得了一种算法来求解D中的扩展键方程。为了进行比较，苏丹算法中各个部分的时间复杂性在代码长度中是立方体。
A list decoding algorithm is presented for the family of generalized Reed-Solomon (GRS) codes, capable of correcting a number of errors greater than half the minimum distance d of the code. Based on a previous work of Sudan (see J. Compl., vol.13, p.180-93, 1997), an extended key equation is derived for GRS codes, which is reduced to the classical key equation when the number of errors is limited to [(d-1)/2]. Using a technique due to Feng and Tzeng (1991), an algorithm is obtained for solving the extended key equation in time complexity quadratic in d. For comparison, the time complexity of the respective part in Sudan's algorithm is cubic in the code length.