Row Reduction Applied to Decoding of Rank Metric and Subspace Codes

Sven  Puchinger; Johan Sebastian Rosenkilde 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 Sebastian Rosenkilde Nielsen, Wenhui Li, Vladimir Sidorenko

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

430 Downloads (Pure)

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.

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

Keywords

Skew Polynomials
Row Reduction
Module Minimisation
Gabidulin Codes
Shift Register Synthesis
Mahdavifar–Vardy Codes

Access to Document

10.1007/s10623-016-0257-9

2016 dcc skew moduleAccepted author manuscript, 701 KB

OpenUrl availability

Full text

Cite this

@article{053b054809c947b381d799d081b518e7,

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 = "Skew Polynomials, Row Reduction, Module Minimisation, Gabidulin Codes, Shift Register Synthesis, Mahdavifar–Vardy Codes",

author = "Sven Puchinger and Nielsen, {Johan Sebastian Rosenkilde} and Wenhui Li and Vladimir Sidorenko",

year = "2017",

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

language = "English",

volume = "82",

pages = "389–409",

journal = "Designs, Codes and Cryptography",

issn = "0925-1022",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Row Reduction Applied to Decoding of Rank Metric and Subspace Codes

AU - Puchinger, Sven

AU - Nielsen, Johan Sebastian Rosenkilde

AU - Li, Wenhui

AU - Sidorenko, Vladimir

PY - 2017

Y1 - 2017

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 - Skew Polynomials

KW - Row Reduction

KW - Module Minimisation

KW - Gabidulin Codes

KW - Shift Register Synthesis

KW - Mahdavifar–Vardy Codes

U2 - 10.1007/s10623-016-0257-9

DO - 10.1007/s10623-016-0257-9

M3 - Journal article

SN - 0925-1022

VL - 82

SP - 389

EP - 409

JO - Designs, Codes and Cryptography

JF - Designs, Codes and Cryptography

IS - 1

ER -

Row Reduction Applied to Decoding of Rank Metric and Subspace Codes

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this