On the list decodability of rank-metric codes containing Gabidulin codes

03/12/2021
by   Paolo Santonastaso, et al.
0

Wachter-Zeh in [42], and later together with Raviv [31], proved that Gabidulin codes cannot be efficiently list decoded for any radius τ, providing that τ is large enough. Also, they proved that there are infinitely many choices of the parameters for which Gabidulin codes cannot be efficiently list decoded at all. Subsequently, in [41] these results have been extended to the family of generalized Gabidulin codes and to further family of MRD-codes. In this paper, we provide bounds on the list size of rank-metric codes containing generalized Gabidulin codes in order to determine whether or not a polynomial-time list decoding algorithm exists. We detect several families of rank-metric codes containing a generalized Gabidulin code as subcode which cannot be efficiently list decoded for any radius large enough and families of rank-metric codes which cannot be efficiently list decoded. These results suggest that rank-metric codes which are 𝔽_q^m-linear or that contains a (power of) generalized Gabidulin code cannot be efficiently list decoded for large values of the radius.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset