Algebraic decoding of folded Gabidulin codes

An efficient interpolation-based decoding algorithm for h-folded Gabidulin codes is presented that can correct rank errors beyond half the minimum rank distance for any code rate 0 ≤ R≤ 1. The algorithm serves as a list decoder or as a probabilistic unique decoder and improves upon existing schemes, especially for high code rates. A probabilistic unique decoder with adjustable decoding radius is presented. The decoder outputs a unique solution with high probability and requires at most O(s²n²) operations in Fqm, where 1 ≤ s≤ h is a decoding parameter and n≤ m is the length of the unfolded code over Fqm. An upper bound on the average list size of folded Gabidulin codes and on the decoding failure probability of the decoder is given. Applying the ideas to a list decoding algorithm by Mahdavifar and Vardy (List-decoding of subspace codes and rank-metric codes up to Singleton bound, ISIT 2012) improves the performance when used as probabilistic unique decoder and gives an upper bound on the failure probability.