Rateless Coding in the Finite Length Regime

Rateless codes, also known as digital fountain codes, are excellently suited for erasure correction in packet-switched communication networks. Such networks are usually prone to packet losses due to network congestions or unrecoverable bit errors within packets. The main attributes of rateless codes can be summarised as follows:

• The transmitter is able to produce as many encoded packets as needed from a given source block consisting of k source packets.
• The receiver is able to decode an exact copy of the entire source block from any subset of k (1+e) received (i. e. non-erased) encoded packets, where e = 0 is a small reception overhead.
• Rateless codes do not require a feedback channel for packet acknowledgements.

In the literature, rateless codes are usually based on the simplifying design assumptions of input sequences of infinite length. The analysis and characterisation of the so designed codes applies only to codes with very long input sequences and a corresponding latency. In contrast, this thesis focuses codes with a finite (especially short to medium) length. These practical lengths enable applications that require a low transmission latency. In this context, various types of finite length LT codes and Raptor codes are investigated. The main contributions of this thesis are:

• The derivation of closed form expressions of the residual erasure probability under optimal decoding.
• The derivation of tight upper and lower residual erasure bounds.
• The generalisation of binary codes to higher order Galois fields.
• The formulation of concrete design guidelines for highly efficient LT code ensembles with equal and unequal erasure protection.
• New performance assessment tools for Raptor codes in terms of the so-called erasure weight and kernel weight profiles.

The key to the achieved results is to formulate the expected erasure correction performance of an LT code ensemble as an equivalent mathematical problem. This fundamental question is whether a consistent system of designed random linear equations over a finite field can be solved partially or completely.