Website durchsuchen

Fehlerkorrekturverfahren

Um Übertragungsfehler zu beseitigen, die durch die Erdatmosphäre verursacht wurden (links), verwendeten Goddard-Wissenschaftler die Reed-Solomon-Fehlerkorrektur (rechts), die üblicherweise in CDs und DVDs verwendet wird. Typische Fehler sind fehlende Pixel (weiß) und falsche Signale (schwarz). Der weiße Streifen zeigt einen kurzen Zeitraum an, in dem die Übertragung unterbrochen wurde.

Fehlerkorrekturverfahren, auch Error Correcting Code oder Error Checking and Correction (ECC), dienen dazu, Fehler bei der Speicherung und Übertragung von Daten zu erkennen und möglichst zu korrigieren. Fehlererkennungsverfahren beschränken sich auf das Feststellen, ob ein Fehler vorliegt. Dazu wird vor der Datenspeicherung oder Übertragung den Nutzdaten zusätzliche Redundanz hinzugefügt, meist in Form zusätzlicher Bits, die auf der Zielseite zum Erkennen von Fehlern und zum Bestimmen der Fehlerposition(en) genutzt wird.

Geschichte

Bereits 1950 wurden beispielsweise durch den Mathematiker Richard W. Hamming und Marcel J. E. Golay die ersten Fehlerkorrekturverfahren entwickelt. Diese konnten zunächst überwiegend nur Einzelbitfehler korrigieren.

1960 wurden Verfahren entwickelt, die mehrere, auch nebeneinander liegende Fehler (Fehler-Burst) erkennen und korrigieren konnten. Die Wissenschaftler Irving Stoy Reed und Gustave Solomon entwickelten dieses nach ihnen benannte Verfahren Reed-Solomon-Code. Weitere Wissenschaftler, die sich mit der Entwicklung solcher Verfahren beschäftigten sind, Philip Fire (Fire-Code 1959) Raj Chandra Bose, Dijen Kumar Ray-Chaudhuri und Alexis Hocquenghem (BCH-Code).

Ausdruck des Fehlers

Fehlerarten

Fehlererkennung in der Gerätetechnik

Der Error Correction Mode (ECM) kann beispielsweise Übertragungsfehler beim Senden und Empfangen von Faxen durch Leitungsstörungen erkennen. Fehlerhafte Seiten werden gegebenenfalls erneut gesendet.

Fehlererkennung in der Informationstechnik

→ Hauptartikel: Parität (Mathematik), Hashfunktion

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 dafür zusätzlich vier Fehlerkorrektur-Bits nötig. Insgesamt müssen also zwölf Bits übertragen werden.

Nutzdaten:

Bit(Stelle) 8 7 6 5 4 3 2 1
Inhalt 0 0 1 1 0 0 1 0

zu übertragende Daten:

Bit (Stelle) 12 11 10 9 8 7 6 5 4 3 2 1
Inhalt 0 0 1 1 ? 0 0 1 ? 0 ? ?

Die Bits 1, 2, 4 und 8 dienen in diesem Fall als Korrektur-Bits und sind immer an den Positionen der jeweiligen Potenz aus 2 (Pos = 2x, 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. Dafür wird jeder Bit-Position in unserer Übertragung ein Wert zugeordnet, der dem Binärwert der Dezimalposition entspricht. Der Wert ist hier vierstellig, da wir nur vier 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 die Werte der Positionen 5, 9 und 10. 

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

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

zu übertragende Daten:

Bit (Stelle) 12 11 10 9 8 7 6 5 4 3 2 1
Inhalt 0 0 1 1 0 0 0 1 1 0 1 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:

Bit (Stelle) 12 11 10 9 8 7 6 5 4 3 2 1
Inhalt 0 0 1 1 0 0 0 1 1 0 1 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:

Bit (Stelle) 12 11 10 9 8 7 6 5 4 3 2 1
Inhalt 0 0 1 1 0 0 0 0 1 0 1 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. Das funktioniert auch dann, wenn bei der Übertragung ein Korrekturbit verändert wurde. Bei Veränderung von zwei 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

Vor- und Nachteile

Vorteile:

Nachteile:

Hybridverfahren aus Modulation und Fehlererkennung/-korrektur

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

Codespreizung

Codespreizung wird beispielsweise bei UMTS in Mobilfunk verwendet. Darunter versteht man die Aufspreizung einer binären 1 oder 0 in ein Vielfaches davon. Spreizfaktor 8 würde z.B. aus einer Eins eine Folge von acht Einsen (1111 1111) machen. Somit können Übertragungsfehler leicht erkannt und korrigiert werden. Zulässige Spreizfaktoren sind allesamt Zweierpotenzen, in UMTS von 2, 4, 8, … bis 256. Durch Aufspreizung verringert sich allerdings die nutzbare Bandbreite für Daten.

Fehlererkennende und -korrigierende Codes

Fehlererkennende und fehlerkorrigierende Codes (englisch error-detecting codes und englisch error-correcting codes) sind Datenkodierungen, die zusätzlich zu den kodierten Daten noch Informationen enthalten, um Datenfehler zu erkennen oder zu beheben. Abhängig von der verwendeten Kodierung können mehr oder weniger Fehler entdeckt oder korrigiert werden.

Fehlerverdeckung

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

ECC- und Paritätsprüfung

Ein error-correcting code (ECC) ist eine Kodierung zur Fehlerkorrektur, die 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 6 Check-Bits und auf 64 Bit 7 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 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 28. Byte wird um 108 Rahmen verzögert. Da das 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 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 µm. 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 × 4 Paritätsbytes) gebildet. Danach wird anhand der vier 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 das 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 zwei 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 zwei gleiche Ziffern untereinander stehen, wird eine 1 als Korrekturbit eingesetzt, wo zwei ungleiche Ziffern untereinander stehen, eine 0. Nachfolgend ist das 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 regulären ADSL-Anschluss ist standardmäßig Interleaving für die Fehlerkorrektur eingeschaltet. Dabei werden die Datenbits mehrerer Datenblöcke („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).

Das Abschalten des Interleaving wird bei den meisten DSL-Anbietern in Deutschland als Fastpath-Funktion angeboten, obwohl es keine Zusatzleistung, sondern eine Abschaltung einer Funktionalität darstellt. Solche Verbindungen eignen sich für Online-Spieler sowie für Dienste mit hoher Nutzer-Interaktivität (VoIP), bei denen eine geringe Latenz bedeutender ist als die Datenfehlerquote. Als Beispiel ist ein minimaler Lautstärkenverlust oder ein leises Störgeräusch, jeweils < 1 Sekunde, bei einer Sprachverbindung über VoIP eher hinnehmbar als eine stockende Übertragung.

Siehe auch

Literatur

Trenner
Basierend auf einem Artikel in: Extern Wikipedia.de
Seitenende
Seite zurück
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 22.02. 2023