Reed-Solomon og NTP-koder
Oversat titel
Forfattere
Semester
4. semester
Uddannelse
Udgivelsesår
2004
Afleveret
2012-02-14
Abstract
I dette speciale betragtes Reed-Solomon og $NTP$-koder. Først præsenteres Reed-Solomon koder, og deres egenskaber, hvorefter der ses på dekodning af disse koder i de tilfælde, hvor der er sket færre end $d/2$ fejl. Herefter gennemgås to listedekodningsalgoritmer, som gør det muligt at rette flere end $d/2$ fejl. For at kunne benytte disse to listedekodningsalgoritmer skal der kunne bestemmes førstegradsfaktorer i interpolationspolynomiet, hvilket der opstilles forskellige algoritmer til at løse. Før definitionen af $NTP$-koder introduceres gennemgås teori, som gør dette muligt. Herunder teori om Gr\"obner baser og fodaftryk af idealer. Herefter bestemmes minimumsafstand, dimension og dualkode for $NTP$-koderne. Desuden præsenteres en dekodningsalgoritme for disse koder, som kan rette op til $\frac{d-g}{2}$ fejl. Til slut gives en kort vurdering af de to koder, i forhold til hinanden, udfra kriteriet om, at koder bør have en høj hastighed samtidig med en høj relativ minimumsafstand.