Fast Decoding of Codes in the Rank, Subspace, and Sum-Rank Metric

Hannes Bartz, Thomas Jerkovits, Sven Puchinger, Johan Rosenkilde

Research output: Contribution to journalJournal articleResearchpeer-review

119 Downloads (Pure)

Abstract

We speed up existing decoding algorithms for three code classes in different metrics: interleaved Gabidulin codes in the rank metric, lifted interleaved Gabidulin codes in the subspace metric, and linearized Reed–Solomon codes in the sum-rank metric. The speed-ups are achieved by new algorithms that reduce the cores of the underlying computational problems of the decoders to one common tool: computing left and right approximant bases of matrices over skew polynomial rings. To accomplish this, we describe a skew-analogue of the existing PM-Basis algorithm for matrices over ordinary polynomials. This captures the bulk of the work in multiplication of skew polynomials, and the complexity benefit comes from existing algorithms performing this faster than in classical quadratic complexity. The new algorithms for the various decoding-related computational problems are interesting in their own and have further applications, in particular parts of decoders of several other codes and foundational problems related to the remainder-evaluation of skew polynomials.
Original languageEnglish
JournalIEEE Transactions on Information Theory
Volume67
Issue number8
Pages (from-to)5026-5050
ISSN0018-9448
DOIs
Publication statusPublished - 2021

Keywords

  • Rank Metric
  • Subspace Metric
  • Sum-Rank Metric
  • Interleaved Gabidulin Codes
  • Lifted Interleaved Gabidulin Codes
  • Linearized Reed–Solomon Codes
  • Fast Decoding
  • (Minimal) Approximant Basis
  • Interpolation-Based Decoding

Fingerprint

Dive into the research topics of 'Fast Decoding of Codes in the Rank, Subspace, and Sum-Rank Metric'. Together they form a unique fingerprint.

Cite this