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.

→ Hauptartikel: Golay-Code, Hamming-Code und MDS-Code

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

• Rauschen: Rauschen kann unabhängig von der Ursache 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 führen zu einer Verbreiterung der Entscheidungsschwellen im Augendiagramm. Daher wird ab und zu 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 bzw. ionisierende Strahlung
• Signalverformung
  • Dämpfungs- und Phasengang eines Übertragungskanals
• Nebensprechen
  • Unerwünschter Einfluss benachbarter Digitalkanäle zum Beispiel über kapazitive Kopplung

Fehlerarten

• Einzelbitfehler: sind Fehler, die unabhängig von anderen auftreten (Korrelationskoeffizient ist Null).

• Bündelfehler: (auch Burstfehler, Blockfehler, Büschelfehler oder englisch error bursts) 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 Blitze, Relaisschaltungen 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 (englisch 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: Dies sind (meist längere) Bündelfehler, die neben einem Verlust des Inhalts der empfangenen Symbole auch zu einem Verlust der Information darüber führen, wie viele Symbole verlorengegangen sind. Das führt dazu, dass auch nachfolgende korrekte Symbole nicht mehr verwendet werden können, da nicht mehr bekannt ist, an welche Stelle die empfangenen Symbole gehören. Bei Ethernet werden so z. B. Einzelbitfehler zu Synchronisationsfehlern.

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.

→ Hauptartikel: Fehlerdiagnose

Fehlererkennung in der Informationstechnik

→ Hauptartikel: Parität (Mathematik), Zyklische Redundanzprüfung und 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 = 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. 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

→ Hauptartikel: 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, das 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

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.

Codeauswahl

Bose-Ray-Chaudhuri-Code (BCH) Faltungscode Fountain-Code Golay-Code Hamming-Code Low-Density-Parity-Check-Code (LDPC) MDS-Code Nordstrom-Robinson-Code (Preparata-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) Trellis-Code-Modulation (TCM) Turbo-Code (TCC, TPC etc.) Wiederholungscode Woven-Code (Zyklische Redundanzprüfung) (ZRP, engl. CRC, zur Fehlererkennung; Grundlage für ARQ-Verfahren)

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. ¹⁄₃ µ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

• G.821
• Bitfehlerhäufigkeit
• Kanalkodierung
• Kodierungstheorie
• Kreuzsicherung
• Fault-Detection, Fault-Isolation and Recovery Techniques

Literatur

• W. Wesley Peterson, E. J. Weldon, Jr.: Error-Correcting Codes, Second Edition, MIT Press, März 1972, ISBN 978-0-262-52731-6
• Jeremy J. Stone: Multiple burst error correction. In: Information and Control. Band 4, Nr. 4. 1. Dezember 1961, S. 324–331, doi:10.1016/S0019-9958(61)80048-X.
• Thomas Gries: Fehlerkorrekturverfahren mittels Reed-Solomon-Codes für adaptive Teilband-Sprachcodierer. Institut für Fernmeldetechnik, Berlin 1986, urn:nbn:de:kobv:83-opus-17813.
• Robert J. McEliece: BCH ReedSolomon and related codes. In: The theory of information and coding. 2. Auflage. Cambridge University Press, Cambridge / New York 2002, ISBN 0-521-00095-5, S. 230 ff.
• Todd K. Moon: Error Correction Coding. Mathematical Methods and Algorithms. Wiley-Interscience, Hoboken NJ 2005, ISBN 0-471-64800-0.
• Shu Lin, Daniel J. Costello: Error Control Coding. Fundamentals and applications. 2. Auflage. Prentice Hall, Upper Saddle River NJ 2004, ISBN 0-13-042672-5.
• Frank J. Furrer: Fehlerkorrigierende Block-Codierung für die Datenübertragung (= Lehr- und Handbücher der Ingenieurwissenschaften. 36). Birkhäuser, Basel 1981, ISBN 3-0348-5818-3, urn:nbn:de:1111-20130805882.
• Andres Keller: Fehlerschutz. In: Breitbandkabel und Zugangsnetze. Technische Grundlagen und Standards. Springer, Berlin/Heidelberg 2011, ISBN 978-3-642-17631-9, S. 62 ff. urn:nbn:de:1111-20110121222, (books.google.de).
• Matthias Hiller, Michael Pehl, Georg Sigl: Fehlerkorrekturverfahren zur sicheren Schlüsselerzeugung mit Physical Unclonable Functions. In: Datenschutz und Datensicherheit – DuD. Band 39, Nr. 4. 9. April 2015, S. 229–233, ISSN 1614-0702, doi:10.1007/s11623-015-0401-0.

Weblinks

• The Error Correcting Codes (ECC) auf eccpage.com
• Horst Völz: Fehlerkorrektur. (PDF; 1,1 MB) auf horstvoelz.de
• Ulrich Brandt: Fehler korrekt korrigieren. auf elektroniknet.de
• Fehlertoleranter Speicher schützt vor Systemausfällen und Datenverlust – Sicherer Speicher für PC, Server und Workstations. – ECC-Verfahren. auf TecChannel.de
• Jürgen Teich: Grundlagen der Technischen Informatik – Codierung und Fehlerkorrektur. (PDF) auf informatik.uni-erlangen.de