TY - JOUR
T1 - Fast decoding of Gabidulin codes
AU - Wachter-Zeh, Antonia
AU - Afanassiev, Valentin
AU - Sidorenko, Vladimir
N1 - Funding Information:
Acknowledgments This work was supported by the German Research Council “Deutsche Forschungsge-meinschaft” (DFG) under Grant No. Bo867/21-1. The authors thank the reviewers for their valuable comments and suggestions that helped to improve the presentation of the paper.
PY - 2013/1
Y1 - 2013/1
N2 - Gabidulin codes are the analogues of Reed-Solomon codes in rank metric and play an important role in various applications. In this contribution, a method for efficient decoding of Gabidulin codes up to their error correcting capability is shown. The new decoding algorithm for Gabidulin codes (defined over Fqm directly provides the evaluation polynomial of the transmitted codeword. This approach can be seen as a Gao-like algorithm and uses an equivalent of the Euclidean Algorithm. In order to achieve low complexity, a fast symbolic product and a fast symbolic division are presented. The complexity of the whole decoding algorithm for Gabidulin codes is O(m 3 log m) operations over the ground field Fqm.
AB - Gabidulin codes are the analogues of Reed-Solomon codes in rank metric and play an important role in various applications. In this contribution, a method for efficient decoding of Gabidulin codes up to their error correcting capability is shown. The new decoding algorithm for Gabidulin codes (defined over Fqm directly provides the evaluation polynomial of the transmitted codeword. This approach can be seen as a Gao-like algorithm and uses an equivalent of the Euclidean Algorithm. In order to achieve low complexity, a fast symbolic product and a fast symbolic division are presented. The complexity of the whole decoding algorithm for Gabidulin codes is O(m 3 log m) operations over the ground field Fqm.
KW - Fast decoding
KW - Fast symbolic division
KW - Fast symbolic product
KW - Gabidulin codes
KW - Linearized polynomials
KW - Rank metric
UR - http://www.scopus.com/inward/record.url?scp=84872396538&partnerID=8YFLogxK
U2 - 10.1007/s10623-012-9659-5
DO - 10.1007/s10623-012-9659-5
M3 - Article
AN - SCOPUS:84872396538
SN - 0925-1022
VL - 66
SP - 57
EP - 73
JO - Designs, Codes, and Cryptography
JF - Designs, Codes, and Cryptography
IS - 1-3
ER -