Bell Labs, 1947
Richard Hamming trat 1946 den Bell Telephone Laboratories bei. Die Relaiscomputer dort liefen nur an Wochentagen, wenn Techniker sie nach Fehlern neu starten konnten. Am Wochenende hielten die Maschinen an, wenn etwas schiefging – wodurch Aufträge bis Montag in der Warteschlange standen.
Hamming war wütend. „Wenn die Maschine einen Fehler erkennen kann," dachte er, „warum kann sie ihn nicht lokalisieren und korrigieren?" Diese Frustration, gepaart mit tiefer Vertrautheit mit binärer Arithmetik und Paritätsprüfungen, schuf die Grundlage.
Erster Einfall: Rechteckige Codes
Hammings erste Idee: Ordnen Sie Nachrichtenbits in einem m×n-Rechteck an, fügen Sie eine Paritätsprüfung für jede Reihe & jede Spalte hinzu. Ein einzelner Fehler führt zu genau einer fehlgeschlagenen Zeilenprüfung & einer fehlgeschlagenen Spaltenprüfung. Ihr Schnittpunkt nennt die Position des Fehlers.
Redundanzquote: (m+1)(n+1) / mn. Kalkül sagt dir, dass ein Quadrat dies für eine feste Nachrichtengröße minimiert. Aber wenn m & n wachsen, wird ein Doppelfehler wahrscheinlicher – eine technische Beurteilung ohne universelle Antwort.
Minimierung der rechteckigen Redundanz
Ein 4×4-Rechteck trägt 16 Nachrichtenbits mit 4 Zeilenprüfungen & 4 Spaltenprüfungen, plus 1 Eck-Paritätsbit = 9 Prüfbits für 16 Nachrichtenbits.
Redundanzquote: (m+1)(n+1) / mn = 25/16 ≈ 1,56.
Für ein 10×10-Rechteck: 100 Nachrichtenbits, 121 Gesamtbits, Redundanz ≈ 1,21.
Das Syndrom als Binärzahl
Ein paar Wochen nach dem Rechteck-Code-Einfall war Hamming auf dem Weg nach New York durch New Jersey Farmland unterwegs und überprüfte mental seine Erfolge. Der Dreieck-Code fiel ihm ein – bessere Redundanz. Dann der Würfel. Dann 4-dimensional, 5-dimensional...
Jede zusätzliche Dimension verbesserte die Redundanz. Ein Hyperwürfel der Seitenlänge 2 in n Dimensionen verwendet nur n+1 Paritätsprüfungen für 2^n Vertices. Aber war das optimal?
Das Zählargument
n+1 Paritätsbits erzeugen ein Syndrom: eine (n+1)-Bit-Binärzahl. Dieses Syndrom muss 2^n + 1 verschiedene Ergebnisse unterscheiden: jede der 2^n Fehlerpositionen plus das spezielle Ergebnis „kein Fehler".
2^(n+1) = 2·2^n – fast genug. Um den Faktor 2 falsch. Hamming legte das Problem beiseite.
Der Schlüsseleinfall
Später kehrte Hamming mit einer neuen Idee zurück: Verwenden Sie das Syndrom selbst als Binärzahl, die die Fehlerposition benennt. Position 1 = binär 001, Position 2 = binär 010, Position 3 = binär 011, usw. Reservieren Sie alle Nullen für „kein Fehler".
Dies transformiert das Syndrom von einer Ausgabe von Paritätsprüfungen in eine Adresse. Die Paritätsprüfungen werden so entworfen, dass sie bei jedem einzelnen Bitflip genau die richtige Adresse erzeugen.
Entwurf des (7,4)-Codes
Für einen 7-Bit-Code (3 Paritätsbits, 4 Nachrichtenbits) sind die Positionen 1 bis 7 in binär: 001, 010, 011, 100, 101, 110, 111.
Paritätsprüfung 1 deckt Positionen ab, bei denen Bit 0 = 1: Positionen 1, 3, 5, 7.
Paritätsprüfung 2 deckt Positionen ab, bei denen Bit 1 = 1: Positionen 2, 3, 6, 7.
Paritätsprüfung 3 deckt Positionen ab, bei denen Bit 2 = 1: Positionen 4, 5, 6, 7.
Paritätsbits belegen Potenzen-von-2-Positionen: 1, 2, 4. Nachrichtenbits belegen den Rest: 3, 5, 6, 7.
Wenn Bit 6 kippt, schlagen Paritätsprüfungen 2 & 3 fehl (110 in binär = 6). Das Syndrom liest 110 = 6. Kippen Sie Position 6. Fertig.
Einzelfehler korrigieren, Doppelfehler erkennen
Der (7,4)-Hamming-Code korrigiert Einzelfehler. Aber was passiert, wenn zwei Bits kippen? Ohne zusätzlichen Schutz wendet der Decoder die Syndrom-Regel an und „korrigiert" das Codewort zur falschen Nachricht – eine stille Fehlkorrektur.
SECDED: Ein weiteres Paritätsbit
Fügen Sie ein einzelnes Paritätsbit p₀ hinzu, das das gesamte Codewort (alle 7 Bits) abdeckt. Jetzt hat das Syndrom 4 Einträge: die ursprünglichen 3 Prüfungen plus p₀.
``
altes Syndrom neues p₀ Bedeutung
000 0 korrekt
000 1 Fehler nur in p₀
xxx 1 Einzelfehler, altes Syndrom nennt ihn
xxx 0 Doppelfehler – kennzeichnen Sie ihn
``
Die vier Fälle sind erschöpfend. Ein Doppelfehler kippt zwei Bits: Das alte Syndrom wird nicht 000 lesen (beide Bits zusammen beschädigen zwei seiner Prüfungen), aber p₀ kippt zweimal und kehrt zu 0 zurück. Das Muster xxx + 0 ist unverwechselbar.
Warum SECDED funktioniert
Die SECDED-Regel nutzt die modulare Struktur der Parität. Mit gerader Parität ändert jedes einzelne Kippen p₀. Jedes Doppelkippen lässt p₀ unverändert. Also zählt p₀ Fehler modulo 2.
Das geometrische Bild
Hamming kam von einer anderen Richtung zum gleichen Ort: analytische Geometrie. Stellen Sie sich jede n-Bit-Zeichenkette als einen Vertex eines n-dimensionalen Hyperwürfels vor. Ein einzelner Bitflip bewegt einen Punkt eine Kantenlänge entlang einer Achse. Zwei Flips: zwei Kanten. Die Metrik ist die Hamming-Distanz.
Definieren Sie eine Hamming-Kugel vom Radius t um ein Codewort c: alle Punkte innerhalb von t Bitflips von c. Für Einzelfehlerkorrektur, t = 1.
Bedingung für Einzelfehlerkorrektur: Kugeln vom Radius 1 um jedes Paar unterschiedlicher Codewörter dürfen sich nicht überlappen. Wenn sie sich überlappen, könnte ein empfangenes Wort in der Überlappung zu beiden Codewörtern gehören und der Decoder schlägt fehl.
Dies wird direkt in minimale Distanz übersetzt: zwei Kugeln vom Radius 1 überlappen nicht, wenn und nur wenn die Codewörter mindestens 3 auseinander sind (d_min ≥ 3).
Der (7,4)-Code erreicht d_min = 3. Hammings Schranke: 2^7 / (1 + 7) = 16 = 2^4. Genau 16 Codewörter. Ein perfekter Code: Die 16 Kugeln vom Radius 1 parkettieren {0,1}^7 ohne Lücken oder Überlappungen.
Technische Urteile
Hamming war explizit: Fehlerkorrigierende Codes beinhalten technische Urteile, keine reine Mathematik.
Nachrichtenlänge: Längere Nachrichten ermöglichen effizientere Kodierung (log n Paritätsbits für n Nachrichtenbits). Aber längere Nachrichten sammeln auch mehr Rauschen, was das Risiko erhöht, dass ein Doppelfehler als falsche Einzelkorrektur durchgeht.
Korrektur- vs. Erkennungsebene: Den Austausch von einer Fehlerkorrektur gegen zwei zusätzliche Fehlererkennungen. Die optimale Aufteilung hängt von den Rauschmerkmalen des Kanals ab.
Feldwartungswert: Mit zunehmender Gerätekomplexität können Feldtechniker jeden Fehler nicht aus ersten Prinzipien diagnostizieren. Ein selbstdiagnostizierendes System reduziert die erforderlichen Fähigkeiten für die Wartung dramatisch. Hamming nannte dies einen der wichtigsten Vorteile, oft wichtiger als der rohe Zuverlässigkeitsgewinn.
Stil: Glück begünstigt den vorbereiteten Verstand
Hamming schloss Kapitel 12 mit einer direkten Herausforderung. Er beschrieb die Entdeckung als Arbeit von drei bis sechs Monaten, größtenteils in seltsamen Momenten, während er seine Hauptaufgaben in den Bell Labs durchführte.
Er identifizierte drei Dinge, die es möglich machten:
1. Vorbereitung: Tiefe Vertrautheit mit Paritätsprüfungen, binärer Arithmetik & Gruppentheorie, bevor das Problem auftauchte.
2. Überprüfen von Erfolgen: Gewohnheitsmäßiges Wiederholen vergangener Lösungen, um ihren Stil zu verinnerlichen. Der Dreieck-Code fiel ihm ein, während er den rechteckigen Code auf einer Fahrt mental überprüfte.
3. Nicht mit „sieht gut aus" zufriedengeben: Er verbrannte sich einmal die Finger, weil er scheinbare Optimalität akzeptierte. Er drückte, bis er beweisen konnte, dass der Code am besten war.