mini|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 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 StrahlungScott Mueller: PC-Hardware-Superbibel. Das komplette Referenzwerk. 16. Auflage. Markt & Technik-Verlag, München 2005, ISBN 3-8272-6794-3. 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 ) 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 korrekt empfangenen Symbolen innerhalb des Fehlerbündels gibt. Der ganzzahlige Parameter wird auch Schutzbereich () 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 korrekte Bits oder mehr betragen. Der Parameter 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.
Fehlererkennung in der Informationstechnik
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: 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 ( und ) 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 (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. Anzahl nötiger Paritätsbits
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.