Reed-Solomon Erasure Correction
Überlegungen zu Parameterwahl und Effizienz
Das vorliegende Dokument ist aus einem nach HTML konvertierten und
anschließend (erheblich) bearbeiteten Mathematica-Notebook entstanden
und beschreibt die Überlegungen im Hinblick auf eine vollständig
in Java implementierte "Forward Error Correction" auf der Basis einer
"Reed-Solomon Erasure Correction".
Die nachstehend vorgestellten Überlegungen wurden vom Autor als Mitarbeiter
der Abteilung "Projekte,
Kommunikationssysteme und BelWü-Entwicklung" am
Rechenzentrum der Universität
Stuttgart im Rahmen des EU Forschungsprojektes
MECCANO
angestellt und in diesem Kontext von der EU finanziert.
Bitte beachten Sie auch meine
Betrachtungshinweise und die
Liste der letzten Änderungen!
Themenübersicht
Die folgende Themenübersicht führt Sie unmittelbar zu der von Ihnen
gewünschten Information - klicken Sie einfach auf das Thema Ihrer Wahl:
Die Themen im Einzelnen
Vorwort
Zuverlässige Multicast-Übertragungen lassen sich im Prinzip wie
folgt realisieren:
-
der Empfänger fordert beim Sender die erneute Übertragung
(Retransmission) aller verlorenen Pakete an oder
-
der Empfänger rekonstruiert verlorene Pakete mithilfe von redundanter
Information, die vom Sender erzeugt und ebenfalls verschickt wurde.
Das erstgenannte Verfahren ist äußerst robust, kostet aber Zeit
und kann (bei einer hohen Anzahl von Empfängern, die evtl. sogar ghz.
um "Retransmissions" bitten) zu einer Überlastung des Senders führen
(Sender Implosion).
Redundanz kann ihrerseits wieder auf zweierlei Art erzeugt werden:
-
durch mehrfaches Verschicken derselben Daten (vgl. NTE) oder
-
durch Verschicken von Prüfinformationen, die zur Rekonstruktion verlorener
Pakete genutzt werden können (vgl. RAT). Die Verfahren zur Gewinnung
dieser Prüfinformation können dabei von der Art der zu verschickenden
Daten unabhängig sein oder aber bestimmte Eigenheiten dieser Daten ausnutzen
(wie z.B. im Falle von Audio-Datenströmen).
Die vorliegende kleine Studie untersucht (anhand von konkreten, aus
MBone-Messungen gewonnenen Daten) die Auswirkungen von "Reed-Solomon Erasure
Correction" (kurz: RSEC) Codes auf die Anzahl der erforderlichen
Retransmission-Anforderungen, bestimmt die Parameter von möglichst
einfachen, aber dennoch wirkungsvollen RSEC-Kodierungen und berechnet die
Eckdaten einer auf "table-lookup" basierenden RSEC-Implementierung.
Die Frage nach dem Sinn
Anhand von Meßergebnissen soll jedoch zunächst einmal festgestellt
werden, ob die Anzahl der Retransmission-Anforderungen beim derzeitigen
Paketverlust-"Verhalten" durch den Einsatz von RSE-Codes überhaupt gesenkt
werden kann.
Eine erste Interpretation der Meßergebnisse
Das Java-Programm "RTP_02" des Autors schreibt abwechselnd die Anzahl
aufeinanderfolgender empfangener bzw. verlorener Pakete in die Datei
"RTP_02.data":
Zur besseren Handhabung wird LossInfo nun in je eine Liste aller
empfangenen und aller verlorenen Paketfolgen zerlegt (Achtung: die
ReceptionList enthält ein Element mehr als die
LossList):
Daraus läßt sich leicht der prozentuale Anteil der verlorenen
Pakete ermitteln:
Ein "Burst" sei eine Kette aufeinanderfolgender verlorener Pakete. Jeder
Burst hat eine bestimmte Länge, für die spätere Auswertung
wird die max. Burst-Länge in der LossList benötigt:
Interessant ist nun, wie häufig Bursts einer bestimmten Länge
auftreten:
Kurze Bursts sind offensichtlich sehr viel häufiger als lange. Dies
läßt vermuten, daß ein Verfahren, welches kurze Bursts
"übersteht", bereits einen großen Teil aller in der Praxis
auftretenden Verlustfälle behandeln kann - in allen übrigen
Fällen müssen die verlorenen Pakete beim Sender erneut angefordert
werden.
Kurze Bursts sind außerdem einfacher zu korrigieren als lange. Es stellt
sich deshalb die Frage, wie hoch der Anteil der Bursts bis zu einer bestimmten
Länge an der Gesamtzahl aller Bursts ist:
Wenn man einen prozentualen Anteil Percentage aller Fälle behandeln
will, sollten demnach Bursts bis zu folgender Länge berücksichtigt
werden:
Die RSE-Kodierung als "Black Box"
Für die vorliegende Studie ist es vollkommen ausreichend, die
Reed-Solomon-Kodierung als "black box" mit folgenden Eigenschaften zu betrachten:
-
ein RSE-Kodierer erzeugt Blöcke von jeweils BlockSize Symbolen
der Länge SymbolSize, von denen DataCount Symbole
echte Applikationsdaten enthalten und die restlichen ParityCount
Symbole für Prüfinformation reserviert sind;
-
ist bekannt, welches Datensymbol verlorengegangen ist, so reicht ein beliebiges
Prüfsymbol (aus dem gegebenen Übertragungsblock) aus, um dieses
Datensymbol zu rekonstruieren. ParityCount Prüfsymbole
genügen also, um genau soviele verlorene Datensymbole zu rekonstruieren;
Desweiteren gelten die folgenden Beziehungen:
-
2 <= SymbolSize <= 16 [Bit]
d.h., es können nur Symbole mit einer Größe von 2...16 Bit
verarbeitet werden. Größere Pakete müssen vor der Kodierung
in Folgen kleinerer Symbole zerlegt und die RSE- Kodierung unabhängig
vom Rest des Paketes für jedes Symbol aus dieser Folge separat
durchgeführt werden. Achtung: damit verlorene Pakete tatsächlich
wiederhergestellt werden können, müssen die einzelnen Symbole auch
wirklich aus unterschiedlichen Paketen stammen. Es macht keinen Sinn,
Blöcke mit Symbolen aus demselben Paket zu bilden!
-
BlockSize = 2^SymbolSize-1
d.h., die Wahl einer SymbolSize legt zugleich auch die zugehörige
BlockSize fest. Durch die Verwendung eines "verkürzten RSE-Kodes"
kann man jedoch auch Blöcke mit weniger Symbolen bilden: in diesem Fall
werden die "fehlenden" Symbole für Kodierung und Dekodierung als
Datensymbole z.B. mit dem Wert 0 angenommen, aber nicht mit übertragen.
-
ParityCount <= DataCount
aus mathematischer Sicht ist diese Annahme zwar nicht erforderlich, doch
sollen an dieser Stelle nicht mehr Prüfsymbole erzeugt werden, als
Datensymbole zu rekonstruieren sind.
Eine erneute Betrachtung der Meßwerte
Im Hinblick auf eine spätere RSE-Kodierung ist es wichtig zu wissen,
wieviele Pakete innerhalb eines bestimmten Blockes verloren gegangen sind.
Aus diesem Grund wird die in LossInfo beschriebene Paketfolge
(gedanklich) in Sequenzen von jeweils BlockSize Paketen zerlegt
und die Anzahl der in jedem Block verloren gegangenen Pakete berechnet. Um
das Ergebnis etwas allgemeiner zu halten, wird die Berechnung auch für
den Fall durchgeführt, daß der erste Block erst mit dem zweiten,
dritten, ..., oder (BlockSize-1)-ten gemessenen Paket beginnt. Alle
Resultate werden aufsummiert und anschließend wieder durch
BlockSize geteilt. Auf diese Weise läßt sich der
Einfluß eines "unglücklichen" Meßbeginns minimieren.
Achtung: das nachstehend implementierte Verfahren funktioniert anders als
eben beschrieben (und ist insbesondere effizienter), liefert aber dasselbe
Ergebnis.
Der Einfachheit halber sollen an dieser Stelle nur Block- und Burstlängen
von bis zu 16 Symbolen betrachtet werden:
Da ein RSE-Code mit ParityCount Prüfsymbolen alle Fälle
von bis zu ParityCount verlorenen Paketen behandeln kann, stellt
sich erneut die Frage, wie hoch der Anteil an "korrigierbaren" Paketverlusten
bei gegebener BlockSize und ParityCount ist:
Die oben genannte "Bedingung" ParityCount <= DataCount wurde
in Efficiency bislang noch nicht berücksichtigt. Dies wird
an dieser Stelle nachgeholt:
Auch an dieser Darstellung ist gut zu erkennen, daß bereits eine geringe
Anzahl von Prüfsymbolen (pro Block) einen großen Teil von
"Retransmissions" verhindern kann - selbst wenn die Blockgröße
erhöht (und damit der relative Overhead verringert) wird.
Der Einsatz von RSE-Kodierungen lohnt also auf jeden Fall.
Auf der Suche nach einem Verfahren
Das erklärte Ziel ist eine Implementierung von RSE-Kodierung und
-Dekodierung in Java - wobei beide Vorgänge möglichst wenig Zeit
in Anspruch nehmen dürfen. Aus diesem Grunde wird eine Realisierung
mithilfe von Table-Lookups angestrebt:
-
Kodierung
-
aus den zu kodierenden Daten wird eine Adresse generiert, an welcher in einer
Kodiertabelle die zu diesen Daten gehörenden Prüfinformationen
zu finden sind;
-
Dekodierung
-
Trivialfall
sind alle Datensymbole vorhanden, so wird die Dekodierung übersprungen
-
Korrekturfall
sind LossCount Datensymbole verlorengegangen, jedoch mindestens
ebensoviele Prüfsymbole vorhanden, so wird zunächst anhand der
Positionen der verlorenen Datensymbole sowie der zu verwendenden
Prüfsymbole ermittelt, um welchen "Verlustfall" es sich handelt. Aus
dieser Zahl, den vorhandenen Daten und genau LossCount
Prüfsymbolen wird nun wieder die Adresse errechnet, an der in einer
Dekodiertabelle die LossCount fehlenden Datensymbole zu finden sind.
-
Verlustfall
sind LossCount Datensymbole verlorengegangen und nicht mindestens
ebensoviele Prüfsymbole vorhanden, müssen die fehlenden Datensymbole
beim Sender neu angefordert werden.
Restriktionen durch die Art der Implementierung
Aus der Forderung, Kodierung und Dekodierung in Java als "Table-Lookup" zu
realisieren (und zwar möglichst effizient), ergeben sich eine Reihe
von Randbedigungen:
-
will man auf kompliziertere Strukturen verzichten, so bleiben nur Werte vom
Java-Typ byte, int, oder long für die Elemente
der Kodier- und Dekodiertabellen. Sollen darin (bei gegebener
SymbolSize) die Prüfsymbole bzw. rekonstruierten Datensymbole
untergebracht werden, so gilt die folgende Beziehung:
ParityBits := SymbolSize * ParityCount <= 64
-
die Adresse für die Kodiertabelle soll durch Aneinanderreihung der zu
kodierenden Datensymbole gewonnen werden, der Inhalt des ersten Symboles
werde dabei an der höchstwertigen Stelle plaziert. Bei gegebener
SymbolSize berechnet sich die erforderliche Anzahl von
Tabellenplätzen (EncoderLength) wie folgt:
DataBits := SymbolSize * DataCount
EncoderLength := 2^DataBits
-
zur Dekodierung sollen ebenfalls DataCount Symbole (Daten- oder
Prüfsymbole) herangezogen werden ("überzählige" Prüfsymbole
werden im Hinblick auf eine möglichst kleine Tabelle ignoriert).
Gleichzeitig muß aber auch die aktuelle Fehlersituation (abh. von der
Position der fehlenden Datensymbole sowie der zu verwendenden Prüfsymbole)
berücksichtigt werden. Eine kombinatorische Betrachtung (siehe Anhang)
führt dabei zu folgender Formel für die Anzahl der möglichen
Fehlerfälle:
CaseCount := Sum[
Product[(DataCount-(i-1))/i, {i,1,Losses}]
*
Product[(ParityCountCount-(j-1))/j,
{j,1,Losses}],
{Losses, 1, ParityCount}]
unter der Annahme ParityCount <= DataCount. Die Anzahl der Elemente
in der Dekodiertabelle (DecoderLength) beträgt somit
DecoderLength := (2^DataBits) * CaseCount
Will man den Platzbedarf (MemoryLimit) für beide Tabellen zusammen
auf einen bestimmten Wert beschränken (z.B. 1MByte) so ergeben sich
folgende Kombinationsmöglichkeiten für SymbolSize,
BlockSize und DataCount/ParityCount:
Mithilfe der oben berechneten Efficiency läßt sich jeder
Parameterkombination aus Choices eine "Güte" zuordnen:
Die berechneten Speichergrößen und "Güten" legen den
Entschluß nahe, für eine gegebene SymbolSize mehrere
Tabellen für unterschiedliche Kombinationen von BlockSize und
ParityCount anzulegen, um sowohl Situationen mit hohen Verlustraten
als auch solche mit geringen Verlusten optimal behandeln zu können.
Aufsuchen passender Einträge in Kodier- und Dekodiertabelle
Im Hinblick auf die Implementierung wird es Zeit, sich darüber Gedanken
zu machen, wie Kodier- und Dekodiertabelle organisiert sein müssen.
Der Aufbau der Kodiertabelle ist sehr einfach:
-
die Adresse eines Tabelleneintrages ergibt sich durch Aneinanderreihung der
Inhalte der einzelnen Datensymbole, wobei das erste Symbol an die
höchstwertige Stelle der so gewonnenen Zahl geschrieben werden soll
(s.o.);
-
der aus der Tabelle entnommene Wert besteht nun wiederum aus einer
Aneinanderreihung von Symbolen (nämlich den Prüfsymbolen), wobei
diesmal jedoch das erste Symbol an der wertniedrigsten Stelle stehen soll.
Der Zugriff auf die Dekodiertabelle ist etwas komplizierter:
-
der niederwertige Teil der Tabellenadresse ergibt sich durch Aneinanderreihung
der ersten DataCount vorhandenen Daten- oder Prüfsymbole in
ihrer ursprünglichen Reihenfolge (verlorene Symbole werden also nicht
berücksichtigt!), wobei das erste angetroffene Symbol an die
höchstwertige Stelle dieser Teiladresse geschrieben wird;
-
der höherwertige Teil der Tabellenadresse besteht aus der Nummer des
zu behandelnden Fehlerfalles (welcher seinerseits angibt, wieviele und welche
Datensymbole verloren gegangen sind und welche Prüfsymbole stattdessen
verwendet werden sollen).
Durch Aufschreiben der verschiedenen Kombinationsmöglichkeiten von Daten-
und Prüfsymbolen bei gegebener BlockSize, DataCount,
ParityCount sowie Anzahl verlorener Datensymbole (Losses)
kommt man leicht zu folgender kompliziert anmutender Formel zur Berechnung
des Fehlerfalles (LossCase):
LossBase = Sum[
Product[(DataCount-j)*(ParityCount-j), {j, 0,
i-1}],
{i, 1, Losses-1}]
Factor = Product[ParityCount-k, {k, 0, Losses-1}]
LossCase = LossBase + Sum [
Data[[m]] * Product[DataCount-n,
{n,1,Losses-m}]*Factor +
Parity[[m]]* Product[ParityCount-n, {n,1,Losses-m}],
{m,1,Losses-1}] +
Data[[Losses]]*Factor + Parity[[Losses]
]
Darin sind Data[[m]] die Positionen der verlorenen Datensymbole
und Parity[[m]] die Positionen der stattdessen zu verwendenden
Prüfsymbole.
Man beachte auch, daß z.B. LossBase für den Fall Losses
= 1 zu Null wird.
Anhang
Betrachtung zur Anzahl der Fehlerfälle
Durch Aufzeichnen mache man sich klar, daß es die folgende Anzahl von
Möglichkeiten für den Verlust von 1, 2, ... Paketen gibt, wenn
man zusätzlich o.B.d.A. vereinbart, daß das erste verlorene Paket
vor dem zweiten verlorenen Paket usw. liegen soll (n stehe für
DataCount):
Die Aufstellung legt nahe, daß hier eine Produktregel vorliegt - zur
genaueren Analyse betrachte man die Quotienten der o.a. Glieder:
Setzt man für das erste Glied den Term (-0+n) an und ersetzt
außerdem n durch DataCount, so erhält man folgende
Formel für die Anzahl der Kombinationsmöglichkeiten verlorener
Symbole bei insgesamt Losses Verlusten (von Datensymbolen):
Pro verlorenem Datensymbol wird ein erfolgreich empfangenes Prüfsymbol
benötigt. Die Anzahl der Kombinationsmöglichkeiten für die
zu verwendenden Prüfsymbole ergibt sich auf ganz ähnliche Weise:
Da bei insgesamt ParityCount Prüfsymbolen bis zu
ParityCount Datensymbole rekonstruiert werden können, müssen
für das endgültige Ergebnis alle Terme für Losses =
1...ParityCount aufsummiert werden:
Begleitmaterial
Folgende Dateien stehen zusätzlich zum Herunterladen zur Verfügung:
-
createTable.c (ASCII-Datei, 45039 Bytes)
ein einfaches ANSI-C Programm zur Berechnung der Kodier- und Dekodiertabellen
für die Java-Implementierung des Reed-Solomon Erasure Correction
-
RSETest.java (ASCII-Datei, 27492 Bytes)
ein einfaches Beispiel für die Reed-Solomon Erasure Correction in Java
Kodier/Dekodiertabellen
Die folgenden Dateien enthalten je eine fertige Kodier/Dekodiertabelle für
die Java-Implementierung. Die erste Ziffer im Dateinamen gibt dabei die
SymbolSize, die zweite die BlockSize und die letzte Ziffer
den ParityCount an:
-
RSE-Table_4_2_1.bin (Binärdatei, 36
Bytes)
-
RSE-Table_4_3_1.bin (Binärdatei, 772
Bytes)
-
RSE-Table_4_3_2.bin (Binärdatei, 52
Bytes)
-
RSE-Table_4_4_1.bin (Binärdatei, 16388
Bytes)
-
RSE-Table_4_4_2.bin (Binärdatei, 1540
Bytes)
-
RSE-Table_4_4_3.bin (Binärdatei, 132
Bytes)
-
RSE-Table_4_5_1.bin (Binärdatei, 327684
Bytes)
-
RSE-Table_4_5_2.bin (Binärdatei, 40964
Bytes)
-
RSE-Table_4_5_3.bin (Binärdatei, 5124
Bytes)
-
RSE-Table_4_5_4.bin (Binärdatei, 164
Bytes)
Literaturhinweise
|
