Fast decoding of Gabidulin codes

Antonia Wachter-Zeh; Valentin Afanassiev; Vladimir Sidorenko

doi:10.1007/s10623-012-9659-5

Fast decoding of Gabidulin codes

Antonia Wachter-Zeh
, Valentin Afanassiev
, Vladimir Sidorenko

University of Ulm
Institut de Recherche Mathématique de Rennes
Institute for Information Transmission Problems of the Russian Academy of Sciences

Research output: Contribution to journal › Article › peer-review

33 Scopus citations

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 F_qm 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 ³ log m) operations over the ground field F_qm.

Original language	English
Pages (from-to)	57-73
Number of pages	17
Journal	Designs, Codes, and Cryptography
Volume	66
Issue number	1-3
DOIs	https://doi.org/10.1007/s10623-012-9659-5
State	Published - Jan 2013
Externally published	Yes

Keywords

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

Access to Document

10.1007/s10623-012-9659-5

Cite this

@article{dac1bec2d6c34afe9cbb631ce6b8067e,

title = "Fast decoding of Gabidulin codes",

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.",

keywords = "Fast decoding, Fast symbolic division, Fast symbolic product, Gabidulin codes, Linearized polynomials, Rank metric",

author = "Antonia Wachter-Zeh and Valentin Afanassiev and Vladimir Sidorenko",

note = "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.",

year = "2013",

month = jan,

doi = "10.1007/s10623-012-9659-5",

language = "English",

volume = "66",

pages = "57--73",

journal = "Designs, Codes, and Cryptography",

issn = "0925-1022",

publisher = "Springer Netherlands",

number = "1-3",

}

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 - https://www.scopus.com/pages/publications/84872396538

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 -

Fast decoding of Gabidulin codes

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this