elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Impressum | Datenschutz | Kontakt | English
Schriftgröße: [-] Text [+]

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

Bartz, Hannes und Jerkovits, Thomas und Puchinger, Sven und Rosenkilde, Johan Sebastian Heesemann (2019) Fast Root Finding for Interpolation-Based Decoding of Interleaved Gabidulin Codes. In: 2019 IEEE Information Theory Workshop, ITW 2019. 2019 IEEE Information Theory Workshop, Visby, Sweden. doi: 10.1109/ITW44776.2019.8989290. ISBN 978-153866900-6.

[img] PDF - Nur DLR-intern zugänglich
310kB

Kurzfassung

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).

elib-URL des Eintrags:https://elib.dlr.de/131076/
Dokumentart:Konferenzbeitrag (Vortrag)
Titel:Fast Root Finding for Interpolation-Based Decoding of Interleaved Gabidulin Codes
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Bartz, HannesNICHT SPEZIFIZIERTNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Jerkovits, ThomasNICHT SPEZIFIZIERTNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Puchinger, SvenNICHT SPEZIFIZIERTNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Rosenkilde, Johan Sebastian HeesemannNICHT SPEZIFIZIERTNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Datum:August 2019
Erschienen in:2019 IEEE Information Theory Workshop, ITW 2019
Referierte Publikation:Ja
Open Access:Nein
Gold Open Access:Nein
In SCOPUS:Ja
In ISI Web of Science:Nein
DOI:10.1109/ITW44776.2019.8989290
ISBN:978-153866900-6
Status:veröffentlicht
Stichwörter:order bases, interpolation-based decoding, interleaved Gabidulin codes
Veranstaltungstitel:2019 IEEE Information Theory Workshop
Veranstaltungsort:Visby, Sweden
Veranstaltungsart:internationale Konferenz
Veranstalter :IEEE
HGF - Forschungsbereich:Luftfahrt, Raumfahrt und Verkehr
HGF - Programm:Raumfahrt
HGF - Programmthema:Kommunikation und Navigation
DLR - Schwerpunkt:Raumfahrt
DLR - Forschungsgebiet:R KN - Kommunikation und Navigation
DLR - Teilgebiet (Projekt, Vorhaben):R - Vorhaben Multimedia Satellitennetze (alt)
Standort: Oberpfaffenhofen
Institute & Einrichtungen:Institut für Kommunikation und Navigation > Satellitennetze
Hinterlegt von: Bartz, Hannes
Hinterlegt am:04 Dez 2019 13:29
Letzte Änderung:21 Jul 2023 09:11

Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags

Blättern
Suchen
Hilfe & Kontakt
Informationen
electronic library verwendet EPrints 3.3.12
Gestaltung Webseite und Datenbank: Copyright © Deutsches Zentrum für Luft- und Raumfahrt (DLR). Alle Rechte vorbehalten.