Fountain codes: performance analysis and optimization

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Tirronen, Tuomas
dc.date.accessioned 2012-08-24T07:45:13Z
dc.date.available 2012-08-24T07:45:13Z
dc.date.issued 2009
dc.identifier.isbn 978-952-248-267-9 (electronic)
dc.identifier.isbn 978-952-248-266-2 (printed) #8195;
dc.identifier.issn 1797-4798
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/4743
dc.description.abstract 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. en
dc.format.extent Verkkokirja (1416 KB, 110 s.)
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Teknillinen korkeakoulu en
dc.relation.ispartofseries Report. Helsinki University of Technology, Department of Communications and Networking, 6/2009 en
dc.relation.haspart [Publication 1]: Esa Hyytiä, Tuomas Tirronen, and Jorma Virtamo. 2007. Optimal degree distribution for LT codes with small message length. In: Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM 2007). Anchorage, Alaska, USA. 6-12 May 2007, pages 2576-2580. © 2007 Institute of Electrical and Electronics Engineers (IEEE). By permission. en
dc.relation.haspart [Publication 2]: Esa Hyytiä, Tuomas Tirronen, and Jorma Virtamo. 2006. Optimizing the degree distribution of LT codes with an importance sampling approach. In: Werner Sandmann (editor). Proceedings of the 6th International Workshop on Rare Event Simulation (RESIM 2006). Bamberg, Germany. 8-10 October 2006, pages 64-73. © 2006 by authors. en
dc.relation.haspart [Publication 3]: Tuomas Tirronen and Jorma Virtamo. 2007. Performance analysis of divided random linear fountain. In: Proceedings of the 2007 IEEE Global Telecommunications Conference (GLOBECOM 2007). Washington D.C., USA. 26-30 November 2007, pages 520-526. © 2007 Institute of Electrical and Electronics Engineers (IEEE). By permission. en
dc.relation.haspart [Publication 4]: Tuomas Tirronen and Jorma Virtamo. 2008. Greedy approach for efficient packet erasure coding. In: Proceedings of the 2008 5th International Symposium on Turbo Codes and Related Topics. Lausanne, Switzerland. 1-5 September 2008, pages 344-349. © 2008 Institute of Electrical and Electronics Engineers (IEEE). By permission. en
dc.relation.haspart [Publication 5]: Tuomas Tirronen and Jorma Virtamo. 2008. Finding fountain codes for real-time data by fixed point method. In: Proceedings of the 2008 International Symposium on Information Theory and its Applications (ISITA 2008). Auckland, New Zealand. 7-10 December 2008, pages 1244-1249. © 2008 Institute of Electrical and Electronics Engineers (IEEE). By permission. en
dc.relation.haspart [Publication 6]: Tuomas Tirronen and Jorma Virtamo. 2009. Performance analysis of sliding window based erasure correction for real-time traffic. In: Proceedings of the 5th Conference on Next Generation Internet Networks (NGI 2009). Aveiro, Portugal. 1-3 July 2009, pages 1-8. © 2009 Institute of Electrical and Electronics Engineers (IEEE). By permission. en
dc.relation.haspart [Publication 7]: Tuomas Tirronen. 2009. Sliding window-based erasure correction using biased sampling. In: Eugen Borcoci, Michel Diaz, Cosmin Dini, and Reijo Savola (editors). Proceedings of the Fourth International Conference on Systems and Networks Communications (ICSNC 2009). Porto, Portugal. 20-25 September 2009, pages 144-152. © 2009 Institute of Electrical and Electronics Engineers (IEEE). By permission. en
dc.relation.haspart [Errata file]: Errata of publications 2, 5 and 6 en
dc.subject.other Telecommunications engineering
dc.title Fountain codes: performance analysis and optimization en
dc.type G5 Artikkeliväitöskirja fi
dc.contributor.school Aalto-yliopiston teknillinen korkeakoulu fi
dc.contributor.department Tietoliikenne- ja tietoverkkotekniikan laitos fi
dc.subject.keyword fountain coding en
dc.subject.keyword erasure coding en
dc.subject.keyword rateless coding en
dc.subject.keyword coding theory en
dc.subject.keyword Markov chains en
dc.identifier.urn URN:ISBN:978-952-248-267-9
dc.type.dcmitype text en
dc.type.ontasot Väitöskirja (artikkeli) fi
dc.type.ontasot Doctoral dissertation (article-based) en


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account