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

Efficient Decoding of Interleaved Subspace and Gabidulin Codes beyond their Unique Decoding Radius Using Gröbner Bases

Bartz, Hannes and Wachter-Zeh, Antonia (2018) Efficient Decoding of Interleaved Subspace and Gabidulin Codes beyond their Unique Decoding Radius Using Gröbner Bases. Advances in Mathematics of Communications, 12 (4). American Institute of Mathematical Sciences. DOI: 10.3934/amc.2018046 ISSN 1930-5346

Full text not available from this repository.


An interpolation-based decoding scheme for L-interleaved subspace codes is presented. The scheme can be used as a (not necessarily polynomial-time) list decoder as well as a polynomial-time probabilistic unique decoder. Both interpretations allow to decode interleaved subspace codes beyond half the minimum subspace distance. Both schemes can decode γ insertions and δ deletions up to γ + Lδ ≤ L(nt − k), where nt is the dimension of the transmitted subspace and k is the number of data symbols from the field Fqm. Further, a complementary decoding approach is presented which corrects γ insertions and δ deletions up to Lγ +δ ≤ L(nt −k). Both schemes use properties of minimal Gr¨obner bases for the interpolation module that allow predicting the worst-case list size right after the interpolation step. An efficient procedure for constructing the required minimal Gr¨obner basis using the general K¨otter interpolation is presented. A computationally- and memory-efficient root-finding algorithm for the probabilistic unique decoder is proposed. The overall complexity of the decoding algorithm is at most O(L2n2 r) operations in F qm where nr is the dimension of the received subspace and L is the interleaving order. The analysis as well as the efficient algorithms can also be applied for accelerating the decoding of interleaved Gabidulin codes.

Item URL in elib:https://elib.dlr.de/123884/
Document Type:Article
Title:Efficient Decoding of Interleaved Subspace and Gabidulin Codes beyond their Unique Decoding Radius Using Gröbner Bases
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Bartz, Hanneshannes.bartz (at) dlr.dehttps://orcid.org/0000-0001-7767-1513
Wachter-Zeh, Antoniaantonia.wachter-zeh (at) tum.deUNSPECIFIED
Date:November 2018
Journal or Publication Title:Advances in Mathematics of Communications
Refereed publication:Yes
Open Access:No
Gold Open Access:No
In ISI Web of Science:Yes
DOI :10.3934/amc.2018046
American Institute of Mathematical Sciences, American Institute of Mathematical SciencesUNSPECIFIED
Publisher:American Institute of Mathematical Sciences
Series Name:Advances in Mathematics of Communications
Keywords:Subspace Codes, Rank-metric Codes, Interleaved Gabidulin Codes, Probabilistic Unique Decoding, Interpolation-Based Decoding.
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Aeronautics
HGF - Program Themes:air traffic management and operations
DLR - Research area:Aeronautics
DLR - Program:L AO - Air Traffic Management and Operation
DLR - Research theme (Project):L - Communication, Navigation and Surveillance
Location: Oberpfaffenhofen
Institutes and Institutions:Institute of Communication and Navigation > Satellite Networks
Deposited By: Bartz, Hannes
Deposited On:28 Nov 2018 15:36
Last Modified:28 Nov 2018 15:36

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.