An Interpolation Procedure for List Decoding Reed--Solomon codes Based on Generalized Key Equations

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 $\listl$, our algorithm has time complexity \ON{\listl s^4n^2}.
Type de document :
Article dans une revue
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2011, 57, pp.5946-5959. 〈10.1109/TIT.2011.2162160〉
Liste complète des métadonnées

Littérature citée [32 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00633205
Contributeur : Daniel Augot <>
Soumis le : lundi 17 octobre 2011 - 21:32:23
Dernière modification le : mercredi 28 novembre 2018 - 15:36:02
Document(s) archivé(s) le : jeudi 15 novembre 2012 - 09:51:23

Fichiers

BlockHankel_hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Alexander Zeh, Christian Gentner, Daniel Augot. An Interpolation Procedure for List Decoding Reed--Solomon codes Based on Generalized Key Equations. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2011, 57, pp.5946-5959. 〈10.1109/TIT.2011.2162160〉. 〈inria-00633205〉

Partager

Métriques

Consultations de la notice

383

Téléchargements de fichiers

154