On List-Decodability of Random Rank Metric Codes and Subspace Codes

摘要

Codes in rank metric have a wide range of applications. To construct such codes with better list-decoding performance explicitly, it is of interest to investigate the list-decodability of random rank metric codes. It is shown that if is a constant, then for every rank metric code in with rate and list-decoding radius must obey the Gilbert–Varshamov bound, that is, . Otherwise, the list size can be exponential and hence no polynomial-time list decoding is possible. On the other hand, for arbitrary and , with and being independent of each other, with high probability, a random rank metric code with rate can be efficiently list-decoded up to a fraction of rank errors with constant list size . We establish similar results for constant-dimension subspace codes. Moreover, we show that, with high probability, the list-decoding radius of random -linear rank metric codes also achieve the Gilbert–Varshamov bound with constant list size .