• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Efficient decoding of Reed-Solomon codes beyond half the minimum distance
【24h】

Efficient decoding of Reed-Solomon codes beyond half the minimum distance

机译：里德-所罗门码的有效解码超过最小距离的一半

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A list decoding algorithm is presented for [n,k] Reed-Solomon (RS) codes over GF(q), which is capable of correcting more than [(n-k)/2] errors. Based on a previous work of Sudan (see J. Compl., vol.13, p.180-93, 1997), an extended key equation (EKE) is derived for RS codes, which reduces to the classical key equation when the number of errors is limited to [(n-k)/2]. Generalizing Massey's (1969) algorithm that finds the shortest recurrence that generates a given sequence, an algorithm is obtained for solving the EKE in time complexity O(l/spl middot/(n-k)/sup 2/), where l is a design parameter, typically a small constant, which s an upper bound on the size of the list of decoded codewords. (The case l=1 corresponds to classical decoding of up to [(n-k)/2] errors where the decoding ends with at most one codeword.) This improves on the time complexity O(n/sup 3/) needed for solving the equations of Sudan's algorithm by a naive Gaussian elimination. The polynomials found by solving the EKE are then used for reconstructing the codewords in time complexity O((llog/sup 2/l)k(n+llogq)) using root-finders of degree-l univariate polynomials.
机译：针对GF（q）上的[n，k] Reed-Solomon（RS）码，提出了一种列表解码算法，该算法能够校正[[n-k）/ 2]个以上的错误。根据苏丹的先前工作（请参见J. Compl。，第13卷，第180-93页，1997年），为RS码推导了扩展密钥方程（EKE），当数字为错误数限制为[（nk）/ 2]。概括了Massey（1969）的算法，该算法找到了生成给定序列的最短重复发生时间，从而获得了一种算法，用于求解时间复杂度为O（l / spl middot /（nk）/ sup 2 /）的EKE，其中l是设计参数，通常是一个小常数，它是已解码代码字列表的大小的上限。 （情况l = 1对应于最多[[nk] / 2]个错误的经典解码，其中解码最多以一个码字结束。）这提高了解决该问题所需的时间复杂度O（n / sup 3 /）。朴素高斯消除法求解苏丹算法的方程组。然后，使用1级单变量多项式的根查找器将通过求解EKE得出的多项式用于重建时间复杂度O（（llog / sup 2 / l）k（n + llogq））的码字。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号