A Complexity Reducing Transformation for the Lee-O'Sullivan Interpolation Algorithm
A Complexity Reducing Transformation for the Lee-O'Sullivan Interpolation Algorithm
复制标题
DOI：
10.1109/isit.2007.4557512
复制
发表时间：
2007-06
期刊：
影响因子：
--
通讯作者：
Jun Ma;A. Vardy
中科院分区：
文献类型：
--
作者：
Jun Ma;A. Vardy
最近，Lee 和 O'Sullivan 提出了一种用于 Reed-Solomon 码代数软决策解码的新插值算法。在某些情况下，Lee-O'Sullivan 算法比其他插值方法（例如 Koetter 算法）要高效得多。在这里，我们将最初在 Koetter 算法背景下开发的重新编码坐标变换与 Lee 和 O'Sullivan 最近的插值技术相结合。为此，我们开发了一种新的基础构造算法，该算法考虑了重新编码变换所导致的减少插值问题所施加的额外约束。这将 Lee-O'Sullivan 算法的计算和存储复杂度降低了几个数量级，并使其在实际重要的情况下可以直接与 Koetter 算法相媲美。
Recently, Lee and O'Sullivan proposed a new interpolation algorithm for algebraic soft-decision decoding of Reed- Solomon codes. In some cases, the Lee-O'Sullivan algorithm turns out to be substantially more efficient than alternative interpolation approaches, such as Koetter's algorithm. Herein, we combine the re-encoding coordinate transformation, originally developed in the context of Koetter's algorithm, with the recent interpolation technique of Lee and O'Sullivan. To this end, we develop a new basis construction algorithm, which takes into account the additional constraints imposed by the reduced interpolation problem that results upon the re-encoding transformation. This reduces the computational and storage complexity of the Lee-O'Sullivan algorithm by orders of magnitude, and makes it directly comparable to Koetter's algorithm in situations of practical importance.