Rechnernetze

Eigenschaften einiger Generatorpolynome

Die Überlegungen im letzten Abschnitt sollen hier auf praktisch relevante Generatorpolynome angewendet werden. In der Praxis werden Polynome des Grads 5, 8, 16 oder 32 verwendet. Es können auch andere benutzt werden, je nach Anwendung.

Das erste Polynom CRC–16 wird häufig eingesetzt und ist daher sehr wichtig. Es hat im wesentlichen die gleichen Eigenschaften wie das Generatorpolynom CRC–CCITT.

Es gibt genau zwei disjunkte Bitfilter der Periode 2¹⁵-1=32767, wie durch Konstruktion der entsprechenden Bitfilter gezeigt werden kann. Da es insgesamt 2¹⁶ verschiedene Bitfilter gibt, gibt es nur noch die beiden weiteren Bitfilter 000… und 111… Daher werden bei allen Blöcken, die nicht länger als 4095 Bytes sind, alle Fehler mit einer ungeraden Anzahl von Bitfehlern, alle 2-Bit-Fehler, sowie alle Fehlerbursts, die nicht länger als 16 Bits sind, erkannt.

Während die ersten beiden Generator-Polynome, die jeweils eine gerade Anzahl von Termen besitzen, mit Sicherheit alle ungeraden Bitfehler erkennen, hat das dritte eine ungerade Anzahl von Termen und kann somit nicht alle ungeraden Bitfehler erkennen (beispielsweise die Bitfolge der Generatorpolynoms 100000100110000010001110110110111).

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. Die Periode der Bitfilter ist 127, so dass sämtliche 1, 2 und 3-Bit-Fehler in dem vier Byte langen Header mit Sicherheit erkannt werden. Allerdings geht die Empfehlung I.432 noch weiter, indem sogar 1-Bit-Fehler korrigiert werden. Da ein 1-Bit-Fehler jedoch nicht mit Sicherheit als solcher (1-Bit-Fehler) erkannt werden kann, wird diese Korrektur nur einmal in einer Folge von ATM-Zellen durchgeführt. Tritt bei der nächsten ATM-Zelle ebenfalls ein 1- oder Mehrbit-Fehler auf, so werden diese Zellen und alle folgenden fehlerhaften verworfen.

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. 

Die Wahrscheinlichkeit, einen Fehler nicht zu entdecken, hängt auch von den verwendeten Daten ab, sowie von der Fehlercharakteristik des verwendeten Kanals. Empirische Untersuchungen für gute Fehlercodes benötigen normalerweise sehr große Stichproben. In einem Beispiel wurden bei 157.000 Blöcken der Länge 2048 Bits beim CRC-32 keine unentdeckten Fehler beobachtet. Eine Berechnung der Wahrscheinlichkeit für unentdeckte Fehler ergab, dass diese kleiner als 10^-14 ist.

Wir fassen an dieser Stelle noch einmal zusammen, welche Fehler mit Hilfe eines Generatorpolynoms erkannt werden können.