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

Fast Root Finding for Interpolation-Based Decoding of Interleaved Gabidulin Codes

Bartz, Hannes and Jerkovits, Thomas and Puchinger, Sven and Rosenkilde, Johan (2019) Fast Root Finding for Interpolation-Based Decoding of Interleaved Gabidulin Codes. The IEEE Information Theory Workshop 2019, 25.-28. Aug. 2019, Gotland, Schweden.

[img] PDF


We show that the root-finding step in interpolation-based decoding of interleaved Gabidulin codes can be solved by finding a so-called minimal approximant basis of a matrix over a linearized polynomial ring. Based on existing fast algorithms for computing such bases over ordinary polynomial rings, we develop fast algorithms for computing them over linearized polynomials. As a result, root finding costs O~(l^w * M(n)) operations in Fqm, where l is the interleaving degree, n the code length, Fqm the base field of the code, 2<=w<=3 the matrix multiplication exponent, and M(n) in O(n^1.635) is the complexity of multiplying two linearized polynomials of degree at most n. This is an asymptotic improvement upon the previously fastest algorithm of complexity O(l^3*n^2), in some cases O(l^2*n^2)

Item URL in elib:https://elib.dlr.de/131880/
Document Type:Conference or Workshop Item (Speech)
Title:Fast Root Finding for Interpolation-Based Decoding of Interleaved Gabidulin Codes
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Bartz, Hanneshannes.bartz (at) dlr.dehttps://orcid.org/0000-0001-7767-1513
Jerkovits, ThomasThomas.Jerkovits (at) dlr.dehttps://orcid.org/0000-0002-7538-7639
Puchinger, Svensvepu (at) dtu.dkUNSPECIFIED
Rosenkilde, Johanjsrn (at) dtu.dkhttps://orcid.org/0000-0002-3540-0456
Date:14 April 2019
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In ISI Web of Science:No
Keywords:—Interleaved Gabidulin Codes, InterpolationBased Decoding, Order Bases, Rank-Metric Codes, Root Finding
Event Title:The IEEE Information Theory Workshop 2019
Event Location:Gotland, Schweden
Event Type:international Conference
Event Dates:25.-28. Aug. 2019
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Communication and Navigation
DLR - Research area:Raumfahrt
DLR - Program:R KN - Kommunikation und Navigation
DLR - Research theme (Project):R - Vorhaben Multimedia Satellitennetze
Location: Oberpfaffenhofen
Institutes and Institutions:Institute of Communication and Navigation > Satellite Networks
Deposited By: Jerkovits, Thomas
Deposited On:04 Dec 2019 13:22
Last Modified:04 Dec 2019 13:22

Repository Staff Only: item control page

Help & Contact
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.