Fountain codes: performance analysis and optimization
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Aalto-yliopiston teknillinen korkeakoulu |
Doctoral thesis (article-based)
Checking the digitized thesis and permission for publishing
Instructions for the author
Instructions for the author
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2009
Major/Subject
Mcode
Degree programme
Language
en
Pages
Verkkokirja (1416 KB, 110 s.)
Series
Report.
Helsinki University of Technology, Department of Communications and Networking,
6/2009
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.Description
Keywords
fountain coding, erasure coding, rateless coding, coding theory, Markov chains
Other note
Parts
- [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.
- [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.
- [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.
- [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.
- [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.
- [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.
- [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.
- [Errata file]: Errata of publications 2, 5 and 6