A lifting method to replace factorization in Sudan's algorithm.
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
IEEE Transactions on Information Theory, 46(7):2605-2614,
November 2000.
Abstract
This correspondence presents an algorithmic improvement to Sudan's
list-decoding algorithm for Reed Solomon codes and its generalization
to algebraic geometric codes from Shokrollahi and Wasserman. Instead
of completely factoring the interpolation polynomial over the function
field of the curve, we compute sufficiently many coefficients of a
Hensel development to reconstruct the functions that correspond to
codewords. We prove that these Hensel developments can be found
efficiently using Newton s method. We also describe the algorithm in
the special case of Reed Solomon codes.
Keywords
Algebraic geometric codes, Hensel lifting, list decoding, Newton s method, polynomials over algebraic function fields, Reed Solomon codes.