An Alternative to Factorization: a Speedup for SUDAN's Decoding Algorithm and its Generalization to Algebraic-Geometric Codes
Daniel Augot, Lancelot Pecquet · 1998
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.