A list decoding for an error-correcting code is a decoding algorithm that generates a list of codewords within a Hamming distance t from the received vector, where t can be greater than the error-correction bound. In previous work by M. Shokrollahi and H. Wasserman (see ibid., vol.45, p.432-7, March 1999) a list-decoding procedure for Reed-Solomon codes was generalized to algebraic-geometric codes. Recent work by V. Guruswami and M. Sudan (see ibid., vol.45, p.1757-67, Sept. 1999) gives improved list decodings for Reed-Solomon codes and algebraic-geometric codes that work for all rates and have many applications. However, these list-decoding algorithms are rather complicated. R. Roth and G. Ruckenstein (see ibid., vol.46, p.246-57, Jan. 2000) proposed an efficient implementation of the list decoding of Reed-Solomon codes. In this correspondence, extending Roth and Ruckenstein's fast algorithm for finding roots of univariate polynomials over polynomial rings, i.e., the reconstruct algorithm, we present an efficient algorithm for finding the roots of univariate polynomials over function fields. Based on the extended algorithm, we give an efficient list-decoding algorithm for algebraic-geometric codes
展开▼
机译：纠错码的列表解码是一种解码算法，可生成距接收到的矢量的汉明距离t以内的码字列表，其中t可以大于纠错范围。在M. Shokrollahi和H. Wasserman的先前工作中（参见同上，第45卷，第432-7页，1999年3月），将里德-所罗门代码的列表解码过程推广到了代数几何代码。 V. Guruswami和M. Sudan的最新工作（同上，第45卷，第1757-67页，1999年9月）提供了适用于所有速率且具有以下特征的里德-所罗门码和代数几何码的改进列表解码许多应用。但是，这些列表解码算法相当复杂。 R. Roth和G. Ruckenstein（同上，第46卷，第246-57页，2000年1月）提出了Reed-Solomon码的列表解码的有效实现。在这种对应关系中，扩展了罗斯（Roth）和鲁肯斯坦（Ruckenstein）的快速算法以在多项式环上找到一元多项式的根，即重构算法，我们提出了一种在函数域上找到一元多项式的根的有效算法。在扩展算法的基础上，给出了一种高效的代数几何代码列表解码算法。
展开▼
