Rechnernetze

Prüfsummen - Dualaddition

Wir untersuchen hier ein Prüfverfahren, welches die Summe der als Dualzahlen aufgefassten Datenwörter bildet und Überläufe ignoriert. Als Beispiel betrachten wir 16 Bit-Wörter. Die 16 Bits Prüfinformation wird damit durch die Addition der jeweiligen Datenwörter module 2¹⁶=65536 ermittelt.

Offenbar werden mit diesem Verfahren alle einfachen Bitfehler erkannt, da ein einzelner von null verschiedener Term niemals den Rest null lassen kann. Dreifache Bitfehler können bereits nicht alle erkannt werden. So ist 2^r-2+2^r-2+2^r-1=2^r-1+2^r-1=2^r, was nach Division durch 2^r den Rest null lässt (ist r=4, also 2⁴=16, so ist 4+4+8=16). Auch zweifache Bitfehler werden nicht erkannt, wie etwa 2^r-1+2^r-1=2^r (in dem letzten Beispiel 8+8=16). Das Verfahren ist also relativ schwach, was die Sicherheit der Fehlererkennung angeht. Tatsächlich treten bei der Übertragung im Internet häufig unerkannt Fehler auf, die meist erst durch höhere Protokolle oder den Anwender entdeckt werden. Die entsprechenden Standards für diese Verfahren legen zwar ausdrücklich fest, dass nach einer Prüfphase auch untersucht werden sollte, ob das CRC-Verfahren das verwendete Prüfsummenverfahren ablöst, aber bis heute hat man sich nicht dafür entschieden.

Von den zweifachen Bitfehlern werden offenbar nur solche nicht erkannt, die in den "höchstwertigen" Bits stehen. Bei g Codewörtern der Länge r gibt es k=r*g Daten- und r Prüfbits. Mit erhalten wir die Anzahl der möglichen zweifachen Bitfehler, während von diesen nur nicht erkannt werden. Wir erhalten somit als Wahrscheinlichkeit, dass zwei Bitfehler nicht erkannt werden, den Wert

Für r=16, erhalten wir also, dass ca. jeder 256. zweifache Bitfehler nicht erkannt wird. Ähnliche Rechnungen lassen sich auch für drei- und andere Mehrfachbitfehlern durchführen. Für dreifache Bitfehler erhalten wir ähnlich

,

so dass mit den oben genannten Parametern nur jeder 1365. dreifache Bitfehler nicht erkannt wird. Man erkennt an diesen Zahlen, dass auch dieses Verfahren mit einer gewissen Sicherheit Fehler zu erkennen gestattet.