• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >Erasure List-Decodable Codes From Random and Algebraic Geometry Codes
【24h】

Erasure List-Decodable Codes From Random and Algebraic Geometry Codes

机译：来自随机和代数几何代码的擦除列表可分解代码

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

摘要

Erasure list decoding was introduced to correct a larger number of erasures by outputting a list of possible candidates. In this paper, we consider both random linear codes and algebraic geometry codes for list decoding from erasures. The contributions of this paper are twofold. First, for arbitrary (00) ( (R) and (epsilon ) are independent), we show that with high probability a (q) -ary random linear code of rate (R) is an erasure list-decodable code with constant list size (q^{O(1/epsilon )}) that can correct a fraction (1-R-epsilon ) of erasures, i.e., a random linear code achieves the information-theoretic optimal tradeoff between information rate and fraction of erasures. Second, we show that algebraic geometry codes are good erasure list-decodable codes. Precisely speaking, a (q) -ary algebraic geometry code of rate (R) from the Garcia-Stichtenoth tower can correct (1-R-({1}/{sqrt {q}-1})+({1}/{q})-epsilon ) fraction of erasures with list size (O(1/epsilon )) . This improves the Johnson bound for erasures applied to algebraic geometry codes. Furthermore, list de- oding of these algebraic geometry codes can be implemented in polynomial time. Note that the code alphabet size (q) in this paper is constant and independent of (epsilon ) .
机译：引入了擦除列表解码，以通过输出可能的候选列表来校正更多的擦除。在本文中，我们将随机线性代码和代数几何代码同时考虑用于从擦除中进行列表解码。本文的贡献是双重的。首先，对于任意（0 0）（（R）和（epsilon）是独立的），我们证明了率（R）的（q）-ary随机线性码的概率很高具有恒定列表大小（q ^ {O（1 / epsilon）}）的擦除列表可解码代码，它可以校正擦除的分数（1-R-epsilon），即，随机线性代码实现了信息论的最佳折衷信息率和擦除比例之间的关系。其次，我们证明代数几何代码是好的擦除列表可解码代码。准确地说，来自Garcia-Stichtenoth塔的速率（R）的（q）个代数几何代码可以校正（1-R-（{1} / {sqrt {q} -1}）+（{1} / {q}）-ε）擦除大小与列表大小（O（1 / epsilon））的比例。这改善了应用于代数几何代码的擦除的约翰逊边界。此外，这些代数几何代码的列表编码可以在多项式时间内实现。请注意，本文中的代码字母大小（q）是恒定的，并且与（epsilon）无关。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号