elib
DLR-Header
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 Sebastian Heesemann (2019) Fast Root Finding for Interpolation-Based Decoding of Interleaved Gabidulin Codes. 2019 IEEE Information Theory Workshop, Visby, Sweden.

[img] PDF - Registered users only
310kB

Abstract

We show that the root-finding step in interpolationbased 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^wM(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^3n^2), in some cases O(l^2n^2).

Item URL in elib:https://elib.dlr.de/131076/
Document Type:Conference or Workshop Item (Speech)
Title:Fast Root Finding for Interpolation-Based Decoding of Interleaved Gabidulin Codes
Authors:
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Bartz, HannesUNSPECIFIEDUNSPECIFIED
Jerkovits, ThomasUNSPECIFIEDUNSPECIFIED
Puchinger, SvenUNSPECIFIEDUNSPECIFIED
Rosenkilde, Johan Sebastian HeesemannUNSPECIFIEDUNSPECIFIED
Date:August 2019
Refereed publication:Yes
Open Access:No
Gold Open Access:No
In SCOPUS:No
In ISI Web of Science:No
Status:Published
Keywords:order bases, interpolation-based decoding, interleaved Gabidulin codes
Event Title:2019 IEEE Information Theory Workshop
Event Location:Visby, Sweden
Event Type:international Conference
Organizer:IEEE
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: Bartz, Hannes
Deposited On:04 Dec 2019 13:29
Last Modified:04 Dec 2019 13:29

Repository Staff Only: item control page

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