Entwürfe

Fehlererkennung

Wenn binär codierte Daten übertragen oder eingelesen werden, kann es passieren, dass einzelne Werte falsch gelesen werden. Beispielsweise könnte es passieren, dass einzelne Werte der Bitsequenz aus Versehen vertauscht, ausgelassen oder verdoppelt werden. Auf der Empfangsseite kann zunächst nicht festgestellt werden, ob die Daten richtig gelesen wurden, da es den empfangenen Werten nicht unmittelbar anzusehen ist, ob sie richtig oder falsch sind.

Zur Fehlererkennung werden üblicherweise redundante Informationen mit übertragen – also zusätzliche Daten, die sich nach bestimmten Vorgaben aus den eigentlichen Daten berechnen lassen (also keine “neue” Information enthalten). Die Empfangsseite kann dann durch Vergleichen der gelesenen Werte mit den gelesenen redundanten Informationen überprüfen, ob die Daten gültig sind, und eventuell sogar erkannte Fehler korrigieren.

Die einfachste Form der Redundanz besteht darin, dass dieselben Daten mehrmals übertragen werden. Liest die Empfangsseite nicht mehrmals dieselben Werte, weiß sie, dass Übertragungsfehler aufgetreten sind. Der Nachteil dieses Verfahren besteht darin, dass zur Fehlererkennung mindestens die doppelte Menge an Daten verschickt werden muss. Damit die Empfangsseite Fehler so auch korrigieren kann, muss mindestens die dreifache Menge an Daten verschickt werden. In der Praxis werden überlicherweise komplexere Verfahren verwendet, um geringere Mengen redundanter Information zu übertragen, anhand derer trotzdem auf die originale Information zurückgeschlossen werden kann.

Prüfsumme

Eine einfache und vergleichsweise speichersparende Methode zur Fehlererkennung besteht darin, dass eine sogenannte Prüfsumme (engl. checksum) aus den Daten berechnet wird. Dabei werden in der Regel wenige zusätzliche Werte an die zu übertragenden Daten angehängt, die dafür sorgen, dass die Prüfsumme eine bestimmte vorgegebene Eigenschaft hat.

Um zu überprüfen, ob die Daten fehlerhaft sind, wird nach dem Auslesen aus den Daten die Prüfsumme berechnet und die erwartete Eigenschaft überprüft. Ist das nicht der Fall, muss ein Übertragungsfehler stattgefunden haben – die Daten sind nicht in sich konsistent. Je nachdem, wie komplex der Algorithmus zur Berechnung der Prüfsumme ist, können verschiedene Fehlerarten festgestellt oder sogar korrigiert werden.

Zwei sehr einfache und verbreitete Beispiele, um eine Prüfsumme für eine Sequenz von Ganzzahlen oder Bits zu berechnen, sind zum einen die Quersumme (= Summe über alle Elemente der Sequenz und zum anderen die Parität (= Quersumme modulo 2, also “gerade” oder “ungerade”).

• Die Parität wird in der Regel für binäre Daten geprüft. Hier wird an die Daten ein zusätzliches Bit angehängt, das dafür sorgt, dass die Quersumme gerade bzw. ungerade ist.
• Allgemeiner kann bei digitalen Daten ein zusätzlicher Wert angehängt werden, der dafür sorgt, dass die Quersumme durch eine festgelegte Zahl P teilbar ist.

Beide Verfahren erkennen viele Fehler allerdings nicht, beispielsweise ändert sich die Quersumme nicht, wenn einzelne Zahlen oder Bits in der Sequenz versehentlich vertauscht wurden. Die Parität ändert sich nicht, wenn gleich viele 0- und 1-Bits “gekippt” sind (hier rot dargestellt):

Effektivere Verfahren berechnen stattdessen eine gewichtete Quersumme als Prüfsumme, in der die Elemente der Sequenz vor der Summenbildung mit unterschiedlichen Faktoren, die von ihrer Position in der Sequenz abhängen, multipliziert werden. So fällt es beispielsweise mit einer höheren Wahrscheinlichkeit auf, wenn zwei Elemente vertauscht wurden.

Beispiel: Bei Artikelnummern im Format GTIN-13 wird als Prüfsumme eine gewichtete Quersumme berechnet, in der die Stellen abwechselnd mit 1 und 3 multipliziert und summiert werden. Die Artikelnummer ist zulässig, wenn die Prüfsumme durch 10 teilbar ist. Dazu reicht es, eine zusätzliche Ziffer als Prüfziffer an die Artikelnummer anzuhängen.