Bounds on polynomial-time list decoding of rank metric codes
Antonia Wachter-Zeh · 2013
This contribution provides bounds on the list size of rank metric codes in order to understand whether polynomial-time list decoding is possible or not. First, an exponential upper bound is derived, which holds for any rank metric code of length n and minimum rank distance d. Second, a lower bound proves that there exists a rank metric code over Fqm of length n ≤ m such that the list size is exponential in the length of the code for any radius greater than half the minimum distance. This implies that in rank metric there cannot exist a polynomial upper bound depending only on n and d as the Johnson bound for Hamming metric. These bounds reveal significant differences between codes in Hamming and rank metric.