Reed-Solomon og NTP-koder
Forfattere
Knudsen, Jane Gravgård ; Iversen, Maria Sondrup
Semester
4. semester
Uddannelse
Udgivelsesår
2004
Abstract
I dette speciale undersøger vi fejlkorrigerende koder af typerne Reed-Solomon og NTP. Først introduceres Reed-Solomon-koder og deres centrale egenskaber. Vi beskriver, hvordan de kan dekodes, når antallet af fejl er mindre end d/2, hvor d er kodens minimumsafstand (en størrelse, der siger noget om, hvor mange fejl der kan rettes). Derefter gennemgås to listedekodningsalgoritmer, som kan finde en liste af mulige løsninger og dermed håndtere flere end d/2 fejl. For at bruge disse algoritmer skal man kunne finde førstegradsfaktorer (lineære faktorer) i det interpolationspolynomium, der indgår i metoden, og vi opstiller forskellige algoritmer til netop denne opgave. Før definitionen af NTP-koder præsenteres den nødvendige algebraiske teori, herunder Gröbner-baser og fodaftryk af idealer. For NTP-koder bestemmes minimumsafstand, dimension og dualkode. Desuden præsenteres en dekodningsalgoritme, som kan rette op til (d - g)/2 fejl, hvor d er minimumsafstanden. Afslutningsvis vurderes de to kodetyper i forhold til hinanden ud fra ønsket om både høj hastighed (høj kodningsrate) og høj relativ minimumsafstand.
This thesis studies error-correcting codes of the Reed-Solomon and NTP types. We first introduce Reed-Solomon codes and their key properties, and explain how to decode them when fewer than d/2 errors have occurred, where d is the code’s minimum distance (a quantity indicating how many errors can be corrected). We then present two list-decoding algorithms that can handle more than d/2 errors by outputting a list of candidate codewords. To use these algorithms, one must find linear (first-degree) factors in a certain interpolation polynomial; we develop several algorithms to perform this task. Before defining NTP codes, we review the necessary algebraic background, including Gröbner bases and footprints of ideals. For NTP codes, we determine the minimum distance, the dimension, and the dual code. We also present a decoding algorithm that can correct up to (d - g)/2 errors, where d is the minimum distance. Finally, we briefly compare the two code families with respect to the goal of achieving both high rate and high relative minimum distance.
[Dette resumé er genereret ved hjælp af AI]