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

An Interpolation Procedure for List Decoding Reed–Solomon Codes Based on Generalized Key Equations

Zeh, Alexander and Gentner, Christian and Augot, Daniel (2011) An Interpolation Procedure for List Decoding Reed–Solomon Codes Based on Generalized Key Equations. IEEE Transactions on Information Theory, 57 (9), pp. 5946-5959. IEEE - Institute of Electrical and Electronics Engineers. ISSN 0018-9448.

[img] PDF
441kB

Abstract

The key step of syndrome-based decoding of Reed-Solomon codes up to half the minimum distance is to solve the so-called Key Equation. List decoding algorithms, capable of decoding beyond half the minimum distance, are based on interpolation and factorization of multivariate polynomials. This article provides a link between syndrome-based decoding approaches based on Key Equations and the interpolation-based list decoding algorithms of Guruswami and Sudan for Reed-Solomon codes. The original interpolation conditions of Guruswami and Sudan for Reed-Solomon codes are reformulated in terms of a set of Key Equations. These equations provide a structured homogeneous linear system of equations of Block-Hankel form, that can be solved by an adaption of the Fundamental Iterative Algorithm. For an (n,k) Reed-Solomon code, a multiplicity s and a list size l , our algorithm has time complexity O(ls4n2).

Item URL in elib:https://elib.dlr.de/72163/
Document Type:Article
Title:An Interpolation Procedure for List Decoding Reed–Solomon Codes Based on Generalized Key Equations
Authors:
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Zeh, Alexanderalexander.zeh (at) uni-ulm.deUNSPECIFIED
Gentner, Christianchristian.gentner (at) dlr.deUNSPECIFIED
Augot, Danieldaniel.augot (at) inriaUNSPECIFIED
Date:September 2011
Journal or Publication Title:IEEE Transactions on Information Theory
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In SCOPUS:Yes
In ISI Web of Science:Yes
Volume:57
Page Range:pp. 5946-5959
Publisher:IEEE - Institute of Electrical and Electronics Engineers
ISSN:0018-9448
Status:Published
Keywords:Block-Hankel matrix , Guruswami–Sudan interpolation , Reed–Solomon codes , fundamental iterative algorithm (FIA) , key equation , list decoding
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 GNSS2/Neue Dienste und Produkte (old)
Location: Oberpfaffenhofen
Institutes and Institutions:Institute of Communication and Navigation > Communications Systems
Deposited By: Gentner, Christian
Deposited On:06 Dec 2011 08:48
Last Modified:31 Jul 2019 19:33

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.