Algebraic decoding of folded Gabidulin codes

作者：Bartz Hannes^*; Sidorenko Vladimir

来源：Designs, Codes and Cryptography, 2017, 82(1-2): 449-467.

DOI：10.1007/s10623-016-0195-6

• Rank-metric codes
• Folded Gabidulin codes
• Probabilistic unique decoding
• Interpolation-based decoding

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 . 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 operations in , where is a decoding parameter and is the length of the unfolded code over . 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.

• 出版日期2017-1