Efficient Decoding of Gabidulin Codes over Galois Rings

Sven Puchinger; Julian Renner; Antonia Wachter-Zeh; Jens Zumbrage

doi:10.1109/ISIT45174.2021.9517904

Efficient Decoding of Gabidulin Codes over Galois Rings

Sven Puchinger
, Julian Renner
, Antonia Wachter-Zeh
, Jens Zumbrage

University of Passau
Technical University of Munich

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

136 Downloads (Orbit)

Abstract

This paper presents the first decoding algorithm for Gabidulin codes over Galois rings with provable quadratic complexity in the code length. The new method consists of two steps: (1) solving a syndrome-based key equation to obtain the annihilator polynomial of the error and therefore the column space of the error, (2) solving a key equation based on the received word in order to reconstruct the error vector. This two-step approach became necessary since standard solutions as the Euclidean algorithm do not properly work over rings.

Original language	English
Title of host publication	Proceedings of 2021 IEEE International Symposium on Information Theory
Publisher	IEEE
Publication date	2021
Pages	25-30
ISBN (Print)	978-1-5386-8210-4
DOIs	https://doi.org/10.1109/ISIT45174.2021.9517904
Publication status	Published - 2021
Event	2021 IEEE International Symposium on Information Theory - Virtual event, Melbourne, Australia Duration: 12 Jul 2021 → 20 Jul 2021

Conference

Conference	2021 IEEE International Symposium on Information Theory
Location	Virtual event
Country/Territory	Australia
City	Melbourne
Period	12/07/2021 → 20/07/2021

Access to Document

10.1109/ISIT45174.2021.9517904

FulltextAccepted author manuscript, 178 KB

OpenUrl availability

Check availability in DTU Findit

Cite this

@inproceedings{08ba721d2a324e8680769bf925302b76,

title = "Efficient Decoding of Gabidulin Codes over Galois Rings",

abstract = "This paper presents the first decoding algorithm for Gabidulin codes over Galois rings with provable quadratic complexity in the code length. The new method consists of two steps: (1) solving a syndrome-based key equation to obtain the annihilator polynomial of the error and therefore the column space of the error, (2) solving a key equation based on the received word in order to reconstruct the error vector. This two-step approach became necessary since standard solutions as the Euclidean algorithm do not properly work over rings.",

author = "Sven Puchinger and Julian Renner and Antonia Wachter-Zeh and Jens Zumbrage",

year = "2021",

doi = "10.1109/ISIT45174.2021.9517904",

language = "English",

isbn = "978-1-5386-8210-4",

pages = "25--30",

booktitle = "Proceedings of 2021 IEEE International Symposium on Information Theory",

publisher = "IEEE",

address = "United States",

note = "2021 IEEE International Symposium on Information Theory, ISIT 2021 ; Conference date: 12-07-2021 Through 20-07-2021",

}

TY - GEN

T1 - Efficient Decoding of Gabidulin Codes over Galois Rings

AU - Puchinger, Sven

AU - Renner, Julian

AU - Wachter-Zeh, Antonia

AU - Zumbrage, Jens

PY - 2021

Y1 - 2021

N2 - This paper presents the first decoding algorithm for Gabidulin codes over Galois rings with provable quadratic complexity in the code length. The new method consists of two steps: (1) solving a syndrome-based key equation to obtain the annihilator polynomial of the error and therefore the column space of the error, (2) solving a key equation based on the received word in order to reconstruct the error vector. This two-step approach became necessary since standard solutions as the Euclidean algorithm do not properly work over rings.

AB - This paper presents the first decoding algorithm for Gabidulin codes over Galois rings with provable quadratic complexity in the code length. The new method consists of two steps: (1) solving a syndrome-based key equation to obtain the annihilator polynomial of the error and therefore the column space of the error, (2) solving a key equation based on the received word in order to reconstruct the error vector. This two-step approach became necessary since standard solutions as the Euclidean algorithm do not properly work over rings.

U2 - 10.1109/ISIT45174.2021.9517904

DO - 10.1109/ISIT45174.2021.9517904

M3 - Article in proceedings

SN - 978-1-5386-8210-4

SP - 25

EP - 30

BT - Proceedings of 2021 IEEE International Symposium on Information Theory

PB - IEEE

T2 - 2021 IEEE International Symposium on Information Theory

Y2 - 12 July 2021 through 20 July 2021

ER -

Efficient Decoding of Gabidulin Codes over Galois Rings

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this