Some Gabidulin Codes cannot be List Decoded Efficiently at any Radius

Preprint
Publisher Website
Google Scholar
  • 18 January 2015
Abstract
Gabidulin codes can be seen as the rank-metric equivalent of Reed-Solomon codes. It was recently proven, using subspace polynomials, that Gabidulin codes cannot be list decoded beyond the so-called Johnson radius. In another result, cyclic subspace codes were constructed by inspecting the connection between subspaces and their subspace polynomials. In this paper, these subspace codes are used to prove two bounds on the minimum possible size of a list in decoding certain Gabidulin codes. The first bound is an existential one, showing that exponentially-sized lists exist for codes with specific parameters. The second bound presents exponentially-sized lists explicitly, for a different set of parameters. Both bounds rule out the possibility of efficiently list decoding their respective families of codes for any radius beyond half the minimum distance. Such a result was known so far only for non-linear rank-metric codes, and not for Gabidulin codes.

This publication has 0 references indexed in Scilit: