Reduced Complexity Interpolation for List Decoding Hermitian Codes
Reduced Complexity Interpolation for List Decoding Hermitian Codes
复制标题
DOI：
10.1109/t-wc.2008.070615
复制
发表时间：
2008-11
影响因子：
10.4
通讯作者：
Li Chen;R. Carrasco;M. Johnston
中科院分区：
文献类型：
--
作者：
Li Chen;R. Carrasco;M. Johnston
使用 Guruswami-Sudan (GS) 算法进行列表解码埃尔米特码可以纠正超过设计最小距离一半的错误。它由两个过程组成：插值和因式分解。通过首先定义埃尔米特曲线，这些过程可以分别用迭代多项式构造算法和递归系数搜索算法来实现。为了提高列表解码埃尔米特码的效率，本文提出了两个降低插值复杂度的贡献。首先，为了简化迭代插值过程中多项式零条件的计算，我们提出了一种确定埃尔米特曲线的极基单项式和零基函数之间对应系数的算法。其次，我们提出了一种改进的复杂性降低插值算法。该方案在迭代过程中识别任何不必要的多项式并消除它们以提高插值效率。由于上述复杂度降低的修改，具有更高插值重数的长埃尔米特码的列表解码变得可行。本文表明列表解码算法比传统的独特解码算法可以获得显着的编码增益。
List decoding Hermitian codes using the Guruswami-Sudan (GS) algorithm can correct errors beyond half the designed minimum distance. It consists of two processes: interpolation and factorisation. By first defining a Hermitian curve, these processes can be implemented with an iterative polynomial construction algorithm and a recursive coefficient search algorithm respectively. To improve the efficiency of list decoding Hermitian codes, this paper presents two contributions to reduce the interpolation complexity. First, in order to simplify the calculation of a polynomialiquests zero condition during the iterative interpolation, we propose an algorithm to determine the corresponding coefficients between the pole basis monomials and zero basis functions of a Hermitian curve. Second, we propose a modified complexity reducing interpolation algorithm. This scheme identifies any unnecessary polynomials during iterations and eliminates them to improve the interpolation efficiency. Due to the above complexity reducing modifications, list decoding long Hermitian codes with higher interpolation multiplicity becomes feasible. This paper shows list decoding algorithm can achieve significant coding gain over the conventional unique decoding algorithm.