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 journalJournal articleResearchpeer-review

260 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 languageEnglish
JournalDesigns, Codes and Cryptography
Volume82
Issue number1
Pages (from-to)389–409
Number of pages21
ISSN0925-1022
DOIs
Publication statusPublished - 2017

Keywords

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

Cite this