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

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

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


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 languageEnglish
Pages (from-to)389-409
Number of pages21
JournalDesigns, Codes, and Cryptography
Issue number1-2
StatePublished - 1 Jan 2017


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


Dive into the research topics of 'Row reduction applied to decoding of rank-metric and subspace codes'. Together they form a unique fingerprint.

Cite this