NTP-koder - deres egenskaber og dekodning
Forfatter
Rasmussen, Elisabeth Kuhr
Semester
4. semester
Uddannelse
Udgivelsesår
2005
Abstract
Dette speciale undersøger en generalisering af Reed–Solomon-koder, som her kaldes NTP-koder. Før definitionen af NTP-koder gennemgås den nødvendige teori, herunder Gröbner-baser og idealers fodaftryk (footprint), som er algebraiske værktøjer til at analysere polynomiale strukturer. Efter at have defineret NTP-koderne bestemmes deres minimumsafstand ved hjælp af egenskaber ved fodaftryk af et ideal. Minimumsafstanden angiver den mindste forskel mellem to kodeord og hænger tæt sammen med, hvor mange fejl koden kan rette. Derudover bruges teori om semigrupper til at finde både dimensionen og dualkoden for NTP-koderne. Resten af arbejdet fokuserer på dekodning. Først præsenteres en grundalgoritme, der kan rette op til (d − g)/2 fejl. Derefter erstattes dele af denne med en basisalgoritme, som i første omgang ikke er bedre, da den kun kan rette (n − s − g − 1)/2 fejl (med (n − s) ≤ d). En forbedring baseret på et majoritetsprincip øger dog antallet af fejl, der kan rettes, til (n − s − 1)/2. Til sidst præsenteres en algoritme, der ikke kan rette flere fejl, men som er mere effektiv, fordi den har lavere beregningskompleksitet.
This thesis studies a generalization of Reed–Solomon codes, referred to here as NTP codes. Before defining NTP codes, it reviews the necessary background, including Gröbner bases and the footprint of ideals, algebraic tools used to analyze polynomial structures. After defining NTP codes, the minimum distance is derived using properties of ideal footprints. The minimum distance is the smallest difference between two codewords and is directly linked to how many errors the code can correct. Semigroup theory is then used to determine the dimension and the dual code of the NTP codes. The remainder of the work focuses on decoding. First, a basic algorithm is presented that can correct up to (d − g)/2 errors. Parts of this are then replaced by a base algorithm, which is initially not better, since it only corrects (n − s − g − 1)/2 errors (with (n − s) ≤ d). An improvement based on a majority principle raises the number of correctable errors to (n − s − 1)/2. Finally, an algorithm is presented that does not correct more errors but is more efficient due to reduced computational complexity.
[Dette resumé er genereret ved hjælp af AI]