Reed-Solomon og NTP-koder
Studenteropgave: Kandidatspeciale og HD afgangsprojekt
- Jane Gravgård Knudsen
- Maria Sondrup Iversen
4. semester, Matematik, Kandidat (Kandidatuddannelse)
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.
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.
Sprog | Dansk |
---|---|
Udgivelsesdato | jun. 2004 |