Kodierungstheorie

Wenn Daten von einem Ort zum anderen wandern, gehen unterwegs Teile kaputt. Ein Funksignal wird gestört, ein Kratzer beschädigt eine DVD, ein Speicherchip kippt ein einzelnes Bit um. Die Kodierungstheorie ist das Teilgebiet der Mathematik, das genau dieses Problem behandelt. Ihre Grundidee: Man schreibt die Daten absichtlich etwas länger auf als nötig und fügt zusätzliche Prüfstellen hinzu. Aus diesen Zusatzstellen kann der Empfänger später berechnen, ob etwas fehlt, und oft sogar, was ursprünglich dort stand. Das Ziel ist also nicht Geheimhaltung, sondern Zuverlässigkeit.

Warum jede Funkverbindung darauf angewiesen ist

Kein realer Übertragungsweg ist störungsfrei. Bei Mobilfunk reflektieren Häuserwände das Signal, bei Satelliten ist die Strecke einfach zu lang. Ohne Fehlerkorrektur müsste ein Gerät jedes beschädigte Datenpaket neu anfordern. Bei schlechter Verbindung würde man dann fast nichts mehr übertragen.

Mit guten Codes lässt sich stattdessen ein bestimmter Anteil an Fehlern direkt vor Ort reparieren. Das erlaubt schnellere Verbindungen bei gleicher Sendeleistung. Ein berühmtes Beispiel sind die Voyager-Sonden: Ihre Signale kamen extrem schwach an, waren aber durch Codes so geschützt, dass die Bilder trotzdem rekonstruierbar waren. Ein Antwort-Anfordern über Stunden Signallaufzeit wäre gar nicht praktikabel gewesen.

Wichtig ist die Abgrenzung zur Kryptografie. Kryptografie schützt Daten davor, dass Unbefugte sie lesen. Kodierungstheorie schützt sie davor, dass sie durch Zufall unlesbar werden. Beides wird meist zusammen eingesetzt, hat aber völlig verschiedene Ziele.

Redundanz, Abstand und Prüfstellen

Das einfachste Verfahren ist Wiederholung: Man sendet jedes Bit dreimal. Kommt „101“ an, war ursprünglich wohl eine Eins gemeint, denn zwei von drei Stellen sagen das. Dieses Vorgehen funktioniert, ist aber verschwenderisch, weil es die Datenmenge verdreifacht. Die Kodierungstheorie sucht Verfahren, die mit viel weniger Zusatzstellen dieselbe Sicherheit erreichen.

Der zentrale Begriff dabei ist der Abstand zwischen zwei erlaubten Codewörtern. Man legt fest, welche Bitfolgen überhaupt gültig sind, und wählt sie so, dass sich je zwei davon in mehreren Stellen unterscheiden. Kommt eine ungültige Folge an, sucht der Empfänger das nächstgelegene gültige Codewort. Je größer der Abstand, desto mehr gleichzeitige Fehler lassen sich noch eindeutig korrigieren.

Man kann sich das wie Vokabeln einer Sprache vorstellen. Wenn alle Wörter sehr ähnlich klingen, führt ein Verhörer sofort zu einem anderen Wort. Klingen die Wörter dagegen deutlich verschieden, erkennt man das gemeinte Wort auch bei Nebengeräuschen. Bekannte Familien solcher Codes heißen Hamming-Code, Reed-Solomon-Code und LDPC-Code.

Von der QR-Code-Ecke bis ins Rechenzentrum

Ein QR-Code auf einem Plakat funktioniert oft noch, wenn ein Teil überklebt oder verschmutzt ist. Dahinter steckt ein Reed-Solomon-Code, der einen Teil der Fläche für Prüfinformationen reserviert. Dasselbe Prinzip erlaubt es, CDs mit kleinen Kratzern fehlerfrei abzuspielen.

In Rechenzentren sichern verwandte Verfahren große Datenmengen. Statt jede Datei mehrfach zu speichern, verteilt man sie mit sogenannten Erasure Codes auf viele Festplatten und legt Prüfblöcke dazu. Fällt eine Platte aus, wird ihr Inhalt aus den übrigen berechnet. Das spart gegenüber vollständigen Kopien viel Speicherplatz.

In Tech-News tauchen Fehlerkorrekturcodes vor allem bei zwei Themen auf: bei neuen Mobilfunkgenerationen und bei Quantencomputern. Deren Rechenbausteine sind extrem störanfällig, weshalb dort tausende physische Bausteine ein einziges verlässliches Rechenbit tragen müssen. Ein typischer Irrtum ist übrigens, Kodierungstheorie mit Datenkompression zu verwechseln: Kompression entfernt Redundanz, Fehlerkorrektur fügt sie gezielt wieder hinzu.