article

Fehlerkorrekturverfahren 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 Übertragungen 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

  • Thermisches und elektronisches Rauschen => Verbreiterung der Entscheidungsschwellen im Augendiagramm => ab und zu wird die Fehlerschwelle überschritten
  • erzeugt weitgehend gleichmäßig verteilte Fehler (die keine Codespreizung erfordern)

Kurzzeitstörungen

  • Elektrische Funken, Kratzer auf CDs
  • mehrere Bits hintereinander fehlerhaft, sehr ungleichmäßige Fehlerverteilung

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 Fehlern häufig durch Störeinflüsse wie zum Beispiel Blitze, Relaisschaltungen, u.s.w. 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 empfangenden 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, was man gerade empfängt. Dies führt dazu, dass auch nachfolgende, richtige 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 8 Bit Nutzdaten mit dem Hamming ECC Verfahren übertragen werden, so sind hierfür zusätzlich 4 Fehlerkorrektur-Bits nötig. Insgesamt müssen also 12 Bit übertragen werden. Nutzdaten: 1 2 3 4 5 6 7 8 0 1 0 0 1 1 0 0 zu übertragene 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 der 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 übertragene 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 XORed: 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 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, an welchen Positionen sie sitzen allerdings nicht.

Fehlerkorrektur

Rückwärtsfehlerkorrektur

Unter Rückwärtsfehlerkorrektur versteht man das Erkennen von Fehlern auf der Empfängerseite, bei dem Fehler durch erneute Übertragung(en) korrigiert werden.

Siehe auch ARQ-Protokoll.

Aktive Rückwärtsfehlerkorrektur
Wird bei TCP/IP benutzt. Ein Paket gilt als übertragen, wenn eine positive Rückantwort kommt (Der Sender weiß dann dass die entsprechenden Puffer nicht mehr benötigt werden).

Passive Rückwärtsfehlerkorrektur
Empfänger kann innerhalb einer gewissen Zeit Rückfragen stellen.
Vor- und Nachteile
Vorteile:
  • Kaum Overhead auf fehlerfreien Leitungen
Nachteile:
  • Nicht für Broadcasting geeignet
  • Latenz
  • Nicht optimal für Kanäle mit relativ konstanter (positiver) Fehlerrate

Vorwärtsfehlerkorrektur

Siehe: Vorwärtsfehlerkorrektur

Fehlerkorrekturcodes
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 (müßte ich raussuchen)
  • AMI-Modulation

Grenzen

Codespreizung

Umwandlung von Bündelfehlern in Einzelbitfehler.

Fehlererkennende und -korrigierende Codes

Fehlerverdeckung

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

Robuste Datenstrukturen

Ausnutzen von physiologischen Effekten und Signaleigenschaften

Technische Beispiele

RAM

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 Disk

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 Matritzenrechnung (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 jeden 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 vor jedem jetzt schon modulierten Rahmen mit einer Synchronisationsinformation ausgestattet (1000000000010000000000101), damit der Player den Anfang des Rahmens wiederfindet und 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, von dem ein Spritzgußwerkzeug hergestellt wird, 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 beschädigt leicht die Bits von 20, 50 oder 100 Bytes, sprich die Bytes von halben oder ganzen Rahmen.

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 Informations-Bytes und 2 x 4 Paritätsbytes) gebildet und anhand der 4 zuletzt zugeführten Paritätsbytes wird nachgerechnet, 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. Wenn es sich um kleine Fehler handelt, kann der Decoder den Fehler sofort korrigieren, handelt es sich um größere Mengen von Fehlern (z.B. Kratzer, sogenannte Burst Fehler) ist dies 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 zeigt sich der Effekt des Interleavings. Die durch den Kratzer beschädigten 20 oder 50 auf der Spur nebeneinaderliegenden Bytes stammten jedes aus einem anderen ursprünglichen Fehlerkorrekturrahmen und sind jetzt wieder auf diese Rahmen verteilt.In diesen Rahmen sind in den allerseltesten Fällen mehr als zwei Bytes fehlerhaft. Zwar tauchen jetzt in vielen Fehlerkorrekturrahmen 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 kann man an einem Beispiel stark vereinfacht demonstrieren: Die beiden Bytes 01001010 und 10010010 sollen mit Paritätsbytes ausgestattet werden. Als Regel für die Berechnung wird angenommen: "Wenn 2 gleiche Ziffern untereinander stehen, wird eine 1 als Paritätsbit genommen, wenn 2 ungleiche Ziffern untereinander stehen, eine 0". Wenn man das praktiziert, 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 getan, der Leser kann die Korrektur selbst vollenden: 01 10010010 00100111. Genauso kann man vorgehen, wenn das zweite Byte gelöscht ist und das erste noch vorhanden.

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

DAB / DVB-T

ADSL

Bei einem ADSL-Anschluss der Telekom, von der Telekom auch T-DSL genannt, ist standardmäßig eine Fehlerkorrektur namens Interleaving eingeschaltet. Hierbei werden die Datenbytes verschiedener Frames vermischt, wodurch eine bessere Fehlerkorrektur gegen Impulsstörungen auf der Leitung möglich ist.

Jedoch benötigt man dies im Normalfall nicht. Interleaving treibt eigentlich nur die Latenz (Ping) in die Höhe, eine so gut wie einwandfreie Datenübertragung ist jedoch auch ohne Interleaving möglich.

Eine abgeschaltete Korrektur wird bei T-DSL Fastpath genannt. Sie eignet sich besonders für Online-Spieler, bei denen die Latenz eine Rolle spielt, das Abschalten von Interleaving kostet bei der Telekom zur Zeit (16. Mai 05) auch noch eine Einrichtungsgebühr + Monatspreis. Bei Arcor z.B. ist das Interleaving standardmäßig ausgeschaltet.

Siehe auch

Weblinks

The Error Correcting Codes (ECC) Page

Digitaltechnik

Detecció d'errors | Error correction and detection | Detección de errores | Code correcteur | 誤り検出 | 오류정정부호 | Kanaalcodering | Коррекция ошибок

 

This article is licensed under the GNU Free Documentation License. It uses material from the "Fehlerkorrekturverfahren".

Home Page • arts • business • computers • games • health • hospitals • home • kids & teens • news • physicians • recreation• reference • regional • science • shopping • society • sports • world