A Hensel Lifting to Replace Factorization in List-Decoding of Algebraic-Geometric and Reed-Solomon Codes

Daniel Augot 1 Lancelot Pecquet 1
1 CODES - Coding and cryptography
Inria Paris-Rocquencourt
Abstract : This paper presents an algorithmic improvement to Sudan's list-decoding algorithm for Reed-Solomon codes and its generalization to algebraic-geometric codes from Shokrollahi and Wasserman. Instead of completely factoring the interpolation polynomial over the function field of the curve, we compute sufficiently many coefficients of a Hensel development to reconstruct the functions that correspond to codewords. We prove that these Hensel developments can be found efficiently using Newton's method. We also describe the algorithm in the special case of Reed-Solomon codes.
Type de document :
Article dans une revue
Information Theory, IEEE Transactions on, IEEE Signal Processing Society, 2000, 46 (7), pp.2605 - 2614. 〈http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=887868〉. 〈10.1109/18.887868〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00509339
Contributeur : Daniel Augot <>
Soumis le : mercredi 11 août 2010 - 17:30:41
Dernière modification le : vendredi 25 mai 2018 - 12:02:03
Document(s) archivé(s) le : jeudi 1 décembre 2016 - 18:45:40

Fichiers

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

Identifiants

Collections

Citation

Daniel Augot, Lancelot Pecquet. A Hensel Lifting to Replace Factorization in List-Decoding of Algebraic-Geometric and Reed-Solomon Codes. Information Theory, IEEE Transactions on, IEEE Signal Processing Society, 2000, 46 (7), pp.2605 - 2614. 〈http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=887868〉. 〈10.1109/18.887868〉. 〈inria-00509339〉

Partager

Métriques

Consultations de la notice

253

Téléchargements de fichiers

178