Fountain codes: performance analysis and optimization

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.