Eine Einführung zu Tornado-Codes» English version

Zusammenfassung

Tornado-Codes gehören zu einer neuen Klasse von fehlerkorrigierenden Codes für Erasure Channels, die auf der Konstruktion von zufällig verbundenen irregulären bipartiten Graphen basieren. Durch die sorgfältige Wahl der Struktur der Graphen erreichen Tornado-Codes eine beinahe optimale Effizienz, und mit einer linearen En- und Dekodierkomplexität und relativ einfachen und schnellen Algorithmen sind sie geradezu ideal geeignet für die Kodierung von großen Datenmengen und als Alternative zum klassischen ARQ-Konzept, wie es im Internet verwendet wird.

In dieser Arbeit wird nach einer kurzen Einführung zu fehlerkorrigierenden Codes die Konstruktion und das Funktionsprinzip von Tornado-Codes erläutert, gefolgt von der Analyse des Dekodiervorganges, worauf aufbauend reguläre und irreguläre Graphen mit einer nahezu optimalen Effizienz präsentiert werden. Nach einer kurzen Gegenüberstellung von Tornado-Codes und Reed-Solomon-Codes, den gebräuchlichsten fehlerkorrigierenden Codes, wird eine eigene Implementation von Tornado-Codes vorgestellt. Die letzten beiden Kapitel behandeln mögliche Anwendungen von Tornado-Codes und bieten einen kurzen Ausblick auf weitere Entwicklungen in diesem Bereich.

Einführung zu fehlerkorrigierenden Codes

Bei jeder Übertragung einer Nachricht eines Senders an einen Empfänger treten unweigerlich Störungen im Kanal, den die Nachricht durchläuft, auf. Diese Störungen sind unterschiedlicher Natur, wie z.B. Rauschen im Kanal oder Interferenz durch andere Kommunikationen, und verursachen Fehler in der übertragenen Nachricht [2]. Selbstverständlich ist das Ziel einer jeden Kommunikation die zuverlässige Übertragung der Information, was gleich zu verstehen damit ist, daß die Anzahl der auftretenden Fehler möglichst klein gehalten werden soll. Dies kann auf unterschiedliche Art erreicht werden. Auf direktem Weg kann dies erreicht werden, indem entweder die Störungen verringert werden, z.B. auf physikalischer Seite durch eine bessere Isolation des Kanals, oder einfach ein stärkeres Signal verwendet wird. Eine andere Möglichkeit auf Empfängerseite ist, bei einer nicht verstandenen Nachricht diese einfach vom Sender erneut anzufordern. Diese Technik heißt Automatic Repeat ReQuest (ARQ) und wird zum Beispiel im Internet bei nicht erhaltenen bzw. fehlerhaften Paketen angewendet.

Wenn man eine zwischenmenschliche Kommunikation betrachtet, so bemerkt man, daß bei einer geringen Anzahl von Fehlern die Nachricht dennoch verstanden werden kann. Dies ist möglich, weil die menschliche Sprache genügend Redundanz enthält, mithilfe derer die ursprüngliche Nachricht rekonstruiert werden kann. Dies führt uns zu einer anderen Möglichkeit, zuverlässige Kommunikation zu gewährleisten: dem Einsatz von fehlerkorrigierenden Codes bzw. forward error correcting codes.

Forward Error Correction

Unter Forward Error Correction (FEC) versteht man ganz allgemein das Hinzufügen von Redundanz zu Information derart, daß Fehler bei einer Übertragung erkannt bzw. korrigiert werden können [14]. Einfache fehlerkorrigierende Codes sind der einfache Parity-Check, der der Nachricht ein redundantes Bit als Summe der Datenbits modulo 2 hinzufügt, und der Repetition Code, der jedes Zeichen mehrfach wiederholt. Mit dem einfachen Parity-Check kann ein einzelner Bitfehler in einem Block erkannt werden, während ein Repetition Code der Länge 2t+1 bis zu t Fehler korrigieren kann. Dabei wird das am öftesten auftretende Zeichen als das wahrscheinlichste betrachtet. Mit besserer Fehlerkorrektur werden die Nachrichten mit dem Repetition-Code jedoch sehr lange. Die Coderate R beschreibt das Verhältnis zwischen der Anzahl der ursprünglichen Bits (Datenbits) und der Anzahl der gesamten Bits.

Coderate R = k/n

k...Anzahl der Datenbits (= Datenlänge)
n...Anzahl der gesamten Bits (= Blocklänge)
n-k...Anzahl der Checkbits (Paritätsbits)

Kanalmodelle

Die Behauptung, daß das beim Repetition Code am öftesten auftretende Zeichen das wahrscheinlichste ist, basiert auf der Annahme, daß Fehler unabhängig vom zugrundeliegenden Zeichen mit gleicher Wahrscheinlichkeit und unabhängig voneinander auftreten. Gibt es bei einem derart idealisierten Kanalmodell [3] nur zwei verschiedene Zeichen, so spricht man von einem Binary Symmetric Channel (BSC). Da die Fehler unabhängig von ihrer Position auftreten, spricht man auch von einem discrete memoryless channel.

Ein anderes wichtiges Kanalmodell ist der Binary Erasure Channel (BEC). Bei diesem sind die Positionen der Fehler bekannt. Insofern spricht man stattdessen auch oft von Löschungen (Erasures). Wird ein solcher Fehler erkannt, kann er auch gleich korrigiert werden, weshalb eine bessere Fehlerkorrektur als beim BSC gegeben ist.

Noisy Channel Coding Theorem

In den Anfangszeiten der elektronischen Datenübertragungen, in denen noch die Analogtechnik vorherrschte, nahm man an, daß eine beliebig niedrige Fehlerrate nur durch eine beliebig hohe Verstärkung des Signals oder durch beliebig viel redundate Information erreicht werden kann. Im Jahre 1948 überraschte jedoch Claude Shannon, als Forscher bei der bekannten Telefongesellschaft Bell Labs tätig, die Fachwelt mit seiner Publikation "A Mathematical Theory of Communication", in der er zeigte, daß unter bestimmten Vorraussetzungen und mit steigender Blocklänge eines FEC-Blockes die Fehlerwahrscheinlichkeit gegen 0 geht [12,5,6,20].

