Rechnernetze
|
Rechnernetze |
Fehlerkorrektur mit CRC
In mehreren Protokollen wird mittlerweile das CRC-Verfahren verwendet, um neben Fehlererkennung auch Fehlerkorrektur durchzuführen. Die theoretischen Grundlagen zu dieser interessanten Anwendung sollen hier kurz zusammengefasst werden.
HEC ist ein Prüfpolynom, welches von der CCITT in der Empfehlung I.432 für die Prüfung des vier Byte langen Headers einer ATM-Zelle vorgeschlagen wird. Neben der sicheren Erkennung sämtlicher 1, 2 und 3 Bit-Fehler in dem vier Byte langen Header können sogar 1 Bit-Fehler korrigiert werden. Ebenso werden bei Bluetooth synchrone Datenblöcke (10 Bit) mit einem Generatorpolynom vom Grad 5 geschützt und 1 Bit-Fehler korrigiert (2/3 rate FEC). Damit das Verfahren zur Fehlerkorrektur eingesetzt werden kann, sind die folgenden Eigenschaften zu zeigen:
Dann lässt sich aus dem Rest auf einen 1 Bit-Fehler schließen, bzw. bei Auftreten eines 2 Bit-Fehlers eine Korrektur ablehnen. Um 1. zu zeigen, beweisen wir, dass 1 Bit-Fehler unterschiedliche Reste erzeugen, falls ihr Abstand geringer ist als die Periode eines Bitfilters. Treten an den Stellen r und s zwei 1 Bit-Fehler auf, so gilt jeweils
Addiert man diese beiden Gleichungen, so folgt:
Sind jetzt die beiden Reste gleich, Rr(X)=Rs(X), so ist deren Summe null. Dazu muss aber der Abstand von r und s gleich oder ein Vielfaches der Periode des größten Bitfilters sein. Tritt ein 2 Bit-Fehler auf, so wird dieser erkannt, ist aber nicht korrigierbar. 2 Bit-Fehler lassen sich stets von 1 Bit-Fehler unterscheiden. Seien etwa
Man kann jetzt die Summe beider Polynome bilden und erhält
Ist r von s und t verschieden, so stehen links drei Terme, sonst einer. In beiden Fällen ist jedoch der Rest eines ungeraden Fehlerpolynoms nicht null, also auch
oder
Wir zeigen jetzt, dass ein 1-Bit-Fehler und gewisse 3-Bit-Fehler nicht alleine anhand des Rests unterschieden werden können. Der 1-Bit-Fehler E(X)=X11 lässt den Rest Das folgende Fehlerpolynom mit drei Bitfehlern E(X) = X11·HEC+X11 = X19+X13+X12 hat genau den gleichen Rest, nämlich so dass ein Fehler nicht eindeutig aus dem Rest als 1-Bit-Fehler erkannt werden kann. Dennoch wird das oben beschriebene Verfahren vorgeschlagen, da man auf dem verwendeten Übertragungsmedium (LWL) in der Regel nur von vereinzelten Bitfehlern oder längeren Fehlerbursts ausgeht. Ein entsprechendes Verfahren zur Fehlerkorrektur wird auch bei Bluetooth verwendet. Dort werden zwei verschiedene Fehlerkorrekturverfahren benutzt (die dort forward error correction: FEC genannt werden). Neben dem dreifachen Senden jedes Bits (1/3 rate FEC) wird auch eine Prüfung mit einem Generatorpolynom durchgeführt; 2/3 rate FEC: Generatorpolynom = 110101.
|
