On the decoding of algebraic-geometric codes

A decoding algorithm for algebraic-geometric codes arising from arbitrary algebraic curves is presented. This algorithm corrects any number of errors up to ((d-g-1)/2), where d is the designed distance of the code and g is the genus of the curve. The complexity of decoding equals sigma (n/sup 3/) where n is the length of the code. Also presented is a modification of this algorithm, which in the case of elliptic and hyperelliptic curves is able to correct ((d-1)/2) errors. It is shown that for some codes based on plane curves the modified decoding algorithm corrects approximately d/2-g/4 errors. Asymptotically good q-ary codes with a polynomial construction and a polynomial decoding algorithm (for q>or=361 on some segment their parameters are better than the Gilbert-Varshamov bound) are obtained. A family of asymptotically good binary codes with polynomial construction and polynomial decoding is also obtained, whose parameters are better than the Blokh-Zyablov bound on the whole interval 0>