Decoding Interleaved Gabidulin Codes using Alekhnovich's Algorithm

Sven  Puchinger; Sven Müelich; David Mödinger; Johan Sebastian Heesemann Rosenkilde; Martin Bossert

doi:10.1016/j.endm.2017.02.029

Decoding Interleaved Gabidulin Codes using Alekhnovich's Algorithm

Sven Puchinger, Sven Müelich, David Mödinger, Johan Sebastian Heesemann Rosenkilde, Martin Bossert

Ulm University

Research output: Contribution to journal › Journal article › Research › peer-review

Abstract

We prove that Alekhnovich's algorithm can be used for row reduction of skew polynomial matrices. This yields an O(ℓ3n(ω+1)/2log⁡(n)) decoding algorithm for ℓ-Interleaved Gabidulin codes of length n, where ω is the matrix multiplication exponent.

Original language	English
Journal	Electronic Notes in Discrete Mathematics
Volume	57
Pages (from-to)	175–180
ISSN	1571-0653
DOIs	https://doi.org/10.1016/j.endm.2017.02.029
Publication status	Published - 2017

Keywords

Gabidulin Codes
Characteristic Zero
Low-Rank Matrix Recovery

Access to Document

10.1016/j.endm.2017.02.029

https://arxiv.org/pdf/1604.05899.pdfLicence: CC BY-NC-ND

OpenUrl availability

Full text

Cite this

@article{a8a97c5161ae4c98ac9a1defd47d78ff,

title = "Decoding Interleaved Gabidulin Codes using Alekhnovich's Algorithm",

abstract = "We prove that Alekhnovich's algorithm can be used for row reduction of skew polynomial matrices. This yields an O(ℓ3n(ω+1)/2log⁡(n)) decoding algorithm for ℓ-Interleaved Gabidulin codes of length n, where ω is the matrix multiplication exponent.",

keywords = "Gabidulin Codes, Characteristic Zero, Low-Rank Matrix Recovery",

author = "Sven Puchinger and Sven M{\"u}elich and David M{\"o}dinger and Rosenkilde, {Johan Sebastian Heesemann} and Martin Bossert",

year = "2017",

doi = "10.1016/j.endm.2017.02.029",

language = "English",

volume = "57",

pages = "175–180",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - Decoding Interleaved Gabidulin Codes using Alekhnovich's Algorithm

AU - Puchinger, Sven

AU - Müelich, Sven

AU - Mödinger, David

AU - Rosenkilde, Johan Sebastian Heesemann

AU - Bossert, Martin

PY - 2017

Y1 - 2017

N2 - We prove that Alekhnovich's algorithm can be used for row reduction of skew polynomial matrices. This yields an O(ℓ3n(ω+1)/2log⁡(n)) decoding algorithm for ℓ-Interleaved Gabidulin codes of length n, where ω is the matrix multiplication exponent.

AB - We prove that Alekhnovich's algorithm can be used for row reduction of skew polynomial matrices. This yields an O(ℓ3n(ω+1)/2log⁡(n)) decoding algorithm for ℓ-Interleaved Gabidulin codes of length n, where ω is the matrix multiplication exponent.

KW - Gabidulin Codes

KW - Characteristic Zero

KW - Low-Rank Matrix Recovery

U2 - 10.1016/j.endm.2017.02.029

DO - 10.1016/j.endm.2017.02.029

M3 - Journal article

SN - 1571-0653

VL - 57

SP - 175

EP - 180

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Decoding Interleaved Gabidulin Codes using Alekhnovich's Algorithm

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this