Decoding of Algebraic Geometry Codes

Abstract

Codes derived from algebraic curves are called algebraic geometry (AG) codes. They provide a way to correct errors which occur during transmission of information. This paper will concentrate on the decoding of algebraic geometry codes, in other words, how to find errors. We begin with a brief overview of some classical result in algebra as well as the definition of algebraic geometry codes. Then the theory of cyclic codes and BCH codes will be presented. We discuss the problem of finding the shortest linear feedback shift register (LFSR) which generates a given finite sequence. A decoding algorithm for BCH codes is the Berlekamp-Massey algorithm. This algorithm has complexity O(n^2) and provides a general solution to the problem of finding the shortest LFSR that generates a given sequence (which usually has running time O(n^3)). This algorithm may also be used for AG codes. Further we proceed with algorithms for decoding AG codes. The first algorithm for decoding algebraic geometry codes which we discuss is the so called basic decoding algorithm. This algorithm depends on the choice of a suitable divisor F. By creating a linear system of equation from the bases of spaces with prescribed zeroes and allowed poles we can find an error-locator function which contains all the error positions among its zeros. We find that this algorithm can correct up to (d* - 1 - g)/2 errors and have a running time of O(n^3). From this algorithm two other algorithms which improve on the error correcting capability are developed. The first algorithm developed from the basic algorithm is the modified algorithm. This algorithm depends on a restriction on the divisors which are used to build the code and an increasing sequence of divisors F1, ... , Fs. This gives rise to an algorithm which can correct up to (d*-1)/2 -S(H) errors and have a complexity of O(n^4). The correction rate of this algorithm is larger than the rate for the basic algorithm but it runs slower. The extended modified algorithm is created by the use of what we refer to as special divisors. We choose the divisors in the sequence of the modified algorithm to have certain properties so that the algorithm runs faster. When s(E) is the Clifford's defect of a set E of special divisor, the extended modified algorithm corrects up to (d*-1)/2 -s(E) which is an improvement from the basic algorithm. The running time of the algorithm is O(n^3). The last algorithm we present is the Sudan-Guruswami list decoding algorithm. This algorithm searches for all possible code words within a certain distance from the received word. We show that AG codes are (e,b)-decodable and that the algorithm in most cases has a a higher correction rate than the other algorithms presented here.