DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Fast decoding of codes in the rank, subspace, and sum-rank metric

Bartz, Hannes and Jerkovits, Thomas and Puchinger, Sven and Rosenkilde, Johan (2021) Fast decoding of codes in the rank, subspace, and sum-rank metric. IEEE Transactions on Information Theory. IEEE - Institute of Electrical and Electronics Engineers. doi: 10.1109/TIT.2021.3067318. ISSN 0018-9448.

[img] PDF - Published version


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.

Item URL in elib:https://elib.dlr.de/141913/
Document Type:Article
Title:Fast decoding of codes in the rank, subspace, and sum-rank metric
AuthorsInstitution or Email of AuthorsAuthor's ORCID iDORCID Put Code
Jerkovits, ThomasUNSPECIFIEDhttps://orcid.org/0000-0002-7538-7639UNSPECIFIED
Rosenkilde, JohanUNSPECIFIEDhttps://orcid.org/0000-0002-3540-0456UNSPECIFIED
Date:19 March 2021
Journal or Publication Title:IEEE Transactions on Information Theory
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In ISI Web of Science:Yes
Publisher:IEEE - Institute of Electrical and Electronics Engineers
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
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Communication, Navigation, Quantum Technology
DLR - Research area:Raumfahrt
DLR - Program:R KNQ - Communication, Navigation, Quantum Technology
DLR - Research theme (Project):R - Project Cybersecurity for Autonomous and Networked Systems [KNQ]
Location: Oberpfaffenhofen
Institutes and Institutions:Institute of Communication and Navigation > Satellite Networks
Deposited By: Jerkovits, Thomas
Deposited On:23 Apr 2021 15:50
Last Modified:23 Apr 2021 15:50

Repository Staff Only: item control page

Help & Contact
electronic library is running on EPrints 3.3.12
Website and database design: Copyright © German Aerospace Center (DLR). All rights reserved.