• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Bounds on List Decoding of Rank-Metric Codes
【24h】

Bounds on List Decoding of Rank-Metric Codes

机译：等级度量代码列表解码的界限

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

摘要

So far, there is no polynomial-time list decoding algorithm (beyond half the minimum distance) for Gabidulin codes. These codes can be seen as the rank-metric equivalent of Reed–Solomon codes. In this paper, we provide bounds on the list size of rank-metric codes in order to understand whether polynomial-time list decoding is possible or whether it works only with exponential time complexity. Three bounds on the list size are proven. The first one is a lower exponential bound for Gabidulin codes and shows that for these codes no polynomial-time list decoding beyond the Johnson radius exists. Second, an exponential upper bound is derived, which holds for any rank-metric code of length $n$ and minimum rank distance $d$ . The third bound proves that there exists a rank-metric code over $BBF_{q^{m}}$ of length $nleq m$ such that the list size is exponential in the length for any radius greater than half the minimum rank distance. This implies that there cannot exist a polynomial upper bound depending only on $n$ and $d$ similar to the Johnson bound in Hamming metric. All three rank-metric bounds reveal significant differences to bounds for codes in Hamming metric.
机译：到目前为止，还没有针对Gabidulin码的多项式时间列表解码算法（超过最小距离的一半）。这些代码可以看作是里德-所罗门代码的等级量级等效。在本文中，我们为秩度量代码的列表大小提供了界限，以了解多项式时间列表解码是否可能或仅在指数时间复杂度下起作用。证明了列表大小的三个界限。第一个是Gabidulin码的指数下界，表明对于这些码，不存在超出Johnson半径的多项式时间列表解码。其次，导出指数上限，该指数上限适用于长度为$ n $且最小等级距离为$ d $的任何等级度量代码。第三个界限证明，在长度为$ nleq m $的$ BBF_ {q ^ {m}} $上存在一个排名度量代码，这样，对于任何大于最小排名距离一半的半径，列表大小在长度上都是指数的。这意味着不能存在仅取决于$ n $和$ d $的多项式上限，该上限类似于汉明度量中的Johnson界。所有这三个秩度量范围都揭示了汉明度量中代码范围的显着差异。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号