Skip to Main content Skip to Navigation
Reports

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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00073153
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 12:00:16 PM
Last modification on : Friday, May 25, 2018 - 12:02:03 PM
Long-term archiving on: : Sunday, April 4, 2010 - 11:35:57 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

257

Files downloads

185