Fehlerkorrekturverfahren
| Dieser Artikel bedarf einer Überarbeitung. Eine Begründung befindet sich in der Regel auf der Diskussionsseite. Wenn du Lust hast, verbessere den Artikel und entferne anschließend diesen Baustein. |
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.
| Inhaltsverzeichnis |
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 HDs, 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 (engl. Error Bursts)
Bündelfehler sind Fehler, die abhängig von anderen auftreten (Korrelationsfunktion ist eine Spitze)
Synchronisationsfehler
Sind (meist klängere) Bündelfehler, die neben einem Datenverlust auch zu einem Verlust der Information führen, was man gerade empfängt. Ziemlich schlimm, da auch nachfolgende richtige Bits nicht mehr verwendet werden können. Ethernet z.B. ist Evil, es konvertiert Einzelbitfehler in Synchronisationsfehler.
Beispiele
Fehlererkennung
Parität, CRC, Hashs
Hamming-Distanz und Berechnung
- Verweis auf Hamming-Distanz
- Erkennungs- und Korrekturleistung von Codes mit Hammingdistanz H
Beispiele
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
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-Codierungen
- 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.
Beispiele
Fehlerverdeckung
Ist eine Fehlerkorrektur nicht möglich, wird das s.g. Error Concealment zur Verdeckung von Fehlern angewandt.
Robuste Datenstrukturen
Ausnutzen von physiologischen Effekten und Signaleigenschaften
Technische Beispiele
RAM
RAMs gelten zwar als sehr zuverlässige Datenspeicher, allerdings kann es in Anwendungen mit hoher Zuverlässigkeit ... Weiterhin werden die Bausteine durch die Miniaturierung und Erhöhung der Taktrate immer empfindlicher auf ...
Der klassische PC/XT und PC/AT nutzt eine Fehlererkennung zum Erkennen von Einzelbitfehlern im RAM. Zum Speichern von 8 bits werden insgesamt 9 Speicherzellen genutzt, die ...
In modernen PCs werden die 64 Datenbits und die 8 Paritätsbits für einen H=4 ...
In einigen Servern (Sun) werden die 128 Datenbits und die 16 Paritätsbits für einen H=5 ...
Compact Disk
Bei der Compact Disc wird das sogenannte CIRC-Fehlerkorrekturverfahren verwendet. Dabei werden bei der Codierung aus dem laufenden Datenstrom jeweils 24 Bytes zu einem Fehlerkorrekturrahmen zusammengefaßt und im Prozessor parallel weitergeführt. Die 24 Bytes werden mit 4 Paritätsbytes (Fehlerkorrekturbytes) ausgestattet, die mit Hilfe einer Matritzenrechnung 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 angepaßt 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 Milimeter 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 hhandelt, 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, is standartmäßig eine Fehlerkorrektur Namens Interleaving eingeschaltet. Dabei werden die Daten wieder aufbereitet bzw. verstärkt, falls ein Telefonkabel etc. eine schlechte Verbindung aufweist.
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 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.05.05) auch noch eine Einrichtungsgebühr + Monatspreis.
Links
Literatur
Siehe auch:
- Hash-Funktion
- Hamming-Abstand
- Bitfehlerrate
- Kanalcodierung
- Codierungstheorie
- Vorwärtsfehlerkorrektur
- Error Concealment
Kategorie:Digitaltechnik