An Alternative to Factorization: a Speedup for SUDAN's Decoding Algorithm and its Generalization to Algebraic-Geometric Codes

Daniel Augot 1 Lancelot Pecquet 1
1 CODES - Coding and cryptography
Inria Paris-Rocquencourt
Abstract : We propose an improvement to SUDAN's algorithm for decoding REED-SOLOMON codes beyond half of their minimum distance, and its generalisation to algebraic-geometric codes. Both algorithms, in their original version, involve factorisation of polynomials. The main idea consists in replacing factorisation by an iterative root finding procedure of low complexity based on NEWTON approximation. In the case of REED-SOLOMON codes we give real complexity of tau-reconstructio- n.
Type de document :
Rapport
[Research Report] RR-3532, INRIA. 1998
Liste complète des métadonnées

https://hal.inria.fr/inria-00073153
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:00:16
Dernière modification le : samedi 17 septembre 2016 - 01:30:23
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:35:57

Fichiers

Identifiants

  • HAL Id : inria-00073153, version 1

Collections

Citation

Daniel Augot, Lancelot Pecquet. An Alternative to Factorization: a Speedup for SUDAN's Decoding Algorithm and its Generalization to Algebraic-Geometric Codes. [Research Report] RR-3532, INRIA. 1998. 〈inria-00073153〉

Partager

Métriques

Consultations de la notice

199

Téléchargements de fichiers

136