Change search

Decoding of Algebraic Geometry Codes
Norwegian University of Science and Technology, Faculty of Natural Sciences and Technology, Department of Physics.
2011 (English)MasteroppgaveStudent thesis
##### Abstract [en]

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.

##### Place, publisher, year, edition, pages
Institutt for matematiske fag , 2011. , 67 p.
##### Keyword [no]
ntnudaim:6311, MTFYMA fysikk og matematikk, Industriell matematikk
##### Identifiers
Local ID: ntnudaim:6311OAI: oai:DiVA.org:ntnu-13729DiVA: diva2:442048
##### Supervisors
Available from: 2011-09-20 Created: 2011-09-20 Last updated: 2013-06-23Bibliographically approved

#### Open Access in DiVA

##### File information
File name FULLTEXT01.pdfFile size 876 kBChecksum SHA-512
682fa93bba46bf2438741fdee07febc3d383804e81fc09856b23e431d7910594775ba89691c6129b20b7688d26d1e61eb1ea14e83fd1e429f950626a5ae04705
Type fulltextMimetype application/pdf
##### File information
File name COVER01.pdfFile size 47 kBChecksum SHA-512
11d28b52500a0f791aacfa03a2edfcf20ecacdcaf61c3ba99f59648460f977bc4da1bbff1493617d352ea4f542d4724591aff135e3f9879ed955f42854564466
Type coverMimetype application/pdf
##### By organisation
Department of Physics