Rateless coding in the finite length regime

Schotsch, Birgit; Vary, Peter

doi:1437-6768

Rateless coding in the finite length regime = Ratenlose Codierung bei endlicher Eingangswortbreite

Schotsch, Birgit (Author)

2014

VerantwortlichkeitsangabeBirgit Elke Schotsch

Ausgabe1. Aufl.

ImpressumAachen : Publikationsserver der RWTH Aachen University 2014

UmfangXVI, 165 S. : graph. Darst.

ReiheAachener Beiträge zu digitalen Nachrichtensystemen ; 38

Zugl.: Aachen, Techn. Hochsch., Diss., 2014

Genehmigende Fakultät
Fak06

Hauptberichter/Gutachter
Vary, Peter (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2014-07-18

Online
URN: urn:nbn:de:hbz:82-opus-51940
URL: https://publications.rwth-aachen.de/record/444696/files/5194.pdf

Einrichtungen

Lehrstuhl und Institut für Nachrichtengeräte und Datenverarbeitung (613310)

Inhaltliche Beschreibung (Schlagwörter)
Kanalcodierung (Genormte SW) ; Lineares Gleichungssystem (Genormte SW) ; Galois-Feld (Genormte SW) ; Ingenieurwissenschaften (frei) ; ratenlose Codierung (frei) ; Digital Fountain Codes (frei) ; endliche Eingangswortbreite (frei) ; optimale Decodierung, lineare Gleichungssysteme mit zufälligen Koeffizienten (frei) ; rateless coding (frei) ; finite length (frei) ; optimal erasure decoding (frei) ; systems of random linear equations (frei)

Thematische Einordnung (Klassifikation)
DDC: 620

Kurzfassung
Ratenlose Codes, auch als „Digital Fountain Codes” bekannt, eignen sich hervorragend zur Auslöschungskorrektur bei paketbasierter Datenübertragung. Paketverluste entstehen meist durch Überlastungen im Kommunikationsnetz oder durch Bitfehler innerhalb von Paketen. Die Haupteigenschaften von ratenlosen Codes lassen sich wie folgt zusammenfassen:- Der Sender ist in der Lage aus einem Quelldatenblock, bestehend aus k Quellpaketen, so viele codierte Pakete wie gewünscht zu erzeugen.- Der Empfänger ist in der Lage aus k(1+eps) beliebigen empfangenen (d.h. nicht ausgelöschten) codierten Paketen, den ursprünglichen Quelldatenblock zu rekonstruieren, wobei eps>=0 einen häufig vernachlässigbar kleinen Empfangszuschlag darstellt.- Ratenlose Codes benötigen außerdem keinen Rückkanal, um den Empfang von Paketen zu bestätigen.In der Literatur werden ratenlose Codes häufig unter der vereinfachenden Annahme unendlich langer Eingangsworte betrachtet und entworfen. Die sich daraus ergebenden Analysemöglichkeiten und Charakteristiken sind jedoch auf ebensolche Codes beschränkt, was mit entsprechend langen Übertragungslatenzen einhergeht.Im Gegensatz dazu ist der Schwerpunkt dieser Arbeit die ratenlose Codierung mit endlicher (insbesondere kurzer bis mittlerer) Eingangswortbreite, was den Einsatz in Systemen mit höheren Anforderungen an die Übertragungslatenz erlaubt. In diesem Kontext werden verschiedene Arten von "LT Codes" und "Raptor Codes", ebenfalls unter der Randbedingung endlicher Eingangswortbreiten, untersucht.Die Hauptaspekte dieser Arbeit sind:- Die Herleitung geschlossener Formeln für die Restauslöschungswahrscheinlichkeit bei optimaler Auslöschungsdecodierung.- Die Herleitung asymptotisch exakter oberer und unterer Schranken für die Restauslöschungswahrscheinlichkeit nach Decodierung.- Die Verallgemeinerung binärer Codes zu Codes über Galois-Feldern höherer Ordnung.- Die Formulierung konkreter Entwurfsvorschriften für effiziente LT Code Ensembles mit gleichmäßigem und ungleichmäßigem Schutz gegen Auslöschungen.- Neue Maße in Form zweier Gewichtsprofile zur Bewertung der Leistungsfähigkeit von Raptor Codes.Der Schlüssel zur Erzielung dieser Ergebnisse ist die Formulierung des Erwartungswertes der Auslöschungskorrekturfähigkeit von LT Code Ensembles als äquivalentes mathematisches Problem. Das Problem kann auf die grundlegende Frage zurückgeführt werden, ob ein konsistentes lineares Gleichungssystem, definiert über einem endlichen Körper, dessen Koeffizienten einem speziell entworfenen Zufallsprozess unterliegen, teilweise oder vollständig gelöst werden kann.

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

Fulltext:
PDF