Fehlerkorrekturverfahren

Zweck und Fehlerarten

Fehlerkorrekturverfahren, auch Error Correcting Code oder Error Checking and Correction (ECC), erkennen und korrigieren möglichst Fehler bei der Speicherung und Übertragung von Daten. Dafür erhalten die Nutzdaten vor der Speicherung oder Übertragung zusätzliche Redundanz, meist zusätzliche Bits. Diese ermöglichen es auf der Empfängerseite, Fehler festzustellen und gegebenenfalls ihre Position zu bestimmen. Fehlererkennungsverfahren allein melden nur, ob ein Fehler vorliegt.

Rauschen kann Bitfehler verursachen; die Fehlerwahrscheinlichkeit hängt dabei nur von der Rauschstärke und nicht von früheren Fehlern ab. Deshalb sind gleichmäßig verteilte Fehler in gleich langen Zeitintervallen zu erwarten. Thermisches und elektronisches Rauschen verbreitert Entscheidungsschwellen im Augendiagramm, sodass die Fehlerschwelle gelegentlich überschritten wird. Signalverformung kann durch Dämpfungs- und Phasengang eines Übertragungskanals entstehen; Nebensprechen ist der unerwünschte Einfluss benachbarter Digitalkanäle, etwa durch kapazitive Kopplung. Kurzzeitstörungen wie elektrische Funken oder Kratzer auf CDs führen häufig zu mehreren aufeinanderfolgenden fehlerhaften Bits. Auch kosmische beziehungsweise ionisierende Strahlung wird genannt.

Einzelbitfehler treten unabhängig voneinander auf; ihr Korrelationskoeffizient ist Null. Bündelfehler, auch Burst-, Block- oder Büschelfehler, sind voneinander abhängig; ihre Korrelationsfunktion ist eine Spitze. Ein Bündelfehler ist eine zusammenhängende Symbolfolge, deren erstes und letztes Symbol fehlerhaft sind und die keine zusammenhängende Teilfolge von m korrekt empfangenen Symbolen enthält. Das ganzzahlige m heißt Schutzbereich (guard band). Zwischen zwei Bündelfehlern müssen mindestens m korrekte Bits liegen. Synchronisationsfehler sind meist längere Bündelfehler: Neben dem Inhalt geht auch verloren, wie viele Symbole fehlten. Nachfolgende korrekte Symbole lassen sich dann nicht mehr zuordnen; bei Ethernet können so Einzelbitfehler zu Synchronisationsfehlern werden.

Hamming-Code: Fehler finden und korrigieren

Die Erkennungs- und Korrekturleistung eines Codes hängt von seiner Hamming-Distanz H ab. Beim dargestellten Hamming-ECC-Beispiel werden acht Nutzdatenbits mit vier Fehlerkorrekturbits übertragen, also insgesamt zwölf Bits. Die Korrekturbits stehen an Positionen, die Zweierpotenzen sind: Pos = 2^x mit x = 0, 1, 2, 3, …; hier also an Position 1, 2, 4 und 8.

Jede Bitposition erhält den Binärwert ihrer Dezimalposition. Bei zwölf Bits ist dieser Wert vierstellig, zum Beispiel Pos. 5 = 0101, Pos. 9 = 1001 und Pos. 10 = 1010. Für die Nutzdaten 00110010 stehen an den Datenpositionen 5, 9 und 10 Einsen. Ihre Positionswerte werden mit XOR verknüpft: 0101 XOR 1001 XOR 1010 = 0110. Dies ist der Wert der Korrekturbits. Die zwölf zu übertragenden Bits lauten dann, von Position 12 bis 1: 0 0 1 1 0 0 0 1 1 0 1 0.

Der Empfänger berechnet den Korrekturwert erneut und verknüpft ihn mit den empfangenen Korrekturbits durch Exklusiv-Oder (Kontravalenz). Das Ergebnis 0000 bedeutet eine korrekte Übertragung. Wird etwa Bit 5 verändert, ergibt die Rechnung 0101; das ist der Positionswert von Bit 5 und zeigt damit die falsche Stelle an. Das Verfahren funktioniert auch, wenn ein Korrekturbit verändert wurde. Bei zwei veränderten Bits lässt sich nur noch feststellen, dass Bits verändert wurden, nicht jedoch, an welchen Positionen.

Verfahren und Codes

Fehlererkennende und fehlerkorrigierende Codes sind Datenkodierungen, die neben den Daten Informationen zum Erkennen oder Beheben von Datenfehlern enthalten. Je nach Kodierung können unterschiedlich viele Fehler erkannt oder korrigiert werden. Genannte Codes sind unter anderem BCH-, Faltungs-, Fountain-, Golay-, Hamming-, LDPC-, MDS-, Reed-Muller-, Reed-Solomon-, Turbo- und Wiederholungscode sowie zyklische Redundanzprüfung (ZRP, englisch CRC). CRC dient der Fehlererkennung und ist Grundlage für ARQ-Verfahren. Eine eindimensionale Paritätsprüfung kann Fehler nur erkennen, eine mehrdimensionale auch korrigieren.

Vorwärtsfehlerkorrektur eignet sich für Broadcast und erlaubt eine hohe Leistungsauslastung. Ein Nachteil ist, dass der Empfang bei zu starkem Signal zusammenbricht. Hybridverfahren verbinden Modulation mit Fehlererkennung oder -korrektur: Die Modulation liefert zusätzlich Hinweise auf die Signalqualität. Nicht erlaubte Codes können eingebaut werden; treten sie auf, sind die Daten mit hoher Wahrscheinlichkeit fehlerhaft. Beispiele sind Trellis-Kodierungen, 4B/5B-Code mit 16 von 32 gültigen Codes, 8B/10B-Code mit 256 von 1024 gültigen Codes, EFM und EFMplus sowie AMI-Modulation.

Bei der Codespreizung wird eine binäre 1 oder 0 in ein Vielfaches aufgespreizt. Ein Spreizfaktor 8 macht aus einer Eins beispielsweise 1111 1111. Dadurch lassen sich Übertragungsfehler leicht erkennen und korrigieren. In UMTS werden Zweierpotenzen von 2, 4, 8, … bis 256 verwendet. Die Aufspreizung verringert jedoch die nutzbare Datenbandbreite.

ECC, Fehlerverdeckung und Compact Disc

Wenn Korrektur nicht möglich ist, wird Fehlerverdeckung (error concealment) eingesetzt. Ein ECC kann im Unterschied zur Paritätsprüfung einen 1-Bit-Fehler korrigieren und einen 2-Bit-Fehler erkennen. Er benötigt für 32 Bit 6 Check-Bits und für 64 Bit 7 Check-Bits. ECC wird häufig in Speicherbausteinen von Serversystemen verwendet, die besonders hohe Datenintegrität benötigen.

Die Compact Disc verwendet CIRC-Fehlerkorrektur. Zunächst werden jeweils 24 Bytes mit 4 durch Matrizenrechnung bestimmten Paritätsbytes ergänzt; diese stehen nach Byte-Position 12, sodass ein Rahmen 28 Bytes umfasst. Danach werden Bytes zahlreicher Rahmen verschachtelt (Interleaving): Das erste Byte wird nicht verzögert, das zweite um 4 Rahmen, das dritte um 8 Rahmen und das 28. Byte um 108 Rahmen. Die neu zusammengesetzten Rahmen erhalten erneut 4 Paritätsbytes an den Positionen 29 bis 32. Es folgen Subcodewörter, EFM-Modulation und die Synchronisationsinformation 1000000000010000000000101.

Kratzer können leicht die Bits von 20, 50 oder 100 Bytes beschädigen. Beim Lesen werden fehlende Daten als Dummy-Bits getaktet. In den 32-Byte-Rahmen kann der Decoder kleinere Fehler sofort korrigieren; größere Fehlermengen werden als fehlerhafte Bytes erkannt und markiert. Nach dem Deinterleaving liegen die durch einen Kratzer nebeneinander beschädigten Bytes wieder in verschiedenen ursprünglichen Rahmen. Dadurch sind dort meist höchstens zwei Bytes fehlerhaft und können mit den vier Paritätsbytes korrigiert werden. Pro 24 Bytes fügt die CD 8 Fehlerkorrekturbytes ein, also 33 % zusätzliche redundante Information.

Ein vereinfachtes Beispiel nutzt die XNOR-Verknüpfung für 01001010 und 10010010. Gleiche Ziffern ergeben als Paritätsbit 1, ungleiche 0; das Paritätsbyte lautet 00100111. Ist eines der beiden Bytes gelöscht, kann es aus dem anderen Byte und dem Paritätsbyte mit derselben Regel rekonstruiert werden. In diesem Beispiel bestehen 50 % der Daten aus Fehlerkorrekturdaten.

Interleaving bei ADSL

Bei einem regulären ADSL-Anschluss ist Interleaving zur Fehlerkorrektur standardmäßig eingeschaltet. Dabei werden Datenbits mehrerer Datenblöcke (Frames) vermischt. So wirkt die Fehlerkorrektur besser gegen Impulsstörungen auf der Leitung.

Interleaving erhöht jedoch die Latenz (Ping). Eine fehlerfreie Übertragung kann auch ohne Interleaving möglich sein, abhängig von der Leitungsqualität zwischen Vermittlungsstelle und Teilnehmeranschluss. Viele DSL-Anbieter in Deutschland bieten das Abschalten als Fastpath-Funktion an. Dies eignet sich für Online-Spieler sowie für stark interaktive Dienste wie VoIP, wenn geringe Latenz wichtiger ist als die Datenfehlerquote. Bei VoIP ist beispielsweise ein Lautstärkenverlust oder leises Störgeräusch von jeweils weniger als 1 Sekunde eher hinnehmbar als eine stockende Übertragung.