In einer TV-Quizshow bestand eine Aufgabe darin, die richtige Antwort zu einer Frage per »stiller Post« zu übertragen: Ein Promi flüsterte etwas in das Ohr einer Person, die das Gesagte an die nächste weitergab. Die Herausforderung bestand darin, dass sich die (hoffentlich richtige) Antwort über zehn Menschen hinweg durchsetzen musste. Ich kenne das Spielprinzip noch aus der Grundschule – dort schien es allerdings oft witzlos. Weil der Klassenraum recht ruhig war, bereitete uns die Aufgabe keine großen Schwierigkeiten. Ganz anders schien es in der Quizshow: Das Studio mit Hunderten von Zuschauern schuf wohl eine so laute Atmosphäre, dass keine der geflüsterten Antworten fehlerfrei ankam. Im Gegenteil, das Gesagte wurde meist so verzerrt, dass kaum etwas vom ursprünglichen Sinn übrig war.

Tatsächlich sind solche Aufgaben nicht nur für Grundschüler oder TV-Sendungen unterhaltsam, sondern haben eine praktische Relevanz. Unsere gesamte Nachrichtentechnik fußt darauf, Signale über verrauschte Kanäle zu übertragen, ohne dass die relevante Information dabei verloren geht. Denn kein Übertragungsweg ist völlig störungsfrei: Elektromagnetische Wellen beeinflussen das Signal; es wird durch Bandbreitenbegrenzung verzerrt – und selbst kosmische Strahlung aus den Tiefen des Weltraums kann dazu führen, dass eine einzelne Informationseinheit ihren Wert ändert.

Mit einem ähnlichen Problem sah sich der Mathematiker Richard Hamming in den späten 1940er Jahren konfrontiert. Er arbeitete damals in der US-amerikanischen Forschungseinrichtung Bell Labs, in der es schon Computer gab. Allerdings sahen die Maschinen völlig anders aus als die Rechner, mit denen wir heute arbeiten. Eine Eingabe erfolgte nicht über eine Tastatur oder eine Maus, sondern über Lochstreifen: lange Bänder, die mit Löchern versehen sind. Wie alles in der Welt waren auch diese Datenträger nicht makellos. Es kam durchaus vor, dass sich ein Loch an der falschen Stelle befand. In so einem Fall stoppte der Computer die Berechnung und ein Angestellter musste den Fehler händisch beheben (übrigens stammt der noch heute für Softwarekorrekturen gebräuchliche Begriff Patch, englisch für Flicken, von der Praxis, fehlerhafte Löcher mit Klebeband zu verdecken). Hamming war von diesem Prozedere genervt: »Ich dachte mir: ›Verdammt noch mal, wenn die Maschine einen Fehler erkennen kann, warum kann sie dann nicht die Position des Fehlers finden und ihn korrigieren?‹«, sagte er in einem Interview. Und so entwickelte er die ersten leistungsfähigen Codes, durch die ein Computer eben dazu in der Lage ist.

Damit eine automatisierte Korrektur eines Fehlers gelingt, muss der Rechner zuerst überhaupt bemerken, dass sich ein solcher eingeschlichen hat. Für die stille Post ist das einfach: Der Verbreiter der Nachricht vergleicht das von ihm Gesagte mit dem, was die letzte Person in der Reihe gehört hat. In diesem Fall hat er allerdings keine Möglichkeit mehr, rechtzeitig einzugreifen. Für eine Fehlerkorrektur müsste man aufspüren, wo sich der Irrtum ereignet. Wenn man zum Beispiel während des Spiels feststellt, dass eine bestimmte Person ein Wort missversteht, könnte man direkt einhaken und das Weitergegebene richtigstellen. Natürlich ist das nicht im Sinn des Spiels – aber aus informationstheoretischer Sicht durchaus sinnvoll. Hamming suchte also nach einer Möglichkeit, Fehler zuverlässig zu identifizieren und zu lokalisieren.

Schon vor Hammings Überlegungen hatte es Ansätze der Fehlerkorrektur gegeben, aber sie waren nicht besonders zuverlässig. Eine Methode besteht zum Beispiel darin, die Anzahl der Bits zu vervielfachen. Indem man etwa drei Kopien jeder Informationseinheit anfertigt, kann man Fehlern vorbeugen. Wenn ein Bit seinen Wert ändert, lässt sich die Abweichung schnell entdecken und beheben. Allerdings verschlingt dieser Ansatz enorm viel Speicherplatz. Für jedes Bit gibt es gleich doppelt so viele, die nur als Redundanz dienen und keine zusätzliche Information liefern.

Eine weitere Methode, die schon vor Hammings Forschung Anwendung fand, ist viel effizienter und verlangt wenig Speicherplatz. Aber sie dient bloß zur Fehlererkennung, nicht zur Korrektur. Die Idee besteht darin, jeder Nachricht ein »Paritätsbit« hinzuzufügen. Indem man die Nachricht durch einen Binärcode darstellt, der nur aus Nullen und Einsen besteht, gibt das Paritätsbit Aufschluss über die Anzahl der Einsen. Ist deren Anzahl gerade, nimmt das Paritätsbit den Wert Null an, bei einer ungeraden Anzahl ist das Bit hingegen Eins. Wenn sich ein Fehler einschleicht (also ein Bit seinen Wert ändert), passt der Wert des Paritätsbits nicht mit der Anzahl an Einsen in der Nachricht zusammen. Damit weiß man, dass es irgendwo einen Fehler gibt – wo genau, bleibt allerdings unklar. Sollte es zwei Fehler geben, bleibt das gänzlich unbemerkt, da der Wert des Paritätsbits in diesem Fall wieder zu der Nachricht passt.

Hamming ließ sich von den Paritätsbits inspirieren. Anstatt jedoch einen Paritätscheck über alle zu übermittelnden Daten durchzuführen, spaltete er das Problem auf. Er trennte die Nachricht in zwei Hälften und führte Paritätsbits für diese Teile ein. Wie sich herausstellt, ermöglicht es dieser einfache Trick, einzelne Fehler überraschend effizient zu erkennen und zu korrigieren.

Halbiere und herrsche

Um das zu verstehen, kann man den Binärcode einer Nachricht in einer zweidimensionalen Tabelle eintragen. Dann ordnet man mehrere Paritätsbits geschickt an, wodurch sich einzelne Fehler eindeutig lokalisieren lassen. Für eine Nachricht aus beispielsweise elf Nullen und Einsen brauchte Hamming fünf zusätzliche Paritätsbits – was im Vergleich zu redundanten Fehlerkorrekturen erstaunlich wenig ist.

Wie funktioniert das genau? Ein konkretes Beispiel hilft: Angenommen, die zu versendende Nachricht lautet 11010011100. Diese kann man in eine Tabelle mit vier Zeilen und vier Spalten nach einem bestimmten Schema eintragen. In der ersten Reihe sind die ersten drei Spalteneinträge für Paritätsbits reserviert, in der ersten Spalte sind ebenfalls die ersten drei Einträge dafür vorgesehen. Die übrigen elf Felder können mit den Bits der Nachricht befüllt werden.

Den ersten Eintrag der Tabelle ignorieren wir zunächst. Er lässt sich erst bestimmen, wenn alle anderen Felder ausgefüllt sind. Das erste zu kalkulierende Paritätsbit ist also jenes in der ersten Zeile, zweite Spalte. Um den Wert des Bits festzulegen, muss man alle Einsen in der zweiten und vierten Spalte zählen: Wenn es eine gerade Anzahl davon gibt, trägt man eine Null ein, ansonsten eine Eins. In unserem Beispiel gibt es fünf Einsen, daher hat das Paritätsbit ebenfalls den Wert eins.

Um das nächste Paritätsbit (erste Reihe, dritte Spalte) zu berechnen, muss man die Einträge der letzten beiden Spalten untersuchen. In dem genannten Beispiel finden sich insgesamt drei Einsen, so dass das Paritätsbit ebenfalls eins ist.

Für die Paritätsbits in der ersten Spalte (bis auf das allererste) ging Hamming analog vor. Der Eintrag in der zweiten Zeile ergibt sich aus der Anzahl der Einsen in der zweiten und vierten Zeile. Für das konkrete Beispiel findet man vier Einsen und trägt daher eine Null ein.

Den nächsten Eintrag (erste Spalte, vierte Zeile) erhält man entsprechend, indem man die Einsen in der dritten und vierten Zeile zählt. In unserem Beispiel gibt es drei Stück, daher lautet der Eintrag eins.

Damit kennt man nun den Wert von vier Paritätsbits (1, 1, 0, 1), die man beispielsweise ans Ende einer zu übermittelnden Nachricht anhängen kann: 11010011100 1101. Möchte der Empfänger prüfen, ob sich ein Fehler eingeschlichen hat, braucht er nur die Paritätschecks durchzuführen. Gibt es tatsächlich einen Fehler, wird dank der Paritätsbits sofort ersichtlich, wo er sich befindet. Die ersten beiden Paritätsbits liefern die fehlerhafte Spalte, die letzten beiden die fehlerhafte Zeile.

Das lässt sich anhand eines Beispiels veranschaulichen. Angenommen, das fünfte Bit in der Folge 11010011100 würde sich ändern, so dass der Empfänger die Nachricht 11011011100 erhält. In der Tabelle sieht man folgende Einträge:

Wenn man die Werte der Paritätsbits mit den Einträgen der Tabelle vergleicht, erkennt man sofort, dass zwei Werte nicht zu den Daten passen. Das Paritätsbit in der ersten Zeile, zweite Spalte, und jenes in der dritten Zeile, erste Spalte, passen nicht zu den Zahlen in den dazugehörigen Zeilen und Spalten. Damit lässt sich auf das fehlerhafte Bit schließen, das sich in der dritten Zeile, zweite Spalte, befindet. Mit diesem Wissen kann man das fehlerhafte Bit korrigieren, indem man dessen Wert ändert, also in diesem Fall aus der Eins wieder eine Null macht. Auf die Weise lassen sich einzelne Fehler in der übertragenen Nachricht sofort detektieren – selbst wenn die Fehler Paritätsbits selbst betreffen.

Jenseits von einzelnen Fehlern

Den ersten Eintrag in der Tabelle haben wir bisher ignoriert. Dieser ist wieder ein Paritätscheck, der alle 15 Einträge der Tabelle prüft: Gibt es eine gerade Anzahl an Einsen unter den Bits der Nachricht und den Paritätsbits, ist auch der erste Eintrag der Tabelle eine Eins, sonst eine Null. In unserem Beispiel gibt es in der Tabelle insgesamt neun Einsen, daher ist auch der erste Eintrag der Tabelle eine Eins.

Das fünfte Paritätsbit liefert Hinweise darauf, ob sich mehr als ein Fehler in die Daten eingeschlichen hat. Falls es sich um einen einzelnen Fehler handelt, passt der Wert des ersten Tabelleneintrags nicht zu den restlichen Daten. Wenn es aber zwei Fehler sind, stimmt das Paritätsbit mit den restlichen Werten überein. Dafür findet man in den anderen Paritätsbits Ungereimtheiten, wodurch deutlich wird, dass es zwei Fehler im Code gibt.

Angenommen, das fünfte und das siebte Bit der Folge 11010011100 wären fehlerhaft. Die neue Folge lautet demnach 11011001100. In der Tabelle macht sich das folgendermaßen bemerkbar:

In einem der Paritätsbits (erste Zeile, dritte Spalte) erkennt man einen Fehler – in den anderen Paritätsbits aber nicht. Damit könnte man zunächst annehmen, dass es bloß einen einzelnen Fehler in diesem Paritätsbit gibt. Da die gesamte Parität der Daten (erster Eintrag) aber korrekt ist, kann das nicht der Fall sein. Es muss also zwei Fehler geben. Wo genau sie liegen, lässt sich mit der Methode von Hamming allerdings nicht ermitteln.

Ein Durchbruch in der Informationstheorie

Damit hatte Hamming einen Fehlerkorrekturalgorithmus gefunden, der einzelne Fehler korrigiert und zweifache zumindest erkennt. Um 11 Bits zu übermitteln, brauchte er nur 5 Paritätsbits; damit machen sie nur etwas mehr als 31 Prozent der gesamten Datenmenge aus. Das klingt zunächst nicht allzu effizient – aber wie sich herausstellt, wird die Methode mit wachsender Größe leistungsstärker.

Möchte man etwa eine Nachricht mit 32 Bits versenden, müssen sechs davon Paritätschecks dienen, die übrigen 26 Bits können die Nachricht umfassen (somit werden nur noch knapp 19 Prozent der Bits für die Fehlerkorrektur aufgewendet). Je länger die Nachricht wird, desto effizienter ist der zugehörige Hamming-Code: Bei einer Länge von 64 Bit braucht man nur sieben Paritätsbits (knapp 11 Prozent), bei 128 Bit sind acht Paritätsbits nötig (etwas mehr als 6 Prozent) und bei 256 Bit benötigt man bloß neun Paritätsbits (etwa 3,5 Prozent).

Mit dem so genannten Hamming-Code muss man für eine Übertragung mit 2ⁿ Bits nur n + 1 als Paritätsbits vorsehen. Grund dafür ist, dass sich die Daten mit wachsender Größe so effizient in zwei Hälften unterteilen lassen, dass nur wenige Paritätschecks nötig sind, um einen Fehler zu lokalisieren.

Auch wenn die Arbeiten von Hamming inzwischen mehr als 60 Jahre alt sind, finden seine Methoden noch immer Anwendung. Zum Beispiel werden Hamming-Codes in Speichermedien eingesetzt, außerdem in der Satellitenkommunikation. Mit seiner Forschung setzte Hamming den Grundstein für viele weitere Methoden, die es ermöglichen, Fehler zu entdecken und zu beseitigen.

Die Fehlerkorrektur hat sich zu einem lebhaften Forschungsfeld entwickelt. Aktuell sieht sich dieser Bereich durch das Aufkommen von Quantencomputern neuen Herausforderungen ausgesetzt. Denn die Quantenbits, mit denen diese Maschinen rechnen, bergen völlig andere Eigenschaften als die klassischen Informationseinheiten unserer Rechner. Zudem sind die Quantenbits gegenüber Störungen deutlich empfindlicher, so dass eine Quantenfehlerkorrektur unabdingbar ist. Dafür müssen die Ansätze aber völlig neu gedacht werden.