B Fehlerkorrektur
B.1 BedeutungAlle physikalischen Übertragungswege sind fehlerbehaftet. Die Beeinträchtigungen können beispielsweise entstehen durch thermisches Rauschen von Halbleitern, durch EMV-Einstrahlung oder durch radioaktive Höhenstrahlung.Quantitativ wird der Effekt erfasst durch die Messung der Fehlerrate (Bitfehlerwahrscheinlichkeit; "Bit Error Rate" BER). Diese ist definiert als Anzahl fehlerhafter Bits bezogen auf die Anzahl gesendeter Bits. Sie ist unter anderem abhängig von Länge und Dämpfung des Übertragungswegs, von der Übertragungsgeschwindigkeit und der Sendeleistung. Aus wirtschaftlichen Gründen nimmt man endliche Fehlerraten in Kauf, mit typischen Werten von 10-4 für verdrillte Zweidrahtleitungen in industrieller Umgebung oder 10-12 bei digitalen Standleitungen. Während diese Werte für manche Anwendungen wie Musik oder Sprache unkritisch sind, sind sie beispielsweise für die Übertragung von Programmen oder Datenbankinhalten völlig inakzeptabel. Bei einer Größe von 10 MByte und einer Fehlerrate von 10-7 hätte eine übertragene Datei typischerweise 8 Bitfehler, die als isolierte Einzelfehler oder als Fehlerbündel ("Burst") auftreten können. Alle Verfahren zur Fehlerkorrektur beruhen auf dem gezielten Einsatz von Redundanz, d.h. es werden zusätzlich zur Originalnachricht weitere Sicherungsinformationen übertragen, die vom Empfänger zur Fehlererkennung oder -korrektur verwendet und dann wieder entfernt werden. Da die Fehlerrate nie exakt auf Null reduziert werden kann, muss in jedem Fall ein Kompromiss zwischen Aufwand und gerade noch akzeptabler Fehlerrate gefunden werden. B.2 SystematikReine Fehlererkennung ohne die Möglichkeit einer Korrektur ist nur in Ausnahmefällen sinnvoll. So können z.B. bei Audioübertragungen die Auswirkungen von Fehlern abgemildert werden, indem als fehlerhaft erkannte Bytes durch Interpolation oder als Nullwerte ersetzt werden. Meist wird man aber die ursprüngliche Information durch Fehlerkorrektur möglichst originalgetreu wiederherstellen wollen.Die einfachste Methode besteht darin, dass der Empfänger Fehler erkennt und daraufhin den Sender auffordert, die fehlerhaften Teile noch einmal zu senden (Wiederholung fehlerhafter Blöcke; "Automatic Repeat Request" ARQ). Diese Methode hat ihre Grenzen. Sie funktioniert nicht bei fehlendem Rückkanal (Tastatur, Maus, 1:n-Übertragungssysteme), bei kritischen Echtzeitanwendungen und bei fehlenden Speichermöglichkeiten in Sender oder Empfänger. Sie ist nicht mehr sinnvoll bei hohen Fehlerraten, da die Netto-Datenrate stark sinkt und gleichzeitig schwankt. In diesen Fällen setzt man aufwändigere Verfahren ein, die es dem Empfänger ermöglichen, fehlerhaft empfangene Daten ohne Rückfrage beim Sender zu rekonstruieren. Der Sammelbegriff dafür heißt Vorwärts-Fehlerkorrektur ("Forward Error Correction" FEC). Man unterscheidet dabei zwischen Blockcodierung und Faltungscodierung. Bei der Blockcodierung ("Block Coding") berechnet der Sender aus Blöcken konstanter Länge Prüfinformation, die an den Originalblock angehängt wird. Dabei werden folgende Begriffe verwendet:
Der Empfänger kann Fehler korrigieren, indem er falsche Codewörter erkennt und sie durch die mit höchster Wahrscheinlichkeit richtigen ersetzt. Das kann aber nur funktionieren, wenn der minimale Bit-Abstand zweier beliebiger legaler Codewörter ("Hamming-Distanz") einen bestimmten Mindestwert erreicht. Um e Bitfehler pro Block erkennen zu können, benötigt man eine Hamming-Distanz von e+1, zur Korrektur von e Fehlern eine Distanz von 2e+1. Bei der Faltungscodierung ("Convolutional Coding") wird ein wanderndes Fenster über den Originaldatenstrom gelegt. Dieses bläht den Originaldatenstrom unter Verwendung definierter Algorithmen zu einem höheren, aber kontinuierlichem Übertragungsdatenstrom auf. B.3 Praktische VerfahrenB.3.1 ParitätsprüfungDieses Verfahren wird auch als Querparität ("Vertical Redundancy Check" VRC) bezeichnet und gehört zur Gruppe der fehlererkennenden Verfahren mittels Blockcodierung.An einen Block von beispielsweise 8 bit wird eine weitere Stelle angehängt, die die Anzahl der 1-Bits auf eine ungerade Anzahl ergänzt bei ungerader Parität ("odd parity") oder auf eine gerade Anzahl bei gerader Parität ("even parity"). Die Auswahl der Methode muss vor der Übertragung zwischen den Kommunikationspartnern vereinbart sein.
Ein weiteres Beispiel zeigt die obere Hälfte der Abb. B-1. Erkannt wird jede ungerade Anzahl von Fehlern pro Block. Nicht erkannt wird jede gerade Anzahl von Fehlern pro Block. Korrektur von Fehlern ist nur möglich durch Wiederholung der Übertragung. B.3.2 KreuzparitätDieses Verfahren wird auch als Längs- und Querparität ("Longitudinal and vertical redundancy check" LRC/VRC) bezeichnet. Zusätzlich zum Paritätsbit pro Block wird ein weiteres Prüf-Codewort über n Codewörter gebildet und angehängt. Die Redundanz ist etwas höher als bei der reinen Querparität, dafür können aber auch wesentlich mehr Fehler erkannt bzw. sogar korrigiert werden. (Beispiel s. Abb. B-1 unten).
B.3.3 Zyklische BlockcodierungDas Verfahren der zyklischen Blockcodierung ("Cyclic redundancy check" CRC) beruht auf der Verwendung von Generatorpolynomen, um eine Folge von r bit an einen Block von k bit anzuhängen. Die Originalnachricht wird durch das Generatorpolynom "dividiert". Der entstehende Divisionsrest wird angehängt. Der Empfänger kann den gleichen Algorithmus verwenden und die beiden Reste vergleichen. Bei Ungleichheit enthält der Nutzdatenblock Fehler. Zur Korrektur wird meist eine Wiederholung des fehlerhaften Blocks angefordert.Erkannt werden (mindestens) alle Bündelfehler, deren Länge kleiner ist als der Grad des verwendeten Generatorpolynoms, oder allgemeiner formuliert, alle Bündelfehler, deren Fehlerpolynom das Generatorpolynom nicht als Teiler enthält. Abb. B-2 enthält eine Übersicht häufig verwendeter Polynome und ihre mögliche Realisierung durch rückgekoppelte Schieberegister. Die dargestellten Hardware-Schaltungen werden häufig in Software nachgebildet. B.3.4 Reed-Solomon-FehlerkorrekturDer Reed-Solomon-Algorithmus beruht auf der Theorie der Galois-Felder (auf die hier nicht näher eingegangen werden soll) und dient zur Korrektur von Fehlern im Empfänger. Er wird beispielsweise verwendet in Rundfunk- oder Satellitenübertragungen, bei denen ein Rückkanal wirtschaftlich nicht sinnvoll ist, und die außerdem starken und stark schwankenden Störungen und daraus resultierenden Bündelfehlern ausgesetzt sind.Reed-Solomon wird angewendet auf Blöcke von Symbolen, wobei ein Symbol jeweils ein oder mehrere Bits enthält. Die Notierung RS(n,k) bedeutet, dass der Originalblock aus k, der Sendeblock aus n Symbolen besteht. Über die Länge eines einzelnen Symbols wird nichts ausgesagt. Nach der Berechnung werden vom Sender also 2*t = n-k zusätzliche Symbole angefügt. Der Empfänger kann damit t = (n-k)/2 Symbolfehler korrigieren.
B.3.5 FaltungscodierungDas bekannteste und am häufigsten eingesetzte Verfahren aus dieser Gruppe benutzt den Viterbi-Algorithmus. Auch hier werden Generatorpolynome (und Schieberegister) verwendet. Die Verarbeitung erfolgt jedoch nicht blockweise, sondern kontinuierlich, indem jedes Bit des Eingangsstroms, zusammen mit s Vorgängern verarbeitet wird und dabei den Übertragungsdatenstrom aufbläht. Vorteilhaft ist dabei die Kürze des benötigten Gedächtnisses und die damit verbundene geringe Verzögerung.Allerdings erzeugt das Verfahren einen (nicht verwendbaren) Vorspann und muss eine der Gedächtnislänge entsprechende Anzahl von 0-Bits an die Originalnachricht anhängen, um auch die letzten Bits übertragen und auswerten zu können. Als Parameter werden verwendet:
Zwei einfache Beispiele (Abb. B-3 und Abb. B-4) sollen das Prinzip verdeutlichen. Beide Abbildungen zeigen links oben den Codierungsalgorithmus als Schieberegisterschaltung. Darunter ist die Impulsantwort der Schaltung in Tabellenform dargestellt, d.h. die Ausgangssignale A1, A2 und die inneren Zustände D als Reaktion auf die Eingabe E eines einzelnen 1-Bits. Ganz unten zeigt das Zustandsdiagramm der Schaltung die möglichen internen Zustände, die möglichen Übergänge und die dabei erzeugten Ausgangssignale. In der rechten Hälfte ist beispielhaft das Verhalten des Codierers für eine konkrete Eingangsfolge mit 4 bit Länge (1001) dargestellt. Die obere Hälfte verwendet zur Darstellung eine Methode, bei der jedes angelegte 1-Bit eine Einzelimpulsantwort erzeugt, die dann zeitabhängig zur Ausgangssignalfolge addiert werden. Die untere Hälfte zeigt ein Trellis-Diagramm. Es verwendet die Informationen des Zustandsdiagramms (innere Zustände, Übergänge und Ausgangssignale), stellt jedoch zusätzlich den zeitlichen Ablauf dar. Abb. B-3 verwendet die Parameter k=1, n=2 und s=2. Aus den 4 Eingangsbits 1001 werden insgesamt 12 Ausgangsbits 111011111011 erzeugt und an den Empfänger übertragen. Abb. B-4 verwendet die Parameter k=1, n=2 und s=3. Aus den 4 Eingangsbits 1001 werden insgesamt 14 Ausgangsbits 11011100011111 erzeugt und an den Empfänger übertragen. Die Decodierung im Empfänger (nicht dargestellt) vergleicht den empfangenen Datenstrom mit allen möglichen Datenströmen, die durch erlaubte Zustandsfolgen erzeugt werden können. Der Kandidat mit der geringsten Hamming-Distanz wird für die Decodierung herangezogen, bei der aus den Übertragungsdaten die ursprüngliche Eingabefolge rekonstruiert wird. |
|||||||||||||||||||||||||||||||||||||||||||||
 |
Dateneingabe |