List and Probabilistic Unique Decoding of High-Rate Folded Gabidulin Codes

Abstract : An efficient interpolation-based decoding algorithm for folded Gabidulin codes is presented that can correct rank errors beyond half the minimum rank distance for any code rate R ∈ [0, 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 de-coder outputs a unique solution with high probability and requires at most O(s^2 n^2) operations in Fqm , where s is a decoding parameter and n is the length of the unfolded code. An upper bound on the average list size and on the decoding failure probability of the decoder is given.