Fast decoding of Gabidulin codes

Antonia Wachter-Zeh, Valentin Afanassiev, Vladimir Sidorenko

Research output: Contribution to journalArticlepeer-review

29 Citations (SciVal)

Abstract

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
Volume66
Issue number1-3
DOIs
Publication statusPublished - Jan 2013
Externally publishedYes

Keywords

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

Fingerprint

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

Cite this