Parameter choices and a better bound on the list size in the Guruswami-Sudan algorithm for algebraic geometry codes

摘要

Given an algebraic geometry code C_L(D,αP), the Guruswami-Sudan algorithm produces a list of all codewords in C_L(D, αP) within a specified distance of a received word. The initialization step in the algorithm involves parameter choices that bound the degree of the interpolating polynomial and hence the length of the list of codewords generated. In this paper, we use simple properties of discriminants of polynomials over finite fields to provide improved parameter choices for the Guruswami-Sudan list decoding algorithm for algebraic geometry codes. As a consequence, we obtain a better bound on the list size as well as a lower degree interpolating polynomial.