Decoding Interleaved Gabidulin Codes using Alekhnovich's Algorithm

Sven Puchinger; Sven Müelich; David Mödinger; Johan Rosenkilde né Nielsen; 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 Rosenkilde né Nielsen, Martin Bossert

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

5 Scopus citations

Abstract

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

Original language	English
Pages (from-to)	175-180
Number of pages	6
Journal	Electronic Notes in Discrete Mathematics
Volume	57
DOIs	https://doi.org/10.1016/j.endm.2017.02.029
State	Published - 1 Mar 2017
Externally published	Yes

Keywords

Characteristic Zero
Gabidulin Codes
Low-Rank Matrix Recovery

Access to Document

10.1016/j.endm.2017.02.029

Cite this

@article{87fe6dacd3e64a3fb376408961e8962e,

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 = "Characteristic Zero, Gabidulin Codes, Low-Rank Matrix Recovery",

author = "Sven Puchinger and Sven M{\"u}elich and David M{\"o}dinger and {Rosenkilde n{\'e} Nielsen}, Johan and Martin Bossert",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier B.V.",

year = "2017",

month = mar,

day = "1",

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 né Nielsen, Johan

AU - Bossert, Martin

PY - 2017/3/1

Y1 - 2017/3/1

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 - Characteristic Zero

KW - Gabidulin Codes

KW - Low-Rank Matrix Recovery

UR - http://www.scopus.com/inward/record.url?scp=85015443652&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2017.02.029

DO - 10.1016/j.endm.2017.02.029

M3 - Article

AN - SCOPUS:85015443652

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

Other files and links

Fingerprint

Cite this