Rechnernetze
Home Nach oben

Prüfsummen - Einerkomplement

Die Standards des IP und TCP nennen die Operation zur Berechnung der Prüfsumme Einerkomplement (one's complement). Dieses ist etwas irreführend, da Einerkomplementzahlen (ähnlich wie Zweierkomplementzahlen) nur definiert sind, wenn der Wertebereich nicht überschritten wird. Wird der Wertebereich überschritten, so rechnet man falsch, und dann ist das Ergebnis nicht notwendigerweise definiert. Da hier aber gerade diese Eigenschaft ausgenutzt werden soll, ist genau zu definieren, wie die Prüfsumme gebildet wird. Die genaue Operation wird hier beschreiben (RFC 1071/1141/1624). Da die ursprünglichen Angaben fehlerhaft waren (insbesondere bei der Neuberechnung der Prüfsumme in Routern) sollten die drei oben genannten RFCs verglichen werden.

Die Bitfolgen werden als Dualzahlen (0 .. 65535) aufgefasst und deren Werte addiert. Wird bei einer Addition ein Überlauf beobachtet (Summe größer als 65535), so wird der Überlauf entfernt und eine 1 zu der Summe addiert. Das folgende Beispiel zeigt dieses.

Es soll für die folgenden Daten die Prüfsumme gebildet werden:

A: 1000 0100 0101 1110
B: 1010 1100 0110 0000
C: 0111 0001 0010 1010
D: 1000 0001 1011 0101

Die Addition erfolgt dann nach dem folgenden Schema, wobei wir jeweils einen Übertrag addieren, auch wenn dessen Wert null ist.

A: 1000 0100 0101 1110
 +B: 1010 1100 0110 0000
 = 1 0011 0010 1011 1110
  +       1
 = 0 0011 0010 1011 1111
 +C: 0111 0001 0010 1010
 = 0 1010 0011 1110 1001
 +       0
 = 0 1010 0011 1110 1001
 +D: 1000 0001 1011 0101
 = 1 0010 0101 1001 1110
 +       1
 = 0 0010 0101 1001 1111
1'c 1101 1010 0110 0000

Wird eine null (0000 0000 0000 0000) addiert, so ändert sich das Ergebnis nicht. Wird eine 1111 1111 1111 1111 addiert, so ändert sich das Ergebnis auch nicht, da für n>1:

(216-1 + n)16 = n-1

Diese Operation erzeugt einen Überlauf, so dass jeweils 1 addiert wird, also wieder n herauskommt, z.B.:

  1000 0100 0010 1110
+ 1111 1111 1111 1111
= 1 1000 0100 0010 1101
+       1
  1000 0100 0010 1110

Daher gibt es zwei Operanden, welche die Eigenschaften einer null haben, was auch beim Einerkomplement der Fall ist.

Die obige Rechnung ließe sich auch anders darstellen (und wird in einigen Implementierungen auch so durchgeführt). Als erstes werden sämtliche Daten addiert und dann werden die Werte, die größer sind als 216, durch 216 dividiert und auf das Ergebnis addiert. Dieses muss evtl. wiederholt werden, da das zu einem weiteren Überlauf führen kann.

Mit Hilfe dieses Verfahrens werden scheinbar 1 Bit-Fehler stets erkannt, aber nicht alle ungeraden. So ist etwa

  0000 0000 0000 0011 = 3
+ 0000 0000 0000 0010 = 2
+ 0000 0000 0000 0000 = 0
0000 0000 0000 0101 = 5
+       0  
0000 0000 0000 0101 = 5
+ 1'c 1111 1111 1111 1010 = -5
0000 0000 0000 0000 = 0

und für einen 3 Bit-Fehler erhalten wir:

  0000 0000 0000 0001 = 1
+ 0000 0000 0000 0011 = 3
+ 0000 0000 0000 0001 = 1
0000 0000 0000 0101 = 5
+       0  
0000 0000 0000 0101 = 5
+ 1'c 1111 1111 1111 1010 = -5
0000 0000 0000 0000 = 0

was im Vergleich zu einem einfachen Paritätsprüfverfahren relativ schwach ist.

Ebenso gilt für einen 2 Bit-Fehler mit dem obigen Beispiel:

  0000 0000 0000 0011 = 3
+ 0000 0000 0000 0000 = 0
+ 0000 0000 0000 0010 = 2
0000 0000 0000 0101 = 5
+       0  
0000 0000 0000 0101 = 5
+ 1'c 1111 1111 1111 1010 = -5
0000 0000 0000 0000 = 0

Damit ist dieses Prüfverfahren anderen deutlich unterlegen, so dass bei den verbreiteten Internet-Verfahren (insbesondere TCP) in der Regel mit relativ großen Fehlerwahrscheinlichkeiten zu rechnen ist.