Key equations for list decoding of Reed-Solomon codes and how to solve them
Key equations for list decoding of Reed-Solomon codes and how to solve them
复制标题
DOI：
10.1016/j.jsc.2010.03.010
复制
发表时间：
2010-07
期刊：
影响因子：
--
通讯作者：
Peter Beelen;K. Brander
中科院分区：
文献类型：
--
作者：
Peter Beelen;K. Brander
长度为n的里德-所罗门码可以使用众所周知的Guruswami-苏丹算法进行列表译码。根据Alekhnovich(2005)的结果，该算法的内插部分的复杂度为O(S414nlog2nlogn)，其中L表示所设计的链表大小，S表示重数参数。在复杂度分析中，L和S的参数有时被认为是常数，但对于高码率的里德-所罗门码，它们的值可能很大。本文将把Alekhnovich(2005)的思想和关键方程的概念结合起来，得到一个复杂度为O(Sl4nlog2nloglogn)的算法。这与其他已知插补算法的复杂性相比是有利的。
A Reed–Solomon code of length n can be list decoded using the well-known Guruswami–Sudan algorithm. By a result of Alekhnovich (2005) the interpolation part in this algorithm can be done in complexity O(s4l4nlog2nloglogn), where l denotes the designed list size and s the multiplicity parameter. The parameters l and s are sometimes considered to be constants in the complexity analysis, but for high rate Reed–Solomon codes, their values can be very large. In this paper we will combine ideas from Alekhnovich (2005) and the concept of key equations to get an algorithm that has complexity O(sl4nlog2nloglogn). This compares favorably to the complexities of other known interpolation algorithms.