Fehlererkennung und Fehlerkorrektur
Daten unterlaufen bei ihrer Übertragung häufig Störungen. Störungsquellen sind unter anderem elektronisches Rauschen und beschädigte Informationsquellen (z. B. Kratzer auf DVD). Erst mit Hilfe von fehlererkennenden Verfahren können fehlerhafte Daten gefunden und mittels Fehlerkorrektur rekonstruiert werden.
Fehlerkorrekturen sind Verfahren, die es ermöglichen, fehlerhafte Daten aus zusätzlicher, wiederholender Information (Redundanz) zu rekonstruieren.
1. Vorwärts- und Rückwerksfehlerkorrektur
Manche Verfahren ermöglichen dem Empfänger der Daten neben der Fehlererkennung auch die Fehlerkorrektur. Diese werden als Vorwärtsfehlerkorrektur bezeichnet. Rückwärtsfehlerkorrektur hingegen ermöglicht lediglich die Feststellung von aufgetreten Fehler bei der Übertragung. Um den Fehler zu korrigieren, muss bei der Quelle der fehlerhafte Teil erneut angefragt werden.
2. Codespreizung
Bei der Codespreizung werden die jeweiligen Bits um das n-fache vervielfacht, mit n = 1, 2, 4, 8, 16...
So entstehen aus dem Block
| 1 0 1 0 0 1 0 0 |
|---|
mit der Spreizung 8 diese 8-Bit-breite Blöcke:
| 11111111 11111111 00000000 11111111 00000000 00000000 11111111 00000000 |
|---|
| 1 0 1 0 0 1 0 0 |
|---|
Insgesamt haben von den 8-Bit-großen Block 3 Bits den Wert 1.
3 ist eine ungerade Zahl. Demnach muss ein Bit mit dem Wert 1 hinzugefügt werden, sodass eine gerade Anzahl an Bits mit dem Wert 1 vorliegt.
| 1 0 1 0 0 1 0 0 1 |
|---|
Es ist auch möglich Bits mit den Wert 0 zu zählen und anschließend auf ungerade Anzahl zu ergänzen und Mischungen beider Varianten. Wichtig ist nur, dass sowohl der Sender als auch der Empfänger sich auf eine Variante einigen.
Mit diesem Verfahren können nur Fehler erkannt werden, wenn sich nur ein oder eine ungeradzahlige Anzahl an Bits verändert. Sobald zwei oder eine geradzahlige Anzahl an Bits sich verändern, ist eine Fehlerfeststellung nicht mehr möglich.
Die Redundanz bei diesem Verfahren liegt bei 1/8 = 0,125 = 12,5%. Die Datengröße steigt dadurch um 12,5%.
3.2 Zweidimensionales Paritätsverfahren
Um dennoch mittels Paritätsbits Fehler sicher erkennen und sogar korrigieren zu können, werden mehrere Datenblöcke in einem Feld angeordnet. So wird zu den Paritätsbit eine Zeile zusätzlich aus allen Bits einer Spalte ein weiteres Paritätsbit gebildet und hinzugefügt. So ergibt sich folgende Matrix:
| Datenblock | 8. Bit | 7. Bit | 6. Bit | 5. Bit | 4. Bit | 3. Bit | 2. Bit | 1. Bit | Paritätsbits |
|---|---|---|---|---|---|---|---|---|---|
| Datenblock 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| Datenblock 2 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| Datenblock 3 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| Datenblock 4 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| Datenblock 5 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| Datenblock 6 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 |
| Datenblock 7 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| Datenblock 8 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
| Paritätsbits | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | - |
Tritt nun ein Fehler auf, kann dieser genau aus den beiden Paritätsbits aus der Spalte und Zeile lokalisiert und korrigiert werden. Auch wenn zwei Fehler auftreten, können diese noch sicher korrigiert werden. 4-Bitfehler werden hingegen nicht mehr zu 100% erkannt. Liegen diese alle nebeneinander in einem 2x2-Feld, wird überhaupt kein Fehler festgestellt.
Die Redundanz liegt bei diesem Verfahrern bei (8+8) / (8*8) = 0,25 = 25%.
3.3 Weitere Kodierungsverfahren
Alle weitere Kodierungsverfahren nutzen ebenfalls Paritätsbit bzw. Prüfwörter. Der Unterschied zu den hier gezeigten Verfahren liegt in ihrer aufwendigeren und komplizierteren Berechnung. So wird beispielsweise beim Reed-Solomon-Code, der unter anderem bei QR-Codes verwendet wird, mehrere hundert Berechnungen durchgeführt, bis das Prüfwort vollständig berechnet wurde.