NTP-koder - deres egenskaber og dekodning

Studenteropgave: Kandidatspeciale og HD afgangsprojekt

  • Elisabeth Kuhr Rasmussen
4. semester, Matematik, Kandidat (Kandidatuddannelse)
I dette speciale betragtes en generalisering af Reed-Solomon koder, som i denne rapport benævnes NTP-koder.
Før definitionen af NTP-koder introduceres, gennemgåes teori, som gør dette muligt. Herunder teori om Gr\"obner baser og fodaftryk af idealer.
Efter definitionen af NTP-koderne bestemmes minimumsafstanden herfor udfra egenskaber vedrørende fodaftrykket af et ideal, og teori om semigrupper anvendes til at afgøre, hvad dimensionen og dualkoden er for NTP-koderne.
Resten af rapporten omhandler dekodning af NTP-koder. Først præsenteres en grundalgoritme, som kan rette op til (d-g)/2 fejl.
Efterfølgende erstattes dele af denne grundalgoritme med en basisalgoritme, som i første omgang ikke er en bedre algoritme, da den kun kan rette (n - s - g - 1)/2 fejl ( (n - s) =<d). En forbedring med et majoritetsprincip bringer dog antallet af fejl, som kan rettes, op på (n - s - 1)/2.
Tilsidst præsenteres en algoritme, som ikke kan rette flere fejl, men den bliver mere effektiv, da kompleksiteten nedsættes.
SprogDansk
Udgivelsesdatomar. 2005
ID: 61063630