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


Daniel Augot
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Daniel.Augot@inria.fr

Lancelot Pecquet
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Lancelot.Pecquet@inria.fr

Research Report RR-3532 INRIA, 1998

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-reconstruction .

Postscript and PDF versions