Change search
ReferencesLink to record
Permanent link

Direct link
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
URN: urn:nbn:no:ntnu:diva-13729Local ID: ntnudaim:6311OAI: diva2:442048
Available from: 2011-09-20 Created: 2011-09-20 Last updated: 2013-06-23Bibliographically approved

Open Access in DiVA

fulltext(876 kB)196 downloads
File information
File name FULLTEXT01.pdfFile size 876 kBChecksum SHA-512
Type fulltextMimetype application/pdf
cover(47 kB)31 downloads
File information
File name COVER01.pdfFile size 47 kBChecksum SHA-512
Type coverMimetype application/pdf

By organisation
Department of Physics

Search outside of DiVA

GoogleGoogle Scholar
Total: 196 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 46 hits
ReferencesLink to record
Permanent link

Direct link