Rechnernetze
Home Nach oben Prüfgruppen Blockparität CRC-Verfahren

Paritätsprüfung

Eine sehr einfache Methode zur Fehlererkennung bei binär kodierten Daten ist die folgende: 

Füge ein Bit Prüfinformation hinzu, so dass die Anzahl aller Bits mit dem Wert 1 gerade ist. 

Ein solches Prüfbit wird Paritätsbit (parity bit) genannt; man spricht auch von gerader Parität. Vereinbart man, dass die Anzahl aller Bits ungerade sein muss, so nennt man dieses ungerade Parität. Wir werden im folgenden stets die gerade Parität verwenden. Statt die Anzahl der Bits zu zählen, lassen sich diese auch aufaddieren, wobei jeweils modulo 2 zu rechnen ist. Man kann somit auch von einer Paritätssumme sprechen.

Für die Redundanz eines Prüfverfahrens mit Paritätsbit für ein Datenwort mit k Bits erhalten wir nach der Definition von Redundanz:

Redundanz bei der Paritätsprüfung = 1/k.

Wird genau ein Bit verfälscht, also z.B. eine '1' zu einer '0', so ändert sich offenbar sofort die Parität, d.h. die Anzahl aller '1'en wird ungerade. Ein solcher Fehler kann daher erkannt werden. Dieses gilt ebenfalls für jede andere ungerade Anzahl von verfälschten Bits. Wird jedoch eine gerade Anzahl von Bits verfälscht, also '2', '4', '6' usw., so wird die Anzahl aller '1'en weiterhin gerade bleiben; diese Fehler werden somit nicht erkannt.

Das Paritätsprüfverfahren ist zwar mit einem Bit 'Prüfsumme' nicht sehr zuverlässig, aber dieses Verfahren lässt sich noch sehr verbessern; heutige Prüfverfahren bestehen im Prinzip aus einem verallgemeinerten Paritätsprüfverfahren. Dazu kann man sich vorstellen, dass entweder die Blocklängen verkürzt werden, oder – was dem entspricht – die Anzahl der Prüfbits erhöht wird. Würde z.B. für jeweils 10 Bits ein Prüfbit eingefügt werden, so würde sich die Fehlerwahrscheinlichkeit stark verringern. Natürlich müssen die geprüften Bits nicht unbedingt nebeneinander stehen. Wegen der Möglichkeit von Bitfehlerhäufungen wäre es sogar günstiger, es würde nur jedes zehnte Datenbit mit jeweils einem Prüfbit kontrolliert werden, also: Prüfbit 1 zählt die Anzahl der '1'en im ersten, elften, einundzwanzigsten, usw. Bit, Prüfbit 2 im zweiten, zwölften, usw. Bit. Wir erhalten:

Prüfbit Überwachte Bits
1 1 11 21 31 41 51 61 71 81 91
2 2 12 22 32 42 52 62 72 82 92
3 3 13 23 33 43 53 63 73 83 93
... ...
10 10 20 30 40 50 60 70 80 90 100

Eine Verallgemeinerung dieses Verfahrens werden wir später kennen lernen. Tritt in einem derartigen Block eine ungerade Anzahl von Bitfehlern auf, so lässt sich dieses erkennen. Es gibt aber immer noch Gruppen von Bitfehlern, die nicht erkannt werden.

Der Nachteil des hier geschilderten Verfahrens ist es, dass die Anzahl der Prüfbits von der Datenmenge abhängt, was die Redundanz sehr groß macht. Es gibt aber Verfahren, bei denen die Anzahl der Prüfbits stets konstant ist, während die Qualität der Prüfung darunter nicht sehr leidet. Hierzu zählen allgemeine Prüfsummenverfahren, die tatsächlich Werte addieren, und das CRC-Verfahren, welches Reste nach einer Polynomdivision als Prüfwerte verwendet. Beide Verfahren werden heute in sehr vielen Anwendungen eingesetzt und werden daher hier genauer untersucht.