Algebraic decoding of folded Gabidulin codes

详细信息    查看全文

• 作者：Hannes Bartz ; Vladimir Sidorenko
• 关键词：Rank ; metric codes ; Folded Gabidulin codes ; Probabilistic unique decoding ; Interpolation ; based decoding
• 刊名：Designs, Codes and Cryptography
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：82
• 期：1-2
• 页码：449-467
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Coding and Information Theory; Data Structures, Cryptology and Information Theory; Data Encryption; Discrete Mathematics in Computer Science; Information and Communication, Circuits;
• 出版者：Springer US
• ISSN：1573-7586
• 卷排序：82

文摘

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\le R\le 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 \(\mathcal {O}({s^2n^2})\) operations in \(\mathbb {F}_{q^m}\), where \(1\le s\le h\) is a decoding parameter and \(n\le m\) is the length of the unfolded code over \(\mathbb {F}_{q^m}\). 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.