• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Improvements on the Johnson bound for Reed-Solomon codes
【24h】

Improvements on the Johnson bound for Reed-Solomon codes

机译：Reed-Solomon码的Johnson界的改进

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

摘要

For Reed-Solomon codes with block length n and dimension k, the Johnson theorem states that for a Hamming ball of radius smaller than n - root n-k, there can be at most O(n(2)) codewords. It was not known whether for larger radius, the number of codewords is polynomial. The best known list decoding algorithm for Reed-Solomon codes due to Guruswami and Sudan [Venkatesan Guruswami, Madhu Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Transactions on Information Theory 45 (6) (1999) 1757-1767] is also known to work in polynomial time only within this radius. In this paper we prove that when k < alpha n for any constant 0 < alpha < 1, we can overcome the barrier of the Johnson bound for list decoding of Reed-Solomon codes (even if the field size is exponential). More specifically in such a case, we prove that for Hamming ball of radius n - root n-k + c (for any c > 0) there can be at most O(n (c 2 root alpha/(1-root alpha)2 +c+2)) number of codewords. For any constant c, we describe a polynomial time algorithm for enumerating all of them, thereby also improving on the Guruswami-Sudan algorithm. Although the improvement is modest. this provides evidence for the first time that the n - root nk bound is not sacrosanct for such a high rate. We apply our method to obtain sharper bounds on a list recovery problem introduced by Guruswami and Rudra [Venkatesan Guruswami, Atri Rudra, Limits to list decoding Reed-Solomon codes, IEEE Transactions on Information Theory 52 (8) (2006) 3642-3649] where they establish super-polynomial lower bounds on the output size when the list size exceeds inverted right perpendicular n/k inverted left perpendicular. We show that even for larger list sizes the problem can be solved in polynomial time for certain values of k.
机译：对于块长度为n，维数为k的Reed-Solomon码，约翰逊定理指出，对于半径小于n-根n-k的汉明球，最多可以有O（n（2））个码字。对于较大的半径，代码字的数目是否为多项式是未知的。由于Guruswami和Sudan而产生的最著名的Reed-Solomon码列表解码算法[Venkatesan Guruswami，Madhu Sudan，改进了Reed-Solomon码和代数几何码的解码。还已知IEEE Transactions on Information Theory 45（6）（1999）1757-1767]在多项式时间内仅在该半径内工作。在本文中，我们证明了当k 0），最多可以存在O（n（c 2根alpha /（1-根alpha）2+ c + 2））个码字。对于任何常数c，我们都描述了一个多项式时间算法来枚举所有参数，从而也改进了Guruswami-Sudan算法。尽管改进不大。这首次提供了证据，表明n-根nk边界对于如此高的比率不是神圣不可侵犯的。我们应用我们的方法来获得由Guruswami和Rudra提出的列表恢复问题的更清晰界限[Venkatesan Guruswami，Atri Rudra，限制解码Reed-Solomon码的列表，IEEE信息理论学报52（8）（2006）3642-3649]其中，当列表大小超过反向右垂直n / k反向左垂直时，它们会在输出大小上建立超多项式下限。我们表明，即使对于较大的列表大小，对于某些k值，也可以在多项式时间内解决问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号