...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Efficiently Decoding Reed–Muller Codes From Random Errors
【24h】

Efficiently Decoding Reed–Muller Codes From Random Errors

机译：从随机错误中有效解码里德穆勒码

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

摘要

Reed-Muller (RM) codes encode an m-variate polynomial of degree at most r by evaluating it on all points in {0,1}m. We denote this code by RM(r,m). The minimum distance of RM(r,m) is 2m-r and so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result. In this paper we give an efficient algorithm (in the block length n=2m) for decoding random errors in RM codes far beyond the minimum distance. Specifically, for low-rate codes (of degree r=o(√m)), we can correct a random set of (1/2-o(1))n errors with high probability. For high rate codes (of degree m-r for r=o(√m/log m)), we can correct roughly mr/2 errors. More generally, for any integer r, our algorithm can correct any error pattern in RM(m-(2r+2),m), for which the same erasure pattern can be corrected in RM(m-(r+1),m). The results above are obtained by applying recent results of Abbe, Shpilka, and Wigderson (STOC, 2015) and Kudekar et al. (STOC, 2016) regarding the ability of RM codes to correct random erasures. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding RM codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the error-locating pair method of Pellikaan, Duursma, and Kötter that generalizes the Berlekamp-Welch algorithm for decoding Reed-Solomon codes.
机译：里德穆勒（RM）码通过对{0,1} m中的所有点求值，最多对度为m的m变量多项式进行编码。我们用RM（r，m）表示此代码。 RM（r，m）的最小距离为2m-r，因此，在最坏的情况下，它不能校正超过一半的错误。对于随机错误，可能希望获得更好的结果。在本文中，我们给出了一种有效的算法（在块长n = 2m中），用于解码远远超出最小距离的RM代码中的随机错误。具体来说，对于低速率代码（度数r = o（√m）），我们可以以较高的概率校正随机集（1 / 2-o（1））n个错误。对于高速率代码（对于r = o（√m/ log m），为m-r度的代码），我们可以粗略校正mr / 2错误。更笼统地说，对于任何整数r，我们的算法都可以校正RM（m-（2r + 2），m）中的任何错误模式，对于相同的擦除模式，可以在RM（m-（r + 1），m中进行校正）。以上结果是通过应用Abbe，Shpilka和Wigderson（STOC，2015）和Kudekar等人的最新结果而获得的。 （STOC，2016）有关RM代码纠正随机擦除的能力。该算法基于求解一组精心定义的线性方程组，因此与基于代码递归结构的其他用于解码RM代码的算法明显不同。可以将其视为Abbe等人结果的更明确证明。这显示了从纠正纠删到纠正错误的减少，并且与Pellikaan，Duursma和Kötter的错误定位对方法几乎没有相似之处，后者对Berlekamp-Welch算法进行了概括，用于解码Reed-Solomon码。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号