RWTH Aachen
University
Institute for Communication
Systems and Data Processing
Skip to content
Direkt zur Navigation
Home
Home

Publications – Details

Rateless Coding in the Finite Length Regime

Author:
Birgit Schotsch
Editor:
Peter Vary
Type:
Dissertation
Series:
Aachener Beiträge zu Digitalen Nachrichtensystemen (ABDN)
Number:
38
School:
IND, RWTH Aachen
Publisher:
Verlag Mainz in Aachen
Date:
Sept. 2014
ISBN:
978-3-86073-837-5
Language:
English

Abstract

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+ε) received (i.e. non-erased) encoded packets, where ε≥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.

Download of Publication

Copyright Notice

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

The following notice applies to all IEEE publications:
© IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

File

schotsch14.pdf 1486 K