Bounds on List Decoding of Rank-Metric Codes
Bounds on List Decoding of Rank-Metric Codes
复制标题
DOI：
10.1109/tit.2013.2274653
复制
发表时间：
2013-01
影响因子：
2.5
通讯作者：
A. Wachter-Zeh
中科院分区：
文献类型：
--
作者：
A. Wachter-Zeh
到目前为止，还没有多项式时间的列表解码算法（超过一半的最小距离）的Gabidulin码。这些码可以被看作是秩度量等效的里德-所罗门码。在本文中，我们提供的秩度量码的列表大小的界限，以了解是否多项式时间列表解码是可能的，或者它是否只与指数时间复杂度。证明了列表大小的三个界限。第一个是Gabidulin码的指数下界，并表明这些代码没有多项式时间列表解码超过约翰逊半径存在。其次，导出了一个指数上界，它适用于任何长度为n和最小秩距离d的秩度量码。第三个界证明了在\BBFqm上存在一个长度为n ≤ m的秩度量码，使得对于任何大于最小秩距离一半的半径，列表的长度是指数的。这意味着不可能存在类似于Hamming度量中的约翰逊界那样只依赖于n和d的多项式上界。这三种秩度量界与汉明度量下的码界都有很大的不同。
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 \BBFqm of length n ≤ 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.