Rechnernetze
Home Nach oben

Paritätsprüfgruppen zur Fehlererkennung

Wir stellen hier ein Paritätsprüfverfahren vor, welches die im Abschnitt über Fehlerkorrektur eingeführten Prüfgruppen verwendet. Werden die Bits einer Bitfolge durchnummeriert (0, 1, 2, .. , n) und diese Nummern binär dargestellt, so gehört Bit m in die Paritätsgruppe q, wenn in m der binäre Term 2q vorkommt. Die Bits mit der Nummer 1, 2, 4, 8, ... , 2q, ... ,2r-1 werden als Paritätsbits verwendet, wie im Falle der Fehlerkorrektur; die anderen Bits können als Datenbits verwendet werden. Außerdem gebe es ein Paritätsbit, welches den gesamten Datenblock überprüft, so dass jede ungerade Anzahl von Bitfehlern erkannt werden kann.

Treten zwei Bitfehler auf, so können diese entweder nur in den Datenbits vorkommen, in den Datenbits und in den Prüfbits oder nur in den Prüfbits. Im letzteren Fall wird kein Fehler in den Datenbits übersehen, aber natürlich wird auch dieser Fehler erkannt.

Zwei Bitfehler in den Datenbits führen dazu, dass in mindestens einer Prüfgruppe die Parität verfälscht wird. Also wird auch dieser Fehler erkannt. Tritt ein Bitfehler in den Datenbits, ein weiterer in den Prüfbits auf, so kann natürlich das Datenbit in der gleichen Prüfgruppe sein, in welcher der Fehler aufgetreten ist. Aber da jedes Datenbit mindestens in zwei Prüfgruppen ist (nur die Prüfbits sind in genau einer Prüfgruppe) wird auch dieser Fehler erkannt. Somit haben wir ein Verfahren, welches aller ungeraden Bitfehler, aber auch sämtliche doppelten Bitfehler erkennt. Vierfache Bitfehler werden natürlich nicht mit Sicherheit erkannt, wie mit einem Beispiel leicht gezeigt wird.

Beispiel für nicht erkannte vierfache Bitfehler

Fehler in den Bits 6 (2+4) und 12 (4+8) verfälschen die Prüfgruppen mit den Prüfbits 21=2 und 23=8. Werden also die Bits 2, 6, 8 und 12 verfälscht, so zeigt dieses Verfahren keinen Fehler an. Dennoch werden mit diesem Verfahren auch sehr viele vierfache Bitfehler erkannt

Die Redundanz dieses Verfahren hängt von der Anzahl der überwachten Bits ab. Für jeweils bis zu k=2r-r Bits werden r+1 Prüfbits benötigt. Die Redundanz beträgt also wpe2.jpg (1714 Byte). Die folgende Tabelle gibt für einige Werte von r die maximale Anzahl von Datenbits sowie die Redundanz an.

Üblich sind heute Prüfsummen mit 8, 12, 16, 24 oder 32 Bits. Man sieht, dass in diesen Bereichen die möglichen Blocklängen bzw. die Redundanzen durchaus noch vertretbar sind. Bei diesem Verfahren kann allerdings im Gegensatz zu anderen wie dem CRC-Verfahren die Anzahl der Prüfbits den Datenlängen angepasst werden, wenngleich der sich hieraus ergebenden Leistungsgewinn relativ gering sein dürfte.

Um dieses Verfahren zu implementieren, kann man die Prüfgruppen in ein Prüfwort der Länge r speichern und die Datenbits ab dem Bit 3 durchnumerieren, wobei die Prüfbitnummern 1, 2, 4, 8, ... , 2q, ... ,2r-1 natürlich übersprungen werden. Hat ein Datenbit den Wert 1, so wird die Nummer dieses Datenbits mittels der Xor-Operation mit dem Prüfwort verknüpft; das Ergebnis wird dem Prüfwort zugewiesen. Nach dem Ende dieser Operation für alle Datenbits enthält das Prüfwort die Prüfbits der jeweiligen Prüfgruppen. Der Aufwand dieses Verfahrens ist offenbar proportional k, also vertretbar. Die Prüfbits lassen sich offenbar auch "On-the-Fly" realisieren, indem die bitweise Übertragung der Datenbits jeweils eine neue Berechnung des Prüfworts nach sich zieht. Nach der Übertragung des letzten Datenbits kann dann das Prüfwort und das Paritätsbit über das gesamte Wort übertragen werden.