Browsing by Author "Tirronen, Tuomas"

Now showing 1 - 3 of 3

Fountain and Packet Erasure Coding
(2008) Gao, Shan
Elektroniikan, tietoliikenteen ja automaation tiedekunta | Bachelor's thesis
Fountain codes: performance analysis and optimization
(2009) Tirronen, Tuomas
Aalto-yliopiston teknillinen korkeakoulu | Doctoral dissertation (article-based)
The fountain coding principle provides a framework for efficient and reliable data transmission techniques over erasure channels, such as file transmission over the Internet. This thesis presents topics related to the optimisation and performance analysis for different settings where fountain coding methods are applied. We start by reviewing the fountain coding principle on which our own contributions are based. Strategies for both elastic and streaming traffic are considered. The coding schemes are typically modelled as stochastic processes and we analyse them using well-known tools, such as Markov chains and fixed-point iteration. Some of the schemes realise the principles of an ideal digital fountain, while the other sacrifice some characteristics, such as time-independence and the statistical equivalence of the encoded packets. The description of our own work is divided into two parts. The first part begins by addressing the optimisation of the degree distribution of LT coding, the first universal fountain coding method, for small file sizes. We present exact analysis for LT codes of very small size with some novel results. A simulation based method is presented for the analysis and optimisation of longer codes, up to hundreds of source blocks. We further present a method in which a random linear fountain code is divided into parts and conduct a performance analysis of the system. We propose and analyse two different strategies to overcome the performance degradation caused by the division. The first part ends with the description and optimisation of a systematic, sequential coding scheme in which the sender makes greedy choices concerning the repair packet structure on the basis of his belief about the state of the receiver. We present repair packet degree sequences which result in a low required overhead. In the second part we will address the problem of achieving a low residual erasure probability for streaming traffic using packet erasure correction. The methods are based on a sliding window. Four different methods are presented differing in how the repair packets are constructed. These codes further differ in the repair packet sending strategy; one code always sends a repair packet deterministically after a window movement, while the others send the repair packets probabilistically. We conclude that methods inspired by fountain coding provide efficient, yet simple, coding strategies for implementing data transfer in many settings.
Optimizing the Degree Distribution of LT Codes
(2006) Tirronen, Tuomas
Helsinki University of Technology | Master's thesis
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.