Decoding Interleaved Gabidulin Codes using Alekhnovich's Algorithm

Sven Puchinger, Sven Müelich, David Mödinger, Johan Sebastian Heesemann Rosenkilde, Martin Bossert

Research output: Contribution to journalJournal articleResearchpeer-review

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.
Original languageEnglish
JournalElectronic Notes in Discrete Mathematics
Volume57
Pages (from-to)175–180
ISSN1571-0653
DOIs
Publication statusPublished - 2017

Keywords

  • Gabidulin Codes
  • Characteristic Zero
  • Low-Rank Matrix Recovery

Cite this