Fast decoding of Gabidulin codes

Antonia Wachter-Zeh, Valentin Afanassiev, Vladimir Sidorenko

Research output: Contribution to journalArticlepeer-review

29 Citations (SciVal)


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.

Original languageEnglish
Pages (from-to)57-73
Number of pages17
JournalDesigns, Codes, and Cryptography
Issue number1-3
Publication statusPublished - Jan 2013
Externally publishedYes


  • Fast decoding
  • Fast symbolic division
  • Fast symbolic product
  • Gabidulin codes
  • Linearized polynomials
  • Rank metric


Dive into the research topics of 'Fast decoding of Gabidulin codes'. Together they form a unique fingerprint.

Cite this