Optimizing the Degree Distribution of LT Codes
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
Helsinki University of Technology |
Diplomityö
Checking the digitized thesis and permission for publishing
Instructions for the author
Instructions for the author
Authors
Date
2006
Department
Major/Subject
Tietoverkkotekniikka
Mcode
S-38
Degree programme
Language
en
Pages
viii + 74
Series
Abstract
Tämä työ käsittelee tiedonsiirtoon liittyviä kysymyksiä virheen korjaavien koodien näkökulmasta. Erityisesti käsitellään koodeja, jotka toteuttavat niin sanotun suihkulähdeperiaatteen. Suihkulähde suihkuttaa vesipisaroita ilmaan, joita voidaan kerätä asettamalla sanko suihkulähteen alle. Sanko täyttyy riippumatta siitä, paljonko pisaroita menee ohi tai mitkä pisarat sankoon osuvat. Samalla tavalla suihkulähdeperiaatteen mukaisessa tiedonsiirrossa tiedoston lähettäjä lähettää paketteja tietoverkkoon ja tiedoston vastaanottajan tulee kerätä tietty määrä lähetettyjä paketteja saadakseen lähetetyn tiedoston purettua. Sillä, mitkä paketit vastaanottaja saa, ei ole merkitystä. Hyvillä koodeilla tarvittavien pakettien yhteenlaskettu koko on vain vähän enemmän kuin alkuperäisen tiedoston koko. Perinteisiä Reed-Solomon-koodeja voidaan käyttää suihkulähdeperiaatteen tavoin, mutta tehokkaampiakin koodeja on kehitetty. LT-koodit ovat tehokkaita ja asymptoottisesti optimaalisia koodeja, jotka toimivat erittäin hyvin kun lähdelohkojen lukumäärä on suuri. Myös LDPC-koodit esitellään lyhyesti yhtenä vaihtoehtona suihkulähdeperiaatteen toteuttamiseen. LT-koodit tarvitsevat huolellisesti suunnitellun astelukujakauman toimiakseen tehokkaasti. Työssä esitellään kirjallisuudessa aiemmin ehdotettuja jakaumia ja esitetään uusi menetelmä astelukujakauman optimoimiseksi. Tämä menetelmä perustuu koodauksen purkuun tarvittavan keskimääräisen pakettien lukumäärän estimointiin. Estimaatti lasketaan tärkeysotantaan perustuvalla menetelmällä, ja tämän jälkeen estimaattia optimoidaan standardeilla optimointimenetelmillä. Työn lopussa esitetään algoritmilla laskettuja numeerisia testituloksia. Lisäksi työssä ehdotetaan sovellusalueita esitetyille koodeille sekä pohditaan ongelmia, joita näitä koodeja käytettäessä on huomioitava.Description
Supervisor
Virtamo, JormaThesis advisor
Hyytiä, EsaKeywords
LT codes, LT koodit, erasure codes, virheen korjaavat koodit, forward error correction, tärkeysotanta, importance sampling, suihkulähdekoodit