Row reduction applied to decoding of rank-metric and subspace codes

Sven Puchinger; Johan Rosenkilde né Nielsen; Wenhui Li; Vladimir Sidorenko

doi:10.1007/s10623-016-0257-9

Row reduction applied to decoding of rank-metric and subspace codes

Sven Puchinger, Johan Rosenkilde né Nielsen, Wenhui Li, Vladimir Sidorenko

Chair of Communications Engineering

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

15 Scopus citations

Abstract

We show that decoding of ℓ-Interleaved Gabidulin codes, as well as list-ℓ decoding of Mahdavifar–Vardy (MV) codes can be performed by row reducing skew polynomial matrices. Inspired by row reduction of F[ x] matrices, we develop a general and flexible approach of transforming matrices over skew polynomial rings into a certain reduced form. We apply this to solve generalised shift register problems over skew polynomial rings which occur in decoding ℓ-Interleaved Gabidulin codes. We obtain an algorithm with complexity O(ℓμ²) where μ measures the size of the input problem and is proportional to the code length n in the case of decoding. Further, we show how to perform the interpolation step of list-ℓ-decoding MV codes in complexity O(ℓn²) , where n is the number of interpolation constraints.

Original language	English
Pages (from-to)	389-409
Number of pages	21
Journal	Designs, Codes, and Cryptography
Volume	82
Issue number	1-2
DOIs	https://doi.org/10.1007/s10623-016-0257-9
State	Published - 1 Jan 2017

Keywords

Gabidulin codes
Mahdavifar–Vardy codes
Module minimisation
Row reduction
Shift register synthesis
Skew polynomials

Access to Document

10.1007/s10623-016-0257-9

Cite this

@article{b0e5ad7e2f144b559987299ef4390ab5,

title = "Row reduction applied to decoding of rank-metric and subspace codes",

abstract = "We show that decoding of ℓ-Interleaved Gabidulin codes, as well as list-ℓ decoding of Mahdavifar–Vardy (MV) codes can be performed by row reducing skew polynomial matrices. Inspired by row reduction of F[ x] matrices, we develop a general and flexible approach of transforming matrices over skew polynomial rings into a certain reduced form. We apply this to solve generalised shift register problems over skew polynomial rings which occur in decoding ℓ-Interleaved Gabidulin codes. We obtain an algorithm with complexity O(ℓμ2) where μ measures the size of the input problem and is proportional to the code length n in the case of decoding. Further, we show how to perform the interpolation step of list-ℓ-decoding MV codes in complexity O(ℓn2) , where n is the number of interpolation constraints.",

keywords = "Gabidulin codes, Mahdavifar–Vardy codes, Module minimisation, Row reduction, Shift register synthesis, Skew polynomials",

author = "Sven Puchinger and {Rosenkilde n{\'e} Nielsen}, Johan and Wenhui Li and Vladimir Sidorenko",

note = "Publisher Copyright: {\textcopyright} 2016, Springer Science+Business Media New York.",

year = "2017",

month = jan,

day = "1",

doi = "10.1007/s10623-016-0257-9",

language = "English",

volume = "82",

pages = "389--409",

journal = "Designs, Codes, and Cryptography",

issn = "0925-1022",

publisher = "Springer Netherlands",

number = "1-2",

}

TY - JOUR

T1 - Row reduction applied to decoding of rank-metric and subspace codes

AU - Puchinger, Sven

AU - Rosenkilde né Nielsen, Johan

AU - Li, Wenhui

AU - Sidorenko, Vladimir

PY - 2017/1/1

Y1 - 2017/1/1

N2 - We show that decoding of ℓ-Interleaved Gabidulin codes, as well as list-ℓ decoding of Mahdavifar–Vardy (MV) codes can be performed by row reducing skew polynomial matrices. Inspired by row reduction of F[ x] matrices, we develop a general and flexible approach of transforming matrices over skew polynomial rings into a certain reduced form. We apply this to solve generalised shift register problems over skew polynomial rings which occur in decoding ℓ-Interleaved Gabidulin codes. We obtain an algorithm with complexity O(ℓμ2) where μ measures the size of the input problem and is proportional to the code length n in the case of decoding. Further, we show how to perform the interpolation step of list-ℓ-decoding MV codes in complexity O(ℓn2) , where n is the number of interpolation constraints.

AB - We show that decoding of ℓ-Interleaved Gabidulin codes, as well as list-ℓ decoding of Mahdavifar–Vardy (MV) codes can be performed by row reducing skew polynomial matrices. Inspired by row reduction of F[ x] matrices, we develop a general and flexible approach of transforming matrices over skew polynomial rings into a certain reduced form. We apply this to solve generalised shift register problems over skew polynomial rings which occur in decoding ℓ-Interleaved Gabidulin codes. We obtain an algorithm with complexity O(ℓμ2) where μ measures the size of the input problem and is proportional to the code length n in the case of decoding. Further, we show how to perform the interpolation step of list-ℓ-decoding MV codes in complexity O(ℓn2) , where n is the number of interpolation constraints.

KW - Gabidulin codes

KW - Mahdavifar–Vardy codes

KW - Module minimisation

KW - Row reduction

KW - Shift register synthesis

KW - Skew polynomials

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

U2 - 10.1007/s10623-016-0257-9

DO - 10.1007/s10623-016-0257-9

M3 - Article

AN - SCOPUS:84982816941

SN - 0925-1022

VL - 82

SP - 389

EP - 409

JO - Designs, Codes, and Cryptography

JF - Designs, Codes, and Cryptography

IS - 1-2

ER -

Row reduction applied to decoding of rank-metric and subspace codes

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this