Zeh, Alexander und Gentner, Christian und Augot, Daniel (2011) An Interpolation Procedure for List Decoding Reed–Solomon Codes Based on Generalized Key Equations. IEEE Transactions on Information Theory, 57 (9), Seiten 5946-5959. IEEE - Institute of Electrical and Electronics Engineers. ISSN 0018-9448.
![]() |
PDF
441kB |
Kurzfassung
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).
elib-URL des Eintrags: | https://elib.dlr.de/72163/ | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Dokumentart: | Zeitschriftenbeitrag | ||||||||||||||||
Titel: | An Interpolation Procedure for List Decoding Reed–Solomon Codes Based on Generalized Key Equations | ||||||||||||||||
Autoren: |
| ||||||||||||||||
Datum: | September 2011 | ||||||||||||||||
Erschienen in: | IEEE Transactions on Information Theory | ||||||||||||||||
Referierte Publikation: | Ja | ||||||||||||||||
Open Access: | Ja | ||||||||||||||||
Gold Open Access: | Nein | ||||||||||||||||
In SCOPUS: | Ja | ||||||||||||||||
In ISI Web of Science: | Ja | ||||||||||||||||
Band: | 57 | ||||||||||||||||
Seitenbereich: | Seiten 5946-5959 | ||||||||||||||||
Verlag: | IEEE - Institute of Electrical and Electronics Engineers | ||||||||||||||||
ISSN: | 0018-9448 | ||||||||||||||||
Status: | veröffentlicht | ||||||||||||||||
Stichwörter: | Block-Hankel matrix , Guruswami–Sudan interpolation , Reed–Solomon codes , fundamental iterative algorithm (FIA) , key equation , list decoding | ||||||||||||||||
HGF - Forschungsbereich: | Verkehr und Weltraum (alt) | ||||||||||||||||
HGF - Programm: | Weltraum (alt) | ||||||||||||||||
HGF - Programmthema: | W KN - Kommunikation/Navigation | ||||||||||||||||
DLR - Schwerpunkt: | Weltraum | ||||||||||||||||
DLR - Forschungsgebiet: | W KN - Kommunikation/Navigation | ||||||||||||||||
DLR - Teilgebiet (Projekt, Vorhaben): | W - Vorhaben GNSS2/Neue Dienste und Produkte (alt) | ||||||||||||||||
Standort: | Oberpfaffenhofen | ||||||||||||||||
Institute & Einrichtungen: | Institut für Kommunikation und Navigation > Nachrichtensysteme | ||||||||||||||||
Hinterlegt von: | Gentner, Dr. Christian | ||||||||||||||||
Hinterlegt am: | 06 Dez 2011 08:48 | ||||||||||||||||
Letzte Änderung: | 31 Jul 2019 19:33 |
Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags