Error Checking and Correction

Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

Fehlerkorrekturverfahren (englisch: Error Correction Code, kurz ECC), dienen dazu, Fehler bei der Speicherung und Übertragung von Daten zu erkennen und, wenn möglich, zu korrigieren. Fehlererkennungsverfahren beschränken sich auf eine reine Fehlererkennung.

Dazu wird vor der Speicherung oder Übertragung den Nutzdaten zusätzliche Redundanz in Form zusätzlicher Bits hinzugefügt, die auf der Zielseite zur Bestimmung von Fehlern und Fehlerpositionen genutzt wird.

Fehlerursachen

Rauschen

Rauschen kann unabhängig von der Ursache „hin und wieder“ Bitfehler verursachen. Die Wahrscheinlichkeit für einen Fehler hängt dabei nicht vom Auftreten früherer Fehler ab, sondern nur von der Stärke des Rauschens. Daher ist eine gleichmäßige Verteilung der Fehler in gleich langen Zeitintervallen zu erwarten.

• Thermisches und elektronisches Rauschen → Verbreiterung der Entscheidungsschwellen im Augendiagramm → ab und zu wird die Fehlerschwelle überschritten
• erzeugt weitgehend gleichmäßig verteilte Fehler (die keine speziellen Schutzmaßnahmen wie z. B. Interleaving erfordern)

Kurzzeitstörungen

• Elektrische Funken, Kratzer auf CDs
• mehrere Bits hintereinander fehlerhaft (Burstfehler), sehr ungleichmäßige Fehlerverteilung
• kosmische Strahlung ^[1]

Signalverformung

• Dämpfungs- und Phasengang eines Übertragungskanal

Nebensprechen

• Unerwünschter Einfluss benachbarter Digitalkanäle zum Beispiel über kapazitive Kopplung

Fehlerarten

Einzelbitfehler

Einzelbitfehler sind Fehler, die unabhängig von anderen auftreten (Korrelationsfunktion ist konstant).

Bündelfehler (auch Blockfehler, oder engl. Error Bursts)

Bündelfehler sind Fehler, die abhängig von anderen auftreten (Korrelationsfunktion ist eine Spitze). In der Telekommunikation tritt diese Art von Fehler häufig durch Störeinflüsse wie zum Beispiel Blitze, Relaisschaltungen, usw. auf. Ein Fehlerbündel wird dabei durch eine zusammenhängende Sequenz von Symbolen (z. B. Bits) charakterisiert, bei der das erste und das letzte Symbol fehlerbehaftet sind, und es keine zusammenhängende Teilfolge von m korrekt empfangenen Symbolen innerhalb des Fehlerbündels gibt. Der ganzzahlige Parameter m wird auch Schutzbereich (engl. guard band) des Bündelfehlers genannt. Treten z. B. zwei Bündelfehler in einer Übertragung auf, muss der Abstand zwischen dem letzten Symbol des ersten Bündelfehlers und dem ersten Symbol des zweiten Bündelfehlers m korrekte Bits oder mehr betragen. Der Parameter m sollte deshalb spezifiziert werden, wenn ein Bündelfehler beschrieben werden soll.

Synchronisationsfehler

Sind (meist längere) Bündelfehler, die neben einem Datenverlust auch zu einem Verlust der Information führen, die man gerade empfängt. Dies führt dazu, dass auch nachfolgende korrekte Bits nicht mehr verwendet werden können. Bei Ethernet werden so z. B. Einzelbitfehler zu Synchronisationsfehlern.

Fehlererkennung

Parität, CRC, Hashs

Hamming-Distanz und Berechnung

Erkennungs- und Korrekturleistung von Codes mit Hamming-Distanz H

Beispiele

Nehmen wir an, es sollen acht Bits Nutzdaten mit dem Hamming-ECC-Verfahren übertragen werden, so sind hierfür zusätzlich vier Fehlerkorrektur-Bits nötig. Insgesamt müssen also zwölf Bits übertragen werden.

Nutzdaten:            1 2 3 4 5 6 7 8
                      0 1 0 0 1 1 0 0

zu übertragende Daten: 1  2  3  4  5  6  7  8  9 10 11 12
                       ?  ?  0  ?  1  0  0  ?  1  1  0  0

Die Bits 1,2,4,8 dienen in diesem Fall als Korrektur-Bits und sind immer an den Positionen der jeweiligen Potenz aus 2 (Pos=2^x, x=0,1,2,3...), also Position 1, 2, 4, 8, 16, 32 usw.

Nun müssen noch die Werte der Korrektur-Bits ermittelt werden. Hierfür wird jeder Bit-Position in unserer Übertragung ein Wert zugeordnet, der dem Binärwert der Dezimalposition entspricht. Der Wert ist hier 4-stellig, da wir nur 4 Bits für die Korrektur benötigen.

Pos:  1  Wert: 0001
Pos:  2  Wert: 0010
Pos:  3  Wert: 0011
Pos:  4  Wert: 0100
Pos:  5  Wert: 0101
Pos:  6  Wert: 0110
Pos:  7  Wert: 0111
Pos:  8  Wert: 1000
Pos:  9  Wert: 1001
Pos: 10  Wert: 1010
Pos: 11  Wert: 1011
Pos: 12  Wert: 1100
.......

Nun werden die Werte derjenigen Positionen, welche 1 in unserer Übertragung wären, mit XOR zusammen gerechnet, also Wert/Position 5, Wert/Position 9 und Wert/Position 10.

    0101   Position 5
    1001   Position 9
XOR 1010   Position 10
---------
 =  0110

Dies sind die Werte unser Fehlerkorrektur-Bits, welche nun in unsere Übertragung eingefügt werden:

zu übertragende Daten: !1 !2  3 !4  5  6  7 !8  9 10 11 12
                        0  1  0  1  1  0  0  0  1  1  0  0

Jetzt werden unsere Daten übertragen, und der Empfänger kann prüfen, ob es sich um korrekte Informationen handelt. Dazu wird der berechnete und der empfangene Korrekturwert Exklusiv-Oder-verknüpft (Kontravalenz):

empfangene Daten: !1 !2  3 !4  5  6  7 !8  9 10 11 12
                   0  1  0  1  1  0  0  0  1  1  0  0

    0101   Position 5
    1001   Position 9
XOR 1010   Position 10
---------
    0110   Korrekturbits berechnet
XOR 0110   Korrekturbits empfangen
---------
=   0000   => Korrekte Übertragung

Jetzt wird während der Übertragung beispielsweise Bit 5 verändert:

empfangene Daten: !1 !2  3 !4  5  6  7 !8  9 10 11 12
                   0  1  0  1  0  0  0  0  1  1  0  0

    1001   Position 9
XOR 1010   Position 10
---------
    0011   Korrekturbits berechnet
XOR 0110   Korrekturbits empfangen
---------
=   0101   => Wert der Position 5 => Bit 5 ist falsch!

Ergebnis der Berechnung ist immer der Positionswert des veränderten Bits oder 0, wenn kein Fehler auftrat. Dies funktioniert auch dann, wenn bei der Übertragung ein Korrekturbit verändert wurde. Bei Veränderung von 2 Bits kann nur noch eine Aussage darüber getroffen werden, dass Bits verändert wurden, nicht jedoch darüber, an welchen Positionen diese sitzen.

Fehlerkorrektur

Vorwärtsfehlerkorrektur

Siehe: Vorwärtsfehlerkorrektur

Vor- und Nachteile

Vorteile:

• Broadcast
• Hohe Leistungsauslastung

Nachteile:

• "Empfang" bricht bei zu starkem Signal zusammen

Hybridverfahren aus Modulation und Fehlererkennung/-korrektur

Die Modulation liefert neben dem demodulierten Signal noch Informationen über die Qualität des Signals. Eine Möglichkeit, dies zu erreichen, ist, nicht erlaubte Codes einzubauen. Treten diese auf, weiß man, dass die Daten mit hoher Wahrscheinlichkeit fehlerhaft sind.

• Trellis-Kodierungen
• 4B/5B-Code (16 von 32 Codes gültig)
• 8B/10B-Code (256 von 1024 Codes gültig)
• EFM (256 von 16384 (oder 131072) Codes gültig)
• EFMplus (256 von 16384 (oder 65536) Codes gültig)
• Eine bei IEEE 822.11 benutzte Modulation
• AMI-Modulation

Grenzen

Codespreizung

Umwandlung von Bündelfehlern in Einzelbitfehler.

Fehlererkennende und -korrigierende Codes

• Bose-Ray-Chaudhuri-Code (BCH)
• Zyklische Redundanzprüfung
• Faltungs-Code
• Fountain-Code
• Golay-Code
• Hamming-Code
• Low-Density-Parity-Check-Code (LDPC)
• Nordstrom-Robinson-Code
• Paritätsprüfung (eindimensionale Paritätsprüfung kann Fehler nur erkennen, mehrdimensionale auch korrigieren)
• Rank-Code
• Reed-Muller-Code
• Reed-Solomon-Code (RS)
• Repeat-Accumulate-Code (RA)
• Simplex-Code
• Slicing by Eight (SB8)
• Turbo-Code
• Wiederholungs-Code
• Woven-Code

Fehlerverdeckung

Ist eine Fehlerkorrektur nicht möglich, wird die sog. Fehlerverdeckung (error concealment) zur Verdeckung von Fehlern angewandt.

RAM - ECC- und Paritätsprüfung

Ein Error-correcting code (ECC) ist ein Fehlerkorrektur-Algorithmus, der im Gegensatz zur Paritätsprüfung in der Lage ist, einen 1-Bit-Fehler zu korrigieren und einen 2-Bit-Fehler zu erkennen. Das ECC-Verfahren benötigt auf 32 Bit 7 Check-Bits und auf 64 Bit 8 Check-Bits.

Das ECC-Verfahren wird häufig in Speicherbausteinen für Serversysteme eingesetzt, die eine besonders hohe Datenintegrität benötigen.

Compact Disc (CD)

Bei der Compact Disc wird das sogenannte CIRC-Fehlerkorrekturverfahren verwendet. Dabei werden bei der Kodierung aus dem laufenden Datenstrom jeweils 24 Bytes zu einem Fehlerkorrekturrahmen zusammengefasst und im Prozessor parallel weitergeführt. Die 24 Bytes werden mit 4 Paritätsbytes (Fehlerkorrekturbytes) ausgestattet, die mit Hilfe einer Matrizenrechnung bestimmt werden. Die 4 Paritätsbytes werden nach Byte-Position 12 in den Rahmen einsortiert. Der Rahmen hat dann 28 Bytes. Anschließend werden die Bytes von vielen so mit Paritätsbytes ausgestatteten Rahmen verschachtelt (Interleaving). Dabei werden die jeweils ersten Bytes des Rahmens nicht verzögert, die jeweils zweiten Bytes des Rahmens um 4 Rahmen verzögert, die dritten Bytes um 8 Rahmen etc., das 28te Byte wird um 108 Rahmen verzögert. Da dies im laufenden Datenstrom so gemacht wird, entstehen - abgesehen von den ersten 108 Rahmen, die unvollständig bleiben - wieder vollständige Rahmen aus 24 Bytes plus 4 Paritätsbytes. Diese neuen Rahmen, die nunmehr aus völlig anderen Bytes zusammengesetzt sind, werden mit derselben Matrizenrechnung (lediglich angepasst auf nunmehr 28 fehlerzusichernde Bytes) erneut mit 4 Paritätsbytes ausgestattet, die an Byte-Position 29 bis 32 in den Rahmen eingefügt werden.

Nach jedem Rahmen wird dann noch ein sogenanntes Subcodewort eingefügt (98 Subcodewörter ergeben immer eine Steuer- und Anzeigeinformation (u. a. die Adresse) für einen sogenannten Subcoderahmen). Die Daten werden dann wieder seriell weitergeführt, EFM-moduliert Eight-to-Fourteen-Modulation und vor jedem jetzt schon modulierten Rahmen mit einer Synchronisationsinformation ausgestattet (1000000000010000000000101), damit der Player den Anfang des Rahmens wiederfindet. Die so aufbereiteten Daten werden in NRZ-I-Notation in Form von Pits und Lands in einer Spur auf der Disc aufgezeichnet (so bei der CD-R) bzw. auf einem Master aufgezeichnet. Vom Master wird ein Spritzgusswerkzeug hergestellt, mit dem die einzelnen Discs als Kopien gefertigt werden. Ein Bit hat hier die Länge von ca. 1/3 Micrometer. Auf einem Millimeter der Spur sind die Bits von ca. 150 Bytes aufgezeichnet. Ein Kratzer auf der Disc kann somit leicht die Bits von 20, 50 oder 100 Bytes beschädigen, sprich die Bytes eines halben oder ganzen Rahmens.

Die verkratzte Disc kann man dennoch mit einem CD-Player auslesen und fehlerfrei wiedergeben. Das Auslesesignal wird in Bits umgewandelt, diese werden EFM-demoduliert, die Synchronisationsinformation und das Subcodewort werden aus dem Datenstrom entfernt und die Bytes wieder parallel geführt. Wo der Player nichts lesen konnte, werden Dummy-Bits in den Datenstrom getaktet.

Es werden nun wieder die Fehlerkorrekturrahmen aus insgesamt 32 Bytes (24 Informationsbytes und 2 x 4 Paritätsbytes) gebildet. Danach wird anhand der 4 zuletzt zugeführten Paritätsbytes geprüft, ob alle Daten korrekt ausgelesen wurden, oder ob irgendwo ein Bit bzw. ein ganzes Byte oder sogar mehrere Bytes im Fehlerkorrekturblock als nicht korrekt identifiziert werden. Kleinere Fehler kann der Decoder sofort korrigieren. Bei größeren Fehlermengen (z. B. Kratzer, sogenannte Burst-Fehler) ist dies zwar nicht möglich, die fehlerhaften Bytes können aber identifiziert und mit einer Fehlermeldung versehen werden. Anschließend werden die Daten wieder in ihre ursprüngliche Position zurücksortiert (Deinterleaving) und die ursprünglichen Fehlerkorrekturrahmen aus 24 Bytes plus 4 Paritätsbytes gebildet. An dieser Stelle zeigt sich der Korrektureffekt des Interleavings: Die durch den Kratzer beschädigten 20 oder 50 auf der Spur nebeneinanderliegenden Bytes stammten ursprünglich alle aus verschiedenen Fehlerkorrekturrahmen und sind jetzt wieder auf diese Rahmen verteilt. Dadurch sind jetzt in diesen Rahmen in den allerseltensten Fällen mehr als zwei Bytes fehlerhaft. Zwar tauchen also in vielen Fehlerkorrekturrahmen vereinzelt fehlerhafte Bytes auf, diese können jedoch alle mit Hilfe der vier Paritätsbytes korrigiert werden. Am Ende liegt wieder der fehlerfreie serielle Datenstrom vor.

Die Berechnung der Fehlerkorrekturbytes lässt sich stark vereinfacht an folgendem Beispiel demonstrieren: Die beiden Bytes

01001010 und

10010010

sollen mit Paritätsbytes ausgestattet werden. Als Regel für die Berechnung wird die Binäroperation "Exklusives NICHT-ODER" (XNOR-Verknüpfung) verwendet: "Wenn 2 gleiche Ziffern untereinander stehen, wird eine 1 als Paritätsbit genommen, wenn 2 ungleiche Ziffern untereinander stehen, eine 0". Danach ergibt sich folgendes Bild:

01001010

10010010

00100111.

Man kann nun z. B. das erste Byte löschen und mit Hilfe des Paritätsbytes und des nicht gelöschten zweiten Bytes das gelöschte Byte durch Anwendung derselben Regel rekonstruieren. Wo 2 gleiche Ziffern untereinander stehen, wird eine 1 als Korrekturbit eingesetzt, wo 2 ungleiche Ziffern untereinander stehen, eine 0. Nachfolgend ist dies schon für die ersten beiden Bits geschehen, der Leser kann die Korrektur selbst vollenden:

01

10010010

00100111.

Genauso kann man vorgehen, wenn das zweite Byte gelöscht und das erste noch vorhanden ist.

Bei diesem Beispiel wurde mit 50% Fehlerkorrekturdaten gearbeitet. Bei der CD werden pro 24 Bytes 8 Fehlerkorrekturbytes eingefügt, somit muss hier 33% zusätzliche (redundante) Information gespeichert werden.

ADSL

Bei einem ADSL-Anschluss der Deutschen Telekom und anderer Anbieter ist standardmäßig Interleaving für die Fehlerkorrektur eingeschaltet. Hierbei werden die Datenbits verschiedener Frames vermischt, wodurch die Fehlerkorrektur effektiver gegen Impulsstörungen auf der Leitung arbeitet.

Interleaving treibt die Latenz (Ping) in die Höhe, eine einwandfreie Datenübertragung ist jedoch auch ohne Interleaving möglich (allerdings abhängig von der Leitungsqualität zwischen Vermittlungsstelle und Teilnehmeranschluss).

Ein Anschluss mit abgeschaltetem Interleaving wird bei T-DSL Fastpath genannt. Solche Verbindungen eignen sich besonders für Online-Spieler sowie für Dienste mit hoher Nutzer-Interaktivität (VoIP), bei denen die Latenz möglichst gering sein soll.

Siehe auch

• G.821
• Hamming-Abstand
• Bitfehlerrate
• Kanalkodierung
• Kodierungstheorie
• Vorwärtsfehlerkorrektur
• Fehlerverdeckung (error concealment)
• Low-Density-Parity-Check-Code
• Fault-Detection, Fault-Isolation and Recovery Techniques

Weblinks

The Error Correcting Codes (ECC) Page

Einzelnachweise

1. ↑ Scott Mueller: PC-Hardware-Superbibel. 2005. Markt&Technik.