Algebraic soft decoding of Reed-Solomon codes with improved progressive interpolation
Algebraic soft decoding of Reed-Solomon codes with improved progressive interpolation
复制标题
具有改进的渐进插值的 Reed-Solomon 码的代数软解码
DOI：
10.1016/j.phycom.2016.06.001
复制
发表时间：
2016-09
期刊：
影响因子：
--
通讯作者：
Li Chen
中科院分区：
文献类型：
--
作者：
Yi Lyu;Li Chen
RS码的代数软译码（ASD）算法可以纠正超过半距离界的错误，具有多项式时间复杂度。然而，解码复杂度仍然很高，这是由于计算上昂贵的插值是一个迭代的多项式构造过程。通过渐进地执行内插，渐进ASD（PASD）算法可以使解码计算适应需要，从而利用多个解码事件的平均复杂度。但是复杂度的降低是以系统存储器为代价实现的，因为中间插值信息需要被存储。针对这一挑战，本文提出了一种改进的PASD（I-PASD）算法，可以减轻存储需求，进一步降低解码复杂度。将引入一个扩展插值多项式集的条件，该条件排除了对新引入的多项式进行迭代更新的需要。I-PASD算法进一步结合了重编码变换，使译码复杂度比PASD算法降低1/3，而所需存储量最多只有PASD算法的一半。理论上分析了算法的复杂度和内存需求，并通过数值计算进行了验证。最后，我们将确认的复杂性和内存的减少实现与保留的ASD算法的纠错能力。
The algebraic soft decoding (ASD) algorithm for Reed–Solomon (RS) codes can correct errors beyond the half distance bound with a polynomial time complexity. However, the decoding complexity remains high due to the computationally expensive interpolation that is an iterative polynomial construction process. By performing the interpolation progressively, the progressive ASD (PASD) algorithm can adapt the decoding computation to the need, leveraging the average complexity of multiple decoding events. But the complexity reduction is realised at the expense of system memory, since the intermediate interpolation information needs to be memorised. Addressing this challenge, this paper proposes an improved PASD (I-PASD) algorithm that can alleviate the memory requirement and further reduce the decoding complexity. A condition on expanding the set of interpolated polynomials will be introduced, which excepts the need of performing iterative updates for the newly introduced polynomial. Further incorporating the re-encoding transform, the I-PASD algorithm can reduce the decoding complexity over the PASD algorithm by a factor of 1/3 and its memory requirement is at most half of the PASD algorithm. The complexity and memory requirement will be theoretically analysed and validated by numerical results. Finally, we will confirm that the complexity and memory reductions are realised with preserving the error-correction capability of the ASD algorithm.
登录
查看更多内容
影响因子：
2.5
作者：
Yuval Cassuto;Jehoshua Bruck;R. McEliece
通讯作者：
Yuval Cassuto;Jehoshua Bruck;R. McEliece
DOI：
10.1109/isit.2006.261906
发表时间：
2006-07
期刊：
2006 IEEE International Symposium on Information Theory
影响因子：
--
作者：
Kwankyu Lee;M. O'Sullivan
通讯作者：
Kwankyu Lee;M. O'Sullivan
影响因子：
2.5
作者：
Yingquan Wu
通讯作者：
Yingquan Wu
DOI：
10.1109/isit.1998.708637
发表时间：
1998-08
期刊：
Proceedings. 1998 IEEE International Symposium on Information Theory (Cat. No.98CH36252)
影响因子：
--
作者：
R. Roth;G. Ruckenstein
通讯作者：
R. Roth;G. Ruckenstein
DOI：
10.1016/j.jsc.2010.03.010
发表时间：
2010-07
期刊：
J. Symb. Comput.
影响因子：
--
作者：
Peter Beelen;K. Brander
通讯作者：
Peter Beelen;K. Brander