Kürzlich hat mir meine Mutter eine Textnachricht geschickt. Sie hat mir darin von der »Malteser Brücke« in meiner Heimatstadt erzählt. Ich war verwirrt, denn obwohl ich lange dort gelebt habe, war mir diese Brücke unbekannt. Erst mit ein wenig Nachdenken bin ich darauf gekommen, dass sie die »Mauterner Brücke« gemeint haben muss und es sich einfach nur um ein typisches Beispiel einer fehlerhaften Autokorrektur gehandelt hat. In diesem Fall habe ich das durch meine Ortskenntnis schnell erkannt, in anderen Fällen kann es aber deutlich schwerer sein, solche Fehler zu finden. Helfen kann dabei diese Formel:

$$d_H(x,y)=\sum _{j=1}^n|x_i-y_i|$$

Sie stammt vom US-amerikanischen Mathematiker Richard Hamming, der schon 1945 im Rahmen des Manhattan-Projekts an der Programmierung der damals gerade erst entwickelten digitalen Computer gearbeitet hat. Später war er Mitarbeiter der Bell Labs und fütterte die dortigen Rechner mit seinen auf Lochkarten gespeicherten Programmen. Die sollten übers Wochenende die entsprechenden Resultate liefern – das taten sie jedoch nur, wenn es zwischendurch keinen Fehler gab.

Fehler sind aber oft genug passiert. Und zwar so oft, dass Hamming sich nicht nur geärgert, sondern auch eine Lösung gesucht hat: Der Computer sollte Fehler entdecken und gleich selbst korrigieren können.

Das Problem ist hier ein wenig anders gelagert als bei dem Beispiel der Malteser und der Mauterner Brücke. Einem Computer fehlt nicht nur die Ortskenntnis, er weiß generell nichts von den Dingen, die er bearbeitet. Nehmen wir an, wir wollten der Maschine die Zahlenfolge »011010« übermitteln. Wenn dabei ein Übertragungsfehler auftritt, dann kommt vielleicht stattdessen »010010« an. Wie soll ein Computer das merken? Man könnte versuchen, die Zeichen einfach zu verdoppeln. Wenn dann statt »00 11 11 00 11 00« die Folge »00 11 01 00 11 00« ankommt, ist auf jeden Fall klar, dass ein Fehler aufgetreten ist.

Autokorrektur für Computer

Aber der Computer hat keine Möglichkeit, herauszufinden, wie die korrekte Ziffer aussieht. Das Problem lässt sich lösen, wenn man die Zeichen verdreifacht. Bei »011« ist es viel wahrscheinlicher, dass die einzelne 0 falsch ist – und nicht zweimal aus Versehen eine 1 übermittelt wurde. Aber mit dieser Methode verdreifacht sich auch die Übertragungszeit und das ist oft ebenso unerwünscht wie eine fehlerhafte Kommunikation.

Hamming hat deswegen ein Codesystem entwickelt, bei dem – vereinfacht gesagt – jedem Datenblock ein binäres Codewort zugewiesen wird. Die sind dabei so gewählt, dass sie möglichst unterschiedlich voneinander sind und nicht verwechselt werden können. Um das auch mathematisch beschreiben zu können, hat Hamming die obige Formel entwickelt: Zwei Worte (oder Zahlen) x und y, die durch jeweils n Symbole x_i und y_i dargestellt werden, haben einen Hamming-Abstand dH , der der Anzahl der unterschiedlichen Symbole entspricht.

Zum Beispiel unterscheiden sich die Namen PETER und PETRA an den beiden letzten Stellen voneinander; ihr Hamming-Abstand ist daher gleich 2. Der Name KLAUS ist an jeder einzelnen Stelle unterschiedlich und hat sowohl von Peter als auch von Petra einen Abstand von 5. Will man zwei Namen, die möglichst nicht verwechselt werden können, sind Klaus und Petra also eine bessere Wahl als Peter und Petra.

Hammings Codewörter waren natürlich keine Namen, sondern binäre Zahlen. Die waren aber so gewählt, dass zwischen ihnen ein ausreichend großer Abstand existiert, wodurch sie unverwechselbar waren. Der Hamming-Abstand erfüllt übrigens alle Kriterien einer Metrik, ist also tatsächlich aus mathematischer Sicht eine Abstandsfunktion wie die, die wir auf der Landkarte verwenden. Nur dass hier der Abstand zwischen A und B immer gleich 1 ist.