Zuerst sei die Kapazität C eines Kanals wie folgt definiert:

C = W · log2(1 + S/N) bits/sec.

C ist abhängig von der Bandbreite W und dem Signal-Rausch-Verhältnis S/N, und steht in direktem Zusammenhang zur Fehlerwahrscheinlichkeit p des Kanals. Für den BSC ist die Kapazität gegeben durch

CBSC = 1 + p·log2p + (1-p)·log2(1-p),

und für den BEC durch

CBEC = 1-p.

Die Kernaussage in Shannons Arbeit, die unter dem Namen Noisy Channel Coding Theorem bekannt ist, besagt nun, daß es FEC-Codes gibt, für die die Fehlerwahrscheinlichkeit des FEC-Blockes mit steigender Blocklänge 0 wird, unter der Voraussetzung, daß die Coderate kleiner als die Kapazität des Kanals ist. Also:

FEC-Codes: R < C: limn→∞P(Fehler) = 0

Umgekehrt gilt, ist die Coderate größer als die Kapazität, so geht die Fehlerwahrscheinlichkeit gegen 1:

R > C: limn→∞P(Fehler) = 1

Für eine beliebig niedrige Fehlerwahrscheinlichkeit und somit zuverlässige Kommunikation ist es also nicht erforderlich, die Coderate auf ein Minimum zu senken; die Coderate kann mit geeigneten Codes bis zur Kapazität des Kanals, was auch als Shannon-Grenze bezeichnet wird [7], heranreichen. (Insofern sind z.B. Repetition Codes sehr ineffizient.) Der Beweis Shannons Theorems beruht auf Wahrscheinlichkeitsrechnung und zeigt nicht, wie solche Codes konstruiert werden können. Die Konstruktion von FEC-Codes, die möglichst nahe an diese Shannon-Grenze herankommen, sollte die Forscher von nun an hauptsächlich beschäftigen (siehe insbesonders [20]).

Hamming-Codes

Richard Hamming, ebenfalls bei Bell Labs beschäftigt, erkannte als einer der ersten, worauf es bei der Konstruktion von FEC-Codes ankommt. Unter der Hamming-Distanz d zwischen zwei Vektoren X und Yversteht man die Anzahl der Stellen, in denen sich die zwei Vektoren unterscheiden. Je größer die Hamming-Distanz zwischen den einzelnen Codewörtern eines FEC-Codes, als Vektoren von Zeichen aufgefaßt, ist, desto mehr Fehler können erkannt bzw. korrigiert werden. Ein Code mit einer minimalen Hamming-Distanz dmin zwischen je zwei Codewörtern kann dmin-1 Bit-Fehler erkennen und ⌊(dmin-1)/2⌋ Fehler korrigieren [3,20].

1950 publizierte Hamming seine Arbeit über 1-Bit-Fehler-korrigierende Codes, die effizienter als simple Repetition Codes sind. Der dort vorgestellte (7,4)-Hamming-Code benötigt für 4 Datenbits nur noch 3 zusätzliche Checkbits, während z.B. ein Repetition Code dafür 8 zusätzliche Bits benötigt. Hamming-Codes besitzen eine minimale Hamming-Distanz dmin = 3.

Hamming soll diese Codes entwickelt haben, nachdem er sich darüber geärgert hatte, daß der mechanische Relaycomputer, auf dem er an den Wochenenden seine Programme laufen konnte, wiederholt diese aufgrund eines aufgetretenen Parity-Check-Fehlers abgebrochen hatte: "Damn it, if the machine can detect an error, why can't it locate the position of the error and correct it?"

Maximum-Likelihood Decoding

Bei der Dekodierung eines erhaltenen Wortes und somit der Fehlerkorrektur wird diesem das im Sinne der Hamming-Distanz am nähesten liegende Codewort zugeordnet, was einer Minimierung der Fehlerwahrscheinlichkeit entspricht. Dieses Problem ist im allgemeinen NP-vollständig [13].

Lineare Block-Codes

Hamming-Codes sind ein Spezialfall von linearen Block-Codes [3]. Von einem Block-Code spricht man, wenn statt einzelnen Zeichen Blöcke von Zeichen kodiert werden. Linear bedeutet, daß jede Linearkombination von gültigen Codewörtern ebenfalls ein Codewort ist. Aufgrund dieser Eigenschaft kann man einen linearen Code als einen Unterraum GF(q)k eines Vektorraums GF(q)n betrachten, wobei GF(q) für einen endlichen Körper (Galois field) der Ordnung q steht, und die Menge aller Codewörter kann mittels einer (k*n)-Matrix G repräsentiert werden. G steht dabei für Generator-Matrix, da die Codewörter mithilfe dieser Matrix berechnet werden können:

c = d*G = (d0,...,dk-1) * [Ik|P] = (d0,...,dk-1,pk,,...,pn-1)

d...Datensymbole
p...Paritätssymbole

Ist der linke Teil der Matrix G die Identitätsmatrix Ik, wie in der obigen Zeile dargestellt, so spricht man von einem systematischen Code, da die ersten k Symbole des Codewortes genau die Datensymbole sind.

Die Dekodierung eines Codewortes geschieht mithilfe der Parity-Check-Matrix H. H ist der Kern (null space) über alle Codewörter. Ein Wort ist ein Codewort gdw. es im Kern von H enthalten ist:

Syndrom s(c) = c*HT = 0

Die Komplexität von linearen Blockcodes ist im allgemeinen für die Kodierung O(n2), während die Dekodierung aufgrund des Problems des Maximum-Likelihood-Decodings NP-vollständig ist. Eine Lösung für die Dekodierung ist das Verwenden von Look-Up-Tables, was jedoch aufgrund des hohen Speicherverbrauchs nur für kleine Blocklängen geeignet ist. Es existieren jedoch eine Reihe von Spezialfällen von linearen Codes, für die die Dekodierung in polynomieller Zeit gelöst werden kann. Diese Spezialfälle sind die in der Praxis eingesetzten linearen Codes.

Wichtige FEC-Codes bis 1960

In den nächsten Jahren wurden eine Reihe von bedeutenden fehlerkorrigierenden Codes entwickelt, von denen die wichtigsten in dieser Tabelle aufgelistet sind [3]:

JahrFEC-CodeEntwickler
1955Convolutional CodesElias
1957Zyklische CodesPrange
1959-1960BCH-CodesBose, Chaudhuri, Hocquenghem
1960Reed-Solomon-CodesReed, Solomon

Reed-Solomon-Codes

Reed-Solomon-Codes (RS-Codes) [3,19,16] entwickelt von Reed und Solomon im Jahre 1960, sind ein Spezialfall von linearen Block-Codes. Eine genaue Einteilung ist durch folgende Untermengen-Darstellung gegeben:

RS-CodesBCH-Codeszyklische Codeslineare Block-Codes

RS-Codes sind wohl die industriell am bedeutendsten FEC-Codes, da sie eine Reihe von hervorragenden Eigenschaften besitzen. Sie sind sogenannte Maximum Distance Separable (MDS) Codes, d.h. sie besitzen eine maximal mögliche "minimale Hamming-Distanz" dmin = n-k+1 zwischen allen Codewörtern, und können somit bis zu n-k Fehler erkennen bzw.⌊(n-k)/2⌋ Fehler korrigieren. Beim BEC kann also ein FEC-Block bereits nach irgendwelchen erhaltenen k Werten rekonstruiert werden, was natürlich eine optimale Eigenschaft ist! Hierzu sei die Effizienz eines FEC-Codes definiert:

Effizienz = (# Datensymbole) / (# Symbole nötig für Dekodierung).

RS-Codes haben also eine Effizienz von 1.

Bei der Enkodierung werden die redundanten Daten durch (Lagrange-)Interpolation über die gegebenen k Datenwerte berechnet. Dazu sei das Polynom

P(x) = c0+c1x+...+ck-1xk-1

so gewählt, daß P(0) ≡ d0, ..., P(k-1) ≡ dk-1, wobei d0 bis dk-1 die ursprünglichen k Datenwerte sind. Die enkodierten Werte sind dann P(0), ..., P(n-1). RS-Codes sind somit systematische Codes.

Die Dekodierung beim BEC läuft analog zur Enkodierung ab, indem über k (korrekt) erhaltene Werte interpoliert wird, um so die fehlenden zu erhalten. Die Fehlerkorrektur beim BSC ist um einiges komplizierter, und beinhaltet die Syndrom-Berechnung, das Suchen der Fehlerpositionen und das Finden der korrekten Werte, deren Berechnungen im wesentlichen auf die Lösung eines Gleichungssystems hinauslaufen. Es ist interessant zu bemerken, daß die dafür nötigen Algorithmen erst um einige Zeit später entwickelt wurden (Berlekamp-Massey, 1968, und Chiensuche, 1964).

Die in der Praxis eingesetzten Algorithmen besitzen eine Kodier-Komplexität von O(n log n) und eine Dekodier-Komplexität von O(n2). (Über FFT-Techniken kann eine Dekodier-Komplexität von O(n log2n log log n) erreicht werden - mit allerdings in der O-Notation versteckten relativ großen Konstanten. [1]) Aufgrund der quadratischen Komplexität und der komplizierten Berechnungen (GF-Arithmetik) beträgt die maximale praktikable Blocklänge 255.

Aufgrund der oben beschriebenen Eigenschaften werden RS-Codes zahlreich eingesetzt, unter anderem für:

  • Speichersysteme
  • Wireless- und Mobilkommunikation
  • Satellitenkommunikation
  • Digitales Fernsehen
  • ADSL
  • CDs

Tornado-Codes

Gallager-Codes

Die im Jahre 1963 von Gallager im Rahmen seiner Dissertation am MIT entwickelten Gallager-Codes bilden den Anfang in der Entstehungsgeschichte der Tornado-Codes [4,7,13,17]. Gallager-Codes basieren auf bipartiten, regulären Graphen. Auf der linken Seite des Graphen befinden sich die Daten- sowie Paritätsbits. Jeweils q dieser Bits werden dann zufällig ausgewählt und mit einem der rechten Knoten verknüpft, wobei die Bits so gewählt werden, daß sich deren Summe modulo 2 zu 0 ergibt. Der Knotengrad ist dabei auf jeweils jeder Seite konstant. Hier ist eine Darstellung eines Gallager-Codes als bipartiter Graph:

In dieser Form sind Gallager-Codes leicht als lineare Codes darstellbar. Die Parity-Check-Matrix H ergibt sich somit zu

H = [D|P] = 011111 0100
1110000111
1001101110
0101111001
1010011011
.

In jeder Zeile befinden sich dabei q und in jeder Spalte p Einsen, wobei q der rechte und p der linke Knotengrad ist. Die Gesamtanzahl der Einsen entspricht dann der Anzahl der Kanten in der Darstellung als bipartiter Graph. Da die Anzahl der Kanten im allgemeinen relativ gering ist, ist die Parity-Check-Matrix dünn besetzt, weshalb diese Codes auch als Low-Density Parity-Check (LDPC) Codes bezeichnet werden. Für das Lösen von Gleichungssystemen mit dünn besetzten Matrizen existieren spezielle (schnellere) Algorithmen, was wohl eine der Intentionen Gallagers bei diesen Codes war. Die Kodierung ist hingegen kompliziert, da zur Berechnung der Generatormatrix ein lineares Gleichungssystem gelöst werden muß, und diese Matrix hingegen dicht besetzt ist, weshalb eine volle Matrixmultiplikation mit den Daten vollzogen werden muß. Beide diese Schritte sind extrem zeitaufwendig.

Gallager-Codes sind keine optimalen Codes. Insbesonders ergibt sich durch die zufällige Verknüpfung der Knoten eine variable Effizienz, die mit einer ins Unendliche steigenden Blocklänge konvergiert. Dies macht Gallager-Codes erst für große Blocklängen einsetzbar.

Aufgrund der großen Datenmengen, der komplizierten Berechnung und der Erfindung der Reed-Solomon-Codes zur selben Zeit wurden Gallager-Codes für etwa 30 Jahre vergessen, bis sie 1995 von MacKay und Neal wiederentdeckt wurden und seitdem einer ständigen Weiterentwicklung unterstehen. Der endgültige Durchbruch wurde 1997 durch Luby, Mitzenmacher, Shokrollahi, Spielman und Stemann mit ihrer Publikation "Practical Loss-Resilient Codes" [1] erzielt. Aus dieser Arbeit gehen die sogenannten Tornado-Codes hervor.

Tornado-Codes

Tornado-Codes [1] sind, wie Gallager-Codes, systematische FEC-Codes für große Blocklängen. Das zugrundeliegende Kanalmodell dieser Codes ist der Binary Erasure Channel (Fehler sind also gleichverteilt). Im Unterschied zu Gallager-Codes beruht die Konstruktion aber nicht auf bipartiten, regulären Graphen, sondern auf bipartiten, irregulären Graphen, deren Struktur extrem wichtig ist.

Tornado-Codes können in O(n ln\(1/ε)) Zeit en- und dekodiert werden, wobei ε eine beliebig gewählte positive Konstante ist. Die maximale zuverlässige Coderate, also die Rate, bei der die FEC-Block-Fehlerwahrscheinlichkeit mit steigender Blocklänge gegen 0 geht, beträgt dann 1-p/(1- ε), wobei p die Fehlerwahrscheinlichkeit des BEC ist. Über den Parameter ε kann dieser Wert beliebig nahe an die Coderate des Kanals heranreichen, womit Tornado-Codes nahezu optimale Codes (also "fast" MDS-Codes) mit einer Effizienz von etwa 1/(1+ ε) werden.

Aufgrund der linearen Komplexität und der relativ einfachen Berechnung sind Tornado-Codes sehr schnell, und auch die prinzipiellen Algorithmen von En- und Dekodierer sind einfach.

Konstruktion von Tornado-Codes

Bei der Konstruktion von Tornado-Codes werden nun die Paritätsbits der Gallager-Codes auf die rechte Seite des bipartiten Graphen gesetzt und als Checkbits betrachtet. Auf der linken Seite des Graphen befinden sich dann n Datenbits und auf der rechten Seite β n Checkbits ( β<1).

Bei der Kodierung werden die Checkbits durch Bildung der Summe (XOR) aller benachbarten Datenbits erzeugt.

Bei der Dekodierung kann ein fehlendes Datenbit rekonstruiert werden, wenn der Wert eines Checkbit und aller außer einem benachbarten Datenbit bekannt sind, indem das fehlende Datenbit durch die Summe (XOR) des Checkbits und der bekannten Datenbits ermittelt wird.

Das Ziel des gesamten Dekodierungsvorganges ist, daß wiederholte Dekodierschritte alle fehlenden Datenbits rekonstruieren. Dies soll funktionieren, wenn höchstens (1- ε) β n Datenbits fehlen. Indem bei jedem Dekodierschritt die "dekodierten" (verwendeten) Kanten entfernt werden, erhält man für die Dekodierung wie für die Kodierung eine lineare Komplexität in der Anzahl der Kanten. Knoten, die durch die Entfernung der Kanten den Grad 0 erhalten, werden ebenfalls als entfernt betrachtet.

Mit dem bisherigen Prinzip können fehlende Datenbits mithilfe der Checkbits rekonstruiert werden, aber wie können fehlende Checkbits ermittelt werden (und zwar so, daß sie zur Rekonstruktion von anderen Datenbits beitragen können)? Dies wird möglich, wenn die Graphen kaskadiert werden, der Code also rekursiv eingesetzt wird, sodaß sich eine Reihe von Codes C(B0), ..., C(Bm) über die Graphen B0, ..., Bm ergibt. Der erste Graph B0 erhält dabei wie gehabt als Input (also für die linken Knoten) die n Datenbits. Die Checkbits eines jeden Graphen Bi dienen dann als Input für den jeweiligen darauffolgenden Graphen Bi+1. Somit besitzt jeder Graph Bi βin linke und βi+1n rechte Knoten. Dies wird nun so oft rekursiv fortgesetzt, bis βi+1n≤√n. Für diese letzten Checkbits kann dann ein gewöhnlicher Erasure-Correcting Code C mit Coderate 1- β eingesetzt werden, der bei bis zu einem Verlust von β Prozent alle Daten mit hoher Wahrscheinlichkeit rekonstruieren kann.

Unter der Voraussetzung, daß C in O(n2) Zeit en- und dekodiert werden kann, ergibt sich mit

O((√n)2) = O(n)

eine lineare Komplexität. Ein möglicher Kandidat für den Code C ist der Reed-Solomon Erasure-Correcting Code.

Der gesamte Code (B0, ..., Bm, C) ist somit ein Code mit n Datenbits und

i=1m+1 βin+βm+2n/(1-β) = n (β / (1-β))

Checkbits, und besitzt somit eine Coderate von 1-β. Wenn jeder Sub-Code bei einem maximalen Verlust von β(1-ε) Prozent der Daten mit hoher Wahrscheinlichkeit dekodiert werden kann, dann kann der gesamte Code bei einem maximalen Verlust von β(1-ε) Prozent der Daten mit hoher Wahrscheinlichkeit dekodiert werden. Das Ziel ist nun das Finden von entsprechenden Sub-Graphen.

Analyse des Dekodier-Vorganges

Wie im letzten Kapitel beschrieben, kann der Dekodiervorgang nur fortgesetzt werden, wenn es auf der rechten Seite eines Sub-Graphen ein Checkbit gibt, für das genau ein benachbartes Datenbit fehlt, d.h. es gibt einen rechten Knoten mit Grad 1. In diesem Fall wird das fehlende Datenbit rekonstruiert (durch das Checkbit ersetzt), alle vom linken Knoten ausgehenden Kanten entfernt (dabei wird jeweils wieder das XOR des rekonstruierten Datenbits mit den angrenzenden Checkbits gebildet) und abschließend der linke und rechte Knoten entfernt. Dieser Dekodierschritt wird nun wiederholt, solange es rechte Knoten mit Grad 1 gibt. Der gesamte Dekodiervorgang ist erfolgreich, wenn alle Knoten auf der linken Seite entfernt wurden.

Wir wollen nun zeigen, daß es unter der Vorraussetzung eines maximalen Verlustes von β(1-ε) Prozent und solange linke Knoten vorhanden sind, es in diesem Graphen stets einen rechten Knoten mit Grad 1 gibt. Da dies auf Wahrscheinlichkeitsrechnung beruht, ist nur das Grenzverhalten analysierbar.

Dazu definieren wir eine Kante mit linkem (rechtem) Grad i als eine Kante, die an einen linken (rechten) Knoten mit Grad i angrenzt. 1,..., λm) sei dann der Vektor, der den prozentualen Anteil an Kanten mit linkem Grad 1...m angibt. Analog dazu sei 1,..., ρm) der Vektor, der den prozentualen Anteil an Kanten mit rechtem Grad 1...m angibt.

Bei jedem Dekodier-Subschritt wird nun 1 von E Kanten entfernt:

Δt := 1/E = 1 Zeiteinheit = 1 Dekodierschritt,     t = 0...1

li(t) sei der Anteil an Kanten mit linkem Grad i zur Zeit t. Analog dazu sei ri(t) der Anteil an rechten Kanten mit Grad i zum Zeitpunkt t. Der Anteil aller Kanten e(t) zum Zeitpunkt t ergibt sich als

e(t) := ∑li(t) = ∑ri(t)

Weiters wird bei jedem Dekodierschritt ein rechter Knoten mit Grad 1 gewählt, und der benachbarte linke Knoten und alle dessen Kanten entfernt. Die Wahrscheinlichkeit dafür, daß der linke Knotengrad genau i ist, beträgt li(t)/e(t), und in diesem Fall werden i Kanten vom Grad i entfernt. Dies ist durch die folgende Gleichung ausgedrückt:

Li(t+Δt) - Li(t) = - i · li(t)/e(t),

wobei Li(t) die Anzahl der Kanten mit linkem Grad i bezeichnet, und somit Li(t) = li(t) · E = li(t) / Δt. Da nur das Grenzverhalten analysiert werden kann, lassen wir die Anzahl der Kanten nach unendlich gehen: E→∞ und somit Δt→0.

limΔt→0 Li(t+Δt) - Li(t) = limΔt→0 (li(t+Δt) - li(t)) / Δt = (dli(t) / dt = - i · li(t)/e(t)

Diese Differentialgleichung kann leichter gelöst werden, indem man dt/e(t) durch dx/x substituiert. Mit der Anfangsbedingung li(t=0) = δ λi, wobei δ der Anteil an fehlenden (bzw. verbleibenden) linken Knoten ist, ergibt sich für den Anteil an linken Kanten mit Grad i

li(x) = δ λixi,     x∈[1,0)

Das Lösen der Differentialgleichungen für ri(x) bzw. r1(x) ist relativ kompliziert. Das Ergebnis für r1(x) wird mit Hilfe der sogenannten "degree sequence functions" (Polynome) λ(x) = δ λixi-1 und ρ(x) = δ ρixi-1 ausgedrückt:

r1(x) = δ λ(x) (x - 1 + ρ(1 - δ λ(x))).

Dieser Anteil an rechten Kanten mit Grad 1 soll nun stets größer als 0 sein, für alle x ∈ [1,0). Die Ungleichung aufgelöst führt nun zur zentralen Bedingung für einen erfolgreichen Dekodierungsprozeß:

ρ(1 - δ λ(x)) > 1 - x,    ∀ x ∈ [1,0).

Unter der Berücksichtigung, daß diese Berechnungen das grenzwertige Verhalten beschreiben, besagt dies nun folgendes:

Unter der Voraussetzung, daß diese zentrale Bedingung erfüllt ist, geht mit steigender Blocklänge die Wahrscheinlichkeit, daß alle Daten rekonstruiert werden können, gegen 1!

Umgekehrt – und vielleicht eindrucksvoller – gilt:

Ist diese Bedingung verletzt, so geht die Wahrscheinlichkeit einer erfolgreichen Dekodierung gegen 0!

Da diese Ungleichung nur den grenzwertigen Fall exakt beschreibt, bleiben in der Praxis oft ein paar wenige linke Knoten übrig. Bleiben jedoch maximal η% Knoten übrig, für ein η > 0, und ist λ1 = λ2 = 0, dann terminiert der Dekodierungsprozeß erfolgreich (siehe [1]).

Reguläre vs. irreguläre Graphen

Reguläre Graphen

Befinden sich auf der linken Seite des Graphen n Knoten mit Grad d, und sind auf der rechten Seite β n Knoten, so besitzen diese (notwendigerweise) Grad d/β. Die "degree sequence functions" ergeben sich dann zu λ(x) = xd-1 und ρ(x) = xd/ β-1. Ist nun d ≥ 3, dann ist die zentrale Bedingung nur erfüllt, wenn

δ ≤ 4 · (1 - (1/(d-1))1/(d/β-1)).

Es ist leicht zu erkennen, daß sich das Maximum für die für eine erfolgreiche Dekodierung maximal akzeptable Verlustrate δ mit d = 3 ergibt. Als Beispiel sei β = 0.5 gewählt, womit die maximal akzeptable Verlustrate höchstens 0.43% betragen darf. Um also einen Block rekonstruieren zu können, muß mindestens die 1.14-fache Originaldatenmenge erhalten worden sein – ein Wert, der weit vom optimalen Wert 1 entfernt ist.

Irreguläre Graphen

Sei die Verteilung der linken Grade ("left degree sequence") durch folgende "Truncated Heavy Tail"-Verteilung mit Parameter d gegeben:

λi = 1 / (H(d)(i-1)),     i = 2...d+1

mit H(d) := i=1d 1/i, also der harmonischen Reihe bis 1/d. Der durchschnittliche linke Knotengrad ergibt sich zu al = H(d)(d+1)/d ~ ln(d).

Die rechten Grade ("right degree sequence") seien nach Poisson verteilt (die Potenzreihe der Verteilung kann dabei annähernd als Polynom betrachtet werden):

ρi = (e αi-1) / (i-1)!,     i ≥ 1.

Der durschnittliche rechte Knotengrad errechnet sich dann zu ar = α eα / (eα-1), wobei α so gewählt wird, daß ar = al.

Mit den soeben angegebenen Verteilungen der Kantengrade ist die zentrale Bedingung genau dann erfüllt, wenn δ ≤ β / (1+1/d). Die maximal akzeptable Verlustrate wird somit durch den Parameter d bestimmt. Da sich mit wachsendem d der Code immer mehr der Shannon-Grenze annähert, ergibt sich hiermit ein asymptotisch optimaler Code! Welches d nun gewählt wird, muß gegenüber der (De-)kodierkomplexität abgewogen werden, denn d bestimmt auch die Anzahl der Kanten durch n·al ~ n·ln(d). Die Komplexität für die En- und Dekodierung beträgt also O(n ln(d)).

Wie im letzten Kapitel angemerkt, sollte für eine erfolgreiche Dekodierung λ2 = 0 sein, was hier nicht der Fall ist. In [1] ist jedoch folgende Abhilfe beschrieben: Zuerst wird der soeben beschriebene Code über die n linken und (β-γ)n rechte Knoten konstruiert. Ein weiterer Graph wird dann über die n linken und γn rechten Knoten gelegt, wobei die linken Knoten Grad 3 haben und die Kanten zufällig mit den γn rechten Knoten verbunden werden. Der Parameter γ ist dabei ein noch zu bestimmender.

Mit β = 1-R und ε := 1/d kann ein so konstruierter Code für eine beliebige Coderate R und ein ε > 0 bei großen Blocklängen mit sehr hoher Wahrscheinlichkeit alle Fehler korrigieren, sofern höchstens (1-R)(1-ε) Prozent der Daten fehlen, und zwar in einer Zeit proportional zu n ln(1/ε).

Effizienz von irregulären Graphen

Effizienz im Verhältnis zum durchschnittlichen Knotengrad (aus [18]):

Resultate aus "Practical Loss-Resilient Codes":

durchschnittl. linker KnotengradRate
1/22/33/44/59/10
5.700.9650.9780.9840.9870.994
6.820.9770.9870.9900.9930.996
8.010.9860.9920.9930.9950.998

Gegenüberstellung von Tornado- und Reed-Solomon-Codes

Die folgenden Tabellen sollen in einer Gegenüberstellung einen kurzen Überblick mit den wichtigsten Eigenschaften von Tornado-Codes und Reed-Solomon-Codes geben.

Tornado-CodeReed-Solomon-Code
Effizienz~1/(1+ε)1
BerechnungXORkomplexe GF-Arithmetik
KodierungO(n ln(1/ε))O(n log n)
DekodierungO(n ln(1/ε)O(n2)
Blocklängegroß – sehr großklein (≤255)

Ausführungszeiten gemessen auf einer Sun 167 MHz UltraSPARC 1 mit 64 MB RAM und Solaris 2.5.1 [9]:

GrößeEnkodierzeit (sec.), 1K-PaketeDekodierzeit (sec.), 1K-Pakete
Reed-SolomonTornadoReed-SolomonTornado
250 KB4.60.062.060.06
500 KB190.128.40.09
1 MB930.2640.50.14
2 MB4420.531990.19
4 MB17171.068000.40
8 MB69942.1331660.87
16 MB308024.33138291.75

Eigene Implementation von Tornado-Codes

Header - Funktionen

Die hier präsentierten Funktionen stellen die Schnittstelle für die eigene Implementation von Tornado-Codes dar und stammen direkt aus der Header-Datei des Quelltextes.

/* pass the message length, the code rate 1-beta and the efficiency parameter d */ Tornado( unsigned int msg_len, double beta, unsigned int d ); /* returns the block length of the code */ unsigned int BlockLength() const; /* encode a string of size BlockLength(), with the first part of size message length set to the message data */ void Encode( char *msg ); /* feed a new "bit" at position "pos" to the decoder returns the # of symbols not decoded */ unsigned int Decode( char *msg, char bit, unsigned int pos ); /* reset the decoder for a new decoding process this leaves the current graph structure intact */ void Reset();

Header - Datenstrukturen

Diese Datenstrukturen entstammen ebenfalls der Header-Datei, sind aber nur klassenintern verwendbar (privat). Sie sollen darstellen, wie Knoten und Kanten des Graphen intern repräsentiert werden. Des weiteren geben Sie Aufschluß über den Speicherverbrauch des Codes.

/* array of all Vertices with edge lists going away left and right */ struct Vertex : list2<Vertex>::node { list2<Edge> left_edges; int left_degree_remaining; int left_degree_total; list2<Edge> right_edges; int right_degree_remaining; int right_degree_total; } *vertices; /* array of all Edges with pointers to its adjacent (buddy) edge and vertex */ struct Edge : list2<Edge>::node { Edge *buddy_edge; Vertex *buddy_vertex; } *edges;

Aufbau der wichtigsten Funktionen

Die Encode()-Funktion:

  1. setze initial alle Checkbits auf 0
  2. für alle rechten Kanten (das sind jeweils die zweiten im edge-Array) wird zum zugehörigen (angrenzenden) Knotenwert der Wert des zugehörigen Knotens der linken Kante addiert

Die Decode()-Funktion:

  1. das erhaltene Bit für eine Stelle pos wird zum aktuellen Wert addiert
  2. war der Knoten an dieser Stelle bereits rekonstruiert, dann überspringe Punkt 3.
  3. betrachte rechte Knoten:
    - addiere Bit zu jedem benachbarten rechten Knoten und lösche die linken und rechten Kanten dorthin
    - bekommt dadurch ein rechter Knoten Grad 0, oder Grad 1 unter der Bedingung, daß sein Wert bereits rekonstruiert wurde, dann gib ihn in eine Liste für dekodierbare Knoten
    - markiere Knoten als rekonstruiert
  4. betrachte linke Knoten:
    - gibt es nur noch einen benachbarten linken Knoten, dann addiere das Bit zu diesem Knoten, lösche die Kante(n) dorthin, und setze als neues erhaltenes Bit den Wert des Check-Knotens
  5. 2.–4. wiederholen, bis es keinen rechten Knoten mit Grad 1 mehr gibt
  6. Knoten aus der Liste der dekodierbaren Knoten nehmen, und den Wert dieses Knotens als neues erhaltenes Bit setzen
  7. 1.–6. wiederholen, bis die Liste leer ist

Der Konstruktor – Konstruktion des Graphen:

  1. erstelle Pool von rechten Kanten:
    - erstelle zuerst die minimale Anzahl an Kanten für alle rechten Knoten
    - dann wird zufällig ein Anteil von Knoten der Größe exkludiert, die dem Anteil an Knoten entspricht, die genau den vorgegebenen Knotengrad haben
    - die restlichen Knoten brauchen zusätzliche Kanten, wobei deren Anzahl als Differenz zur vorigen Anzahl an Kanten berechnet wird
    - wiederholen, bis keine Knoten mehr übrig sind
  2. erstelle Pool von linken Knoten:
    - erstelle zuerst die minimale Anzahl an Kanten für alle linken Knoten
    - verknüpfe diese linken Kanten zufällig mit rechten
    - entferne zufällig soviele linke Knoten aus dem Pool, wie durch den minimalen linken Knotengrad bestimmt ist
    - die restlichen Knoten brauchen zusätzliche Kanten, wobei deren Anzahl als Differenz zur vorigen Anzahl an Kanten berechnet wird
    - wiederholen, bis keine rechten Kanten mehr übrig sind
  3. wiederhole für alle Sub-Graphen

Warum wird der Graph auf diese Weise konstruiert? Die Anzahl an Kanten bzw. Knoten ist eine reelle Zahl, und deren Diskretisierung führt zu Fehlern bei der Verteilung der Kanten auf die Knoten. Mit dem oben beschriebenen Algorithmus wird eine bessere Verteilung der Kanten erreicht, und Konfliktsituationen in der Art, daß es noch Knoten mit Grad 0 gibt, aber keine Kanten mehr zu verteilen, werden vermieden.

Performance

Mit diesem Algorithmus wurden relativ gute Ergebnisse bei Datenlängen bis zu ~20000 Zeichen erzielt. Bei einem Test mit einer Datenlänge von 10000 Zeichen, einer Coderate von 1/2 und d=10 lag die durchschnittliche Effizienz in etwa bei 91%, womit die theoretische Voraussage ziemlich genau erfüllt wurde.

Anwendungen

ARQ vs. FEC

In vielen Netzwerken, wie auch dem Internet, wird traditionell eine zuverlässige Kommunikation durch Automatic Repeat Request (ARQ) erreicht. ARQ ist gut bei Übertragungen über Kanäle mit variabler Kapazität, aber schlecht oder gar nicht anwendbar in einer Reihe von Situationen. Viele Empfänger verursachen eine große Server- und Netzwerklast durch großen Paket-Puffer- und Bandbreitenverbrauch und Congestion. In Fällen, wo der Rückkanal entweder begrenzt, zu langsam oder gar nicht verfügbar ist, wie in der Satelliten- und Weltallkommunikation, ist ARQ gar nicht anwendbar. In Netzwerken mit großer Verzögerung ist weiters zu bedenken, daß diese durch ARQ oft noch viel größer bzw. zu groß werden [8].

Die Lösung dieser Probleme besteht in der Verwendung von FEC-Codes bzw. Hybriden. Dabei sind nur Erasure-Correcting Codes erforderlich, denn erhaltene Pakete sind stets korrekt (die Integrität wird durch CRC überprüft), und Paketverluste entsprechen Erasures. Der Einsatz von FEC anstelle von ARQ wird unter anderem in Reliable Multicast (RFC 3453) und ALC (RFC 3450-1) vollzogen [10,4]. Bei Hybrid-Techniken gibt es grundsätzlich die Möglichkeit, die Daten von vornherein mit FEC zu versehen und erst bei zu vielen Fehlern ARQ anzuwenden, oder die Daten zuerst ohne FEC zu verschicken und bei ARQ dann nur Checkbits zurückzusenden [8].

Softwareverteilung im Internet

Ein gutes Anwendungsgebiet für Tornado-Codes ist die Softwareverteilung in großen Netzwerken wie dem Internet [9,15,18]. Ein solches ist charakterisiert durch 1 Sender, aber viele Empfänger (Millionen), und dem Problem der Verteilung von großen Datenmengen. Als Beispiele seien genannt: neue Software (Updates), Finanzinformationen, Datenbankreplikation, Audio-/Video-Übertragungen, Zugriff auf populäre Webseiten.

Standardmäßig werden im Internet Punkt-zu-Punkt-Verbindungen erstellt. Dies bietet folgende Vorteile:

  • Download zu jeder Zeit
  • Download kann unterbrochen und sofort wieder aufgenommen werden
  • Paketverlust wird mit ARQ entgegnet
  • Effizienz ist fast optimal

Die Nachteile einer Punkt-zu-Punkt-Verbindung sind jedoch

  • hohe Serverlast (durch viele Paket-Puffer und Retransmission-Timer)
  • hohe Netzwerklast (durch ARQ)
  • schlechte Skalierung (wenig geeignet bei vielen Benutzern)

Dem gegenüber stehen Multicasts bzw. Broadcasts. Diese invertieren das Problem der Punkt-zu-Punkt-Verbindungen, indem Vor- zu Nachteilen werden...:

  • Empfänger können nicht die Download-Zeit bestimmen
  • Empfänger können nach einer Unterbrechung den Download nicht automatisch fortsetzen
  • ARQ ist nicht skalierbar
  • Effizienz ist nicht optimal

...und Nach- zu Vorteilen werden:

  • niedrige Serverlast
  • niedrige Netzwerklast
  • gute Skalierung (ohne ARQ)

Um den Problemen bei Multicasts und Broadcasts zu entgegnen, wird traditionell ein sogenanntes Datenkarussell angewendet, das anstelle von ARQ auf FEC setzt. Dabei werden zusätzlich zu den k Datenpaketen n-k Pakete mit Checkbits gesendet. Bei einem optimalen Code genügen dann irgendwelche k Pakete, um die Originaldaten rekonstruieren zu können. Die Pakete werden dann zyklisch gesendet, wodurch der Empfänger zu jeder Zeit den Download beginnen, unterbrechen und fortsetzen kann.

Bisher wird als FEC-Code ein Reed-Solomon-Code verwendet. Da dieser Code aufgrund der Komplexität aber nur über eine kleine Anzahl an Paketen angewendet werden kann (255), muß das Objekt (Datei) in mehrere Blöcke unterteilt werden. Dabei wird zusätzlich ein Interleaving der Blöcke verwendet, um einen besseren Schutz gegen Burst Errors zu erreichen. Das Problem auf Empfängerseite besteht nun darin, Pakete für genau die Blöcke zu erhalten, die noch nicht dekodiert werden können. Dieses Problem ist das bekannte "Coupon Collector's Problem".

Mit Tornado-Codes kann nun eine FEC über das ganze Objekt erstellt werden, und es genügen dann dem Empfänger irgendwelche k(1+ε) Pakete, um die Originaldaten rekonstruieren zu können. Dabei können die Daten in linearer Zeit (bei fixem ε) en- und dekodiert werden. Dabei ist zu bemerken, daß das Internet kein BEC ist, wie für Tornado-Codes gefordert, sondern ein Burst-Erasure Channel. Dies kann man jedoch elegant umgehen, indem die Pakete in zufälliger Reihenfolge verschickt werden [1].

Ein Datenkarussell mit Tornado-Codes vereint im wesentlichen die Vorteile der Punkt-zu-Punkt- und Multicast-Verbindungen, und sind hiermit zusammengefaßt:

  • Download zu jeder Zeit
  • Download kann unterbrochen und sofort wieder aufgenommen werden
  • mäßiger Paketverlust ist kein Problem
  • Effizienz ist fast optimal
  • niedrige Netzwerklast
  • gute Skalierung

Zwar kann man auch den Wegfall des hohen Speicherverbrauchs für Paketpuffer und Retransmission Timer als Vorteil betrachten, jedoch verursachen auch Tornado-Codes einen hohen Speicherbrauch durch die Berechnung der FEC über das ganze Objekt [7].

Kommerzialisierung der Tornado-Codes

Tornado-Codes sind von der Firma "Digital Fountain" patentiert, die von Luby et al. gegründet wurde [10,9,15]. Diese Codes finden bereits Einsatz in vielen großen Firmen, unter anderem Cisco und Sony.

Weiterentwicklungen

Tornado-Codes haben bereits interessante Weiterentwicklungen erfahren. So stehen Tornado- bzw. LDPC-Codes für den BSC in Forschung, und weiters sind aus ihnen sogenannte ratenlose Codes hervorgegangen, wie den von Luby im Jahre 1998 vorgestellten LT-Codes (Luby-Transform-Codes) [12,10], die ebenfalls von Digital Fountain patentiert sind, und den Online Codes [11], die 2002 von Maymounkov veröffentlicht wurden. Ratenlose Codes besitzen keine vorgegebene Coderate im eigentlichen Sinn, denn diese können immer neue und verschiedene FEC-Blöcke erzeugen, die alle für die Dekodierung eines Objektes verwendet werden können.

Literatur

  1. M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, D. A. Spielman, V. Stemann, "Practical Loss-Resilient Codes", Proceedings of the 29th ACM Symposium on Theory of Computing, 1997
  2. S. Lin, D. J. Costello Jr., Error Control Coding: Fundamentals and Applications, Prentice Hall, 1983
  3. T. R. N. Rao, E. Fujiwara, Error-Control Coding for Computer Systems, Prentice Hall, 1989
  4. Vincent Roca, Zainab Khallouf, Julien Labouré, "Design and evaluation of a Low Density Generator Matrix (LDGM) large block FEC codec", presented at the Fifth International Workshop on Networked Group Communication, 2003
  5. —, "Bell Labs celebrates 50 years of Information Theory", http://www.lucent.com/minds/infotheory/docs/history.pdf
  6. D. Johnson, "Noisy Channel Coding Theorem", The Connexions Project
  7. A. C. Snoeren, "On The Practicality of Low-Density Parity-Check Codes", http://nms.lcs.mit.edu/~snoeren/papers/area-exam.pdf, 2001
  8. A. J. McAuley, "Reliable Broadband Communication Using A Burst Erasure Correcting Code", presented at ACM SIGCOMM, 1990
  9. J. W. Byers, M. Luby, M. Mitzenmacher, A. Rege, "A Digital Fountain Approach to Reliable Distribution of Bulk Data", Digital Equipment Corporation SRC Technical Note 1998-003, 1998
  10. M. Luby et al., "The Use of Forward Error Correction in Reliable Multicast", IETF RMT, RFC 3453, 2002
  11. P. Maymounkov, "Online Codes", NYU, Technical Report TR2002-833, 2002
  12. C. E. Shannon, "A Mathematical Theory of Communication", The Bell System Technical Journal, 1948
  13. A. Shokrollahi, "An Introduction to Low-Density Parity-Check Codes"
  14. S. Robinson, "Coding Theory Meets Theoretical Computer Science", SIAM News, Vol. 34
  15. S. Robinson, "Beyond Reed-Solomon: New Codes for Internet Multicasting Drive Silicon Valley Start-up", SIAM News, Vol. 35
  16. —, "Reed-Solomon Codes", http://www.4i2i.com/reed_solomon_codes.htm
  17. J. Sun, "An Introduction to Low Density Parity Check (LDPC) Codes", West Virginia University, Wireless Communication Research Laboratory, Seminar Series, 2003
  18. M. Mitzenmacher, "Tornado Codes, with Applications to Reliable Multicast"
  19. M. Mitzenmacher, Lecture Notes on Course CS 222
  20. D. MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press (http://www.inference.phy.cam.ac.uk/mackay/itila/), 2003