Algebraisk Netværkskodning: Gröbner-Baser og Deres Anvendelse i Netværkskodning & Fejlkorrigerende Netværkskodning
Oversat titel
Algebraic Network Coding: Application of Gröbner bases in Network Coding & Error Correcting Network Coding
Forfattere
Simonsen, Maria ; Svendsen, Majken
Semester
4. semester
Uddannelse
Udgivelsesår
2012
Afleveret
2012-06-01
Antal sider
151
Abstract
I dette speciale bruger vi algebraisk netværkskodning—hvor datapakker kombineres ved hjælp af algebra—til at gøre dataoverførsel mere effektiv og mere robust over for fejl, og til at udvikle koder, der kan rette fejl. I første del anvender vi Gröbner-basisteori, et værktøj fra algebra, til at afgøre om et givent netværkskodningsproblem overhovedet har en løsning, og til at vurdere sandsynligheden for at finde en løsning for et vilkårligt problem. I anden del præsenterer vi KK-koden, som kan fejlkorrigere med en minimumsafstandsdekoder (en dekoder der vælger det kodeord, der ligger tættest på det modtagne). KK-koden ligger tæt på Singleton-grænsen, en teoretisk grænse for hvor meget fejlretning en kode kan opnå i forhold til dens længde og informationsindhold. Vi modificerer derefter KK-koden til MV-koden, der kan fejlkorrigere ved liste-L-dekodning (dekoderen returnerer en kort liste af mulige løsninger). Vi ser, at MV-koden har bedre fejlretningsevne end KK-koden ved lave pakkehastigheder. Begge koder er konstrueret over ringen af lineariserede polynomier, og derfor gennemgår vi også den nødvendige teori herom.
This thesis uses algebraic network coding—combining data packets using algebraic operations—to make data transmission more efficient and resilient to errors, and to design error-correcting codes. In the first part, we apply Gröbner basis theory, an algebraic tool, to determine whether a given network coding problem has a solution and to assess the probability of finding a solution for an arbitrary problem. In the second part, we present the KK code, which corrects errors with a minimum-distance decoder (a decoder that selects the codeword closest to the received data). The KK code comes close to the Singleton Bound, a theoretical limit on how much error correction a code can achieve relative to its length and information content. We then modify the KK code into the MV code, which supports list-L decoding (the decoder returns a short list of candidate solutions). We find that the MV code has better error-correction capability than the KK code at low packet rates. Both codes are constructed over the ring of linearized polynomials, and we therefore also present the necessary theory for this structure.
[Dette resumé er genereret ved hjælp af AI]
Emneord