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

On Decoding Complexity of Reed-Solomon Codes on the Packet Erasure Channel

Garrammone, Giuliano (2013) On Decoding Complexity of Reed-Solomon Codes on the Packet Erasure Channel. IEEE Communications Letters, 17 (4), pp. 773-776. IEEE - Institute of Electrical and Electronics Engineers. DOI: 10.1109/LCOMM.2013.021913.122427 ISSN 1089-7798

Full text not available from this repository.


We study the finite-length complexity of the Berlekamp-Massey algorithm (BM) and of the Gaussian elimination algorithm (GE) for decoding a Reed-Solomon (RS) code of length n on the packet erasure channel (PEC). In particular, we are interested in the dependency of the complexity on the packet size g. We show that, for large packet sizes, the complexity of both algorithms is O(g) and the constants hidden by the O-notation are comparable. As an example, we consider a RS code from the Digital Video Broadcasting - Handhelds (DVB-H) standard and we show that, although the asymptotic complexity of the GE is O(n^3) and the one of the BM is O(n^2), the finite-length complexity of both algorithms is comparable already for small/moderate packet sizes, in particular for all packet sizes considered within the standard, making the GE not inferior to the BM, in this context.

Item URL in elib:https://elib.dlr.de/82398/
Document Type:Article
Title:On Decoding Complexity of Reed-Solomon Codes on the Packet Erasure Channel
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Date:April 2013
Journal or Publication Title:IEEE Communications Letters
Refereed publication:Yes
Open Access:No
Gold Open Access:No
In ISI Web of Science:Yes
DOI :10.1109/LCOMM.2013.021913.122427
Page Range:pp. 773-776
Publisher:IEEE - Institute of Electrical and Electronics Engineers
Keywords:Reed-Solomon codes, Gaussian elimination algorithm, Berlekamp-Massey algorithm, packet erasure channel.
HGF - Research field:Aeronautics, Space and Transport (old)
HGF - Program:Space (old)
HGF - Program Themes:W KN - Kommunikation/Navigation
DLR - Research area:Space
DLR - Program:W KN - Kommunikation/Navigation
DLR - Research theme (Project):W - Vorhaben Multimedia Satellitennetze (old)
Location: Oberpfaffenhofen
Institutes and Institutions:Institute of Communication and Navigation > Satellite Networks
Deposited By: Garrammone, Giuliano
Deposited On:03 Jun 2013 10:56
Last Modified:06 Sep 2019 15:26

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.