Rechnernetze

Paritätsprüfung von Datenblöcken

Ein Verfahren, welches außer allen ungeraden Bitfehlern auch alle 2-Bit-Fehler, die meisten 4-Bit-Fehler und alle 6-Bit-Fehler erkennt, soll jetzt vorgestellt werden. Es wird vorwiegend in Speichermedien wie Magnetbändern verwendet, da es im Falle eines 1-Bit-Fehlers sogar eine Fehlerkorrektur erlaubt; entsprechend groß ist allerdings auch die Redundanz. In diesem Verfahren werden wieder Gruppen von Bits zusammengefasst, z.B. acht Bits. Über jeweils acht Bits wird dann eine 1-Bit-Prüfsumme gebildet; zusätzlich wird auch noch über jedes achte Bit eine Prüfsumme gebildet. Dieses Verfahren wird dann besonders anschaulich, wenn man die Nachrichtenbits ('x' bzw. 'e' im folgenden Diagramm) als Matrix darstellt, wobei die acht Bits einer Gruppe nebeneinander stehen, während jedes achte Bit untereinander steht. Die vertikale Summe über die Bits des Blocks wird als 'Vertikale Redundanz-Prüfsumme' bezeichnet und VRC (Vertical Redundancy Check) abgekürzt. Das Paritätsbit einer Gruppe wird als 'longitudinale Prüfsumme' (LRC = Longitudinal Redundancy Check) bezeichnet.

Dieses VRC/LRC-Verfahren entdeckt alle ungeraden Bitfehler, sowie alle geraden mit ungerader Anzahl von Bitfehlern in mindestens einer Zeile oder Spalte. 2-Bit-Fehler werden somit immer erkannt, da entweder nur eine Zeile oder nur eine Spalte ein falsches Bit enthalten kann. 4-Bit-Fehler werden zwar nicht mit Sicherheit erkannt, aber von allen möglichen 4-Bit-Fehlern wird die überwiegende Mehrzahl ebenfalls erkannt. Unerkannt bleiben nur jene 4-Bit-Fehler, bei denen die fehlerhaften Bits auf den Eckpunkten eines beliebigen gedachten Rechtecks im Diagramm oben (einschließlich der Prüfbits p) liegen (im Diagramm ist ein solches Rechteck beispielhaft durch 'e' eingezeichnet). Somit ist die Wahrscheinlichkeit, Bitfehler nicht zu erkennen, deutlich verbessert. Im obigen Beispiel ist die Redundanz offenbar: 0.29 = 29%. Bei k=z*s Datenbits werden z+s Prüfbits verwendet. Die Redundanz ist also . Offenbar ist diese minimal, wenn z=s ist, so dass in diesem Fall die Redundanz ist.