Kreuzsicherung
Die Kreuzsicherung ist ein Verfahren zur Fehlererkennung bei der Übertragung digitaler Daten. Es beruht auf der Überprüfung der Parität der empfangenen Daten.
Verfahren
Einfache Paritätsprüfungen beziehen sich auf relativ kurzen Bitfolgen, die man auch Codewörter nennt. Eine einfache Überprüfung der Parität gibt lediglich einen Hinweis, ob es zu einem Übertragungsfehler bei dem Codewort gekommen ist, nicht jedoch, welches Bit betroffen ist. Außerdem wird ein kombinierter Übertragungsfehler, der sowohl ein Bit im Codewort als auch das Prüfbit betrifft, nicht erkannt.
Die Kreuzsicherung ist ein Verfahren, das beide Nachteile der einfachen Paritätsprüfung weitgehend beheben kann. Hierzu wird eine Folge von k Codewörtern der Länge n in einer Matrix aus k Zeilen und n Spalten angeordnet. Nun wird für jede Zeile und jede Spalte die Parität berechnet. Die k Paritätsbits der Zeilen und die n Paritätsbits der Spalten ergeben jeweils ein Prüfzeichen, die zusammen mit den Codewörtern übertragen werden.
Der Empfänger ordnet ebenfalls die Codewörter als Matrix an und berechnet die Parität der Zeilen und Spalten. Anschließend vergleicht er die lokal berechneten Prüfzeichen mit den übertragenen. Stimmen sie überein, kann mit großer Sicherheit davon ausgegangen werden, dass bei der Übertragung kein Fehler aufgetreten ist.
Fehlerkorrektur
Ein Fehler in einem einzelnen Bit der Codewörter bewirkt, dass sich sowohl die Parität für die entsprechende Spalte als auch für die Zeile des Bits in der Matrix ändert. Andere Fehlermöglichkeiten, wie etwa zwei falsch übertragene Bits in den Codewörtern, oder einzelne Bitfehler in den Prüfzeichen haben andere Folgen für die Parität. Dieser Zusammenhang kann ausgenutzt werden, um den Übertragungsfehler zu korrigieren. Angenommen, bei der Überprüfung stellt sich heraus, dass das zweite Bit des Spalten-Prüfzeichens und das dritte Bit des Zeilen-Prüfzeichens sich zwischen lokal berechneten und übertragenen Daten unterscheidet. Dann kann davon ausgegangen werden, dass das zweite Bit der dritten Zeile fehlerhaft übertragen wurde. Falls dieses Bit mit dem Wert "1" empfangen wurde, ist der korrekte Wert also "0". Auf ähnliche Weise kann erkannt werden, ob und wenn ja, welches Bit in den Prüfzeichen falsch übertragen wurde. Der Fehler kann lokal beim Empfänger korrigiert werden, ohne dass erneut Daten übertragen werden müssen. Man spricht daher von einer Vorwärtsfehlerkorrektur.
Grenzen der Zuverlässigkeit
Die lokale Fehlerkorrektur versagt, wenn mehr als ein Bitfehler in der Matrix der Codewörter und den Prüfzeichen auftritt. Bis auf sehr unwahrscheinliche Ausnahmen wird dennoch erkannt, dass es Übertragungsfehler gab. Zur Korrektur muss die betroffene Matrix der Codewörter erneut übertragen werden. Der Ausnahmefall bei dem Übertragungsfehler fälschlich nicht erkannt werden tritt auf, wenn mehrere Bits koordiniert in bestimmtem Mustern betroffen sind. Ein Beispiel wäre ein gleichzeitiger Fehler des dritten Bits des Spalten-Prüfzeichens, des vierten Bits des Zeilenprüfzeichens und des dritten Bits des vierten Codeworts. Diese Fälle sind offensichtlich sehr selten. Sie können jedoch bei Prüfverfahren, die auf dem Vergleich der Parität beruhen grundsätzlich nicht völlig ausgeschlossen werden.
Beispiel mit einer Matrix aus 5 Codewörtern der Länge 8 Bit
| Codewort | Parity Bit | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | |
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | |
| 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | |
| Parity Bit | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | |
mit einem Fehler:
| Codewort | Parity Bit | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | |
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | |
| 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | |
| 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | |
| Parity Bit | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | |
In Zeile 3 und Spalte 2 stimmen die übermittelten nicht mehr mit den berechneten Parity-Bits überein.