Efficient root-finding algorithm with application to list decoding of algebraic-geometric codes

A list decoding for an error-correcting code is a decoding algorithm that g enerates a list of codewords within a Hamming distance t from the received vector, where t can be greater than the error-correction bound. In [18], a list-decoding procedure for Reed-Solomon codes [19] was generalized to alge braic-geometric codes. A recent work [8] gives improved list decodings for Reed-Solomon codes and algebraic-geometric codes that work for all rates an d have many applications. However, these list-decoding algorithms are rathe r complicated. In [17], Roth and Ruckenstein proposed an efficient implemen tation of the list decoding of Reed-Solomon codes. In this correspondence, extending Roth and Ruckenstein's fast algorithm for finding roots of univar iate polynomials over polynomial rings, i.e., the Reconstruct Algorithm, we will present an efficient algorithm for finding the roots of univariate po lynomials over function fields. Based on the extended algorithm, we give an efficient list-decoding algorithm for algebraic-geometric codes.