Bell Labs, 1947
Richard Hamming trat 1946 in die Bell Telephone Laboratories ein. Die Relaiscomputer dort liefen nur an Werktagen, wenn die Techniker sie nach Fehlern neu starten konnten. Am Wochenende hörten die Maschinen auf, wenn etwas schiefging - die angesammelten Aufträge mussten bis Montag warten.
Hamming war wütend. 'Wenn die Maschine einen Fehler erkennen kann', dachte er, 'warum kann sie ihn nicht auch lokalisiert und korrigiert?' Diese Frustration, kombiniert mit einer tiefen Vertrautheit mit binärer Arithmetik und Paritätsprüfungen, legte den Grundstein.
Erster Einblick: Rechteckige Codes
Hamming erste Idee: Die Nachrichtenbits in einem m×n-Rechteck anordnen und eine Paritätsprüfung für jede Zeile und jede Spalte hinzufügen. Ein einzelner Fehler produziert genau einen fehlgeschlagenen Zeilenprüfung und eine fehlgeschlagene Spaltenprüfung. Ihr Durchkreuzung nennt die Position des Fehlers.
Redundanzverhältnis: (m+1)(n+1) / mn. Der Kalkül sagt dir, dass ein Quadrat diese Redundanz minimiert, wenn die Nachrichtengröße festgelegt ist. Aber je mehr m und n wachsen, wird ein Doppelfehler wahrscheinlicher - eine Ingenieurbeurteilung ohne universelles Antwort.
Minimierung der rechteckigen Redundanz
Ein 4×4-Rechteck trägt 16 Nachrichtenbits mit 4 Zeilenprüfungen und 4 Spaltenprüfungen, plus 1 Ecken-Paritätsbit = 9 Prüfungsbits für 16 Nachrichtenbits.
Redundanzverhältnis: (m+1)(n+1) / mn = 25/16 ≈ 1.56.
Für ein 10×10-Rechteck: 100 Nachrichtenbits, 121 Bits insgesamt, Redundanz ≈ 1.21.
Das Syndrom als binäres Zahlensystem
Einige Wochen nach dem rechteckigen Code-Erkenntnis kam Hamming auf dem Weg nach New York durch New Jersey Landwirtschaft, indem er seinen Erfolg im Geist überprüfte. Dann das Dreieckskode, dann das Kubi
Jeder zusätzliche Bereich verbesserte die Redundanz. Ein Hyperkubus mit einer Seitenlänge von 2 in n Dimensionen verwendet nur n+1 Paritätsprüfungen für 2^n Ecken. War dies jedoch optimal?
Die Zählungsargument
n+1 Paritätsbits erzeugen ein Syndrom: eine (n+1)-bitige binäre Zahl. Dieses Syndrom muss 2^n + 1 verschiedene Ergebnisse identifizieren: jede der 2^n Fehlerpositionen, plus das besondere 'kein Fehler' Ergebnis.
2^(n+1) = 2·2^n - fast genug. Um einen Faktor von 2 fehlt. Hamming legte das Problem zur Seite.
Der Schlüsselerkenntnis
Später kehrte Hamming mit einer neuen Idee zurück: Verwenden Sie das Syndrom selbst als binäres Zahl, das die Fehlerposition bezeichnet. Position 1 = binär 001, Position 2 = binär 010, Position 3 = binär 011 usw. Reservieren Sie Null-Null 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 genau die richtige Adresse erzeugen, wenn ein einzelner Bit umgeworfen wird.
Entwerfen des (7,4) Codes
Für einen 7-Bit-Code (3 Paritätsbits, 4 Nachrichtenbits) sind die Positionen 1 bis 7 im binären Format: 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 befinden sich in Potenzen von 2 positionen: 1, 2, 4. Nachrichtenbits befinden sich in den übrigen: 3, 5, 6, 7.
Wenn Bit 6 umgeworfen wird, schlagen die Paritätsprüfungen 2 & 3 fehl (110 im binären Format = 6). Das Syndrom lautet 110 = 6. Umkehren Sie die Position 6. Erledigt.
Einzel-Fehlerkorrektur, Doppel-Fehlererkennung
Das (7,4)-Hamming-Code korrigiert Einzelfehler. Was aber, wenn zwei Bits umgekehrt werden? Ohne zusätzliche Schutzausrüstung greift der Decoder die Regel des Syndroms und 'korrigiert' den Codewort falsch - eine stumme Fehlkorrektur.
SECDED: Ein zusätzlicher Paritätsbit
Fügen Sie einen Paritätsbit hinzuge, der p₀ deckt und den gesamten Codewort (alle 7 Bits) abdeckt. Jetzt hat das Syndrom 4 Einträge: die ursprünglichen 3 Prüfungen plus p₀.
``
alt Syndrom neuer p₀ Bedeutung
000 0 korrekt
000 1 Fehler nur in p₀
xxx 1 Einzelfehler, der alte Syndrom benennt
xxx 0 Doppelfehler - kennzeichnen
``
Die vier Fälle sind erschöpfend. Ein Doppelfehler umkehrt zwei Bits: Das alte Syndrom liest nicht 000 (beide Bits verändern zwei seiner Prüfungen), aber p₀ umkehrt zweimal und kehrt zu 0 zurück. Das Muster xxx + 0 ist eindeutig.
Warum SECDED funktioniert
Die SECDED-Regel nutzt die modulare Struktur der Parität. Bei ungerader Parität ändert jede einzelne Umkehrung p₀. Jede doppelte Umkehrung lässt p₀ unverändert. Daher zählt p₀ Fehler modulo 2.
Das geometrische Bild
Hamming kam von einer anderen Seite: analytische Geometrie. Darstelle jedes n-Bit-Zeichen als Eckpunkt eines n-dimensionalen Hyperwürfels. Ein Einzelbitflip bewegt einen Punkt um eine Kantenlänge entlang einer Achse. Zwei Flips: zwei Kanten. Die Metrik ist die Hamming-Distanz.
Definiere einen Hamming-Kreis mit Radius t um ein Codewort c: alle Punkte innerhalb von t Bitflips von c. Für die Korrektur eines Einzelfehlers: t = 1.
Bedingung für die Korrektur eines Einzelfehlers: Kreise mit Radius 1 um jeden Paar von verschiedenen Codewörtern dürfen sich nicht überschneiden. Wenn sie sich überschneiden, kann ein empfangenes Wort im Überlappungsbereich zu beiden Codewörtern gehören und der Decoder schlägt fehl.
Das überträgt sich direkt auf die minimale Distanz: zwei Kreise mit Radius 1 überschneiden sich nicht, wenn und nur wenn die Codewörter mindestens 3 voneinander entfernt sind (d_min ≥ 3).
Das (7,4)-Code erreicht d_min = 3. Hamming's Grenze: 2^7 / (1 + 7) = 16 = 2^4. Genau 16 Codewörter. Ein perfektes Code: Die 16 Kreise mit Radius 1 füllen {0,1}^7 ohne Lücken oder Überschneidungen aus.
Technische Urteile
Hamming war explizit: Fehlerkorrektur-Codes beinhalten technische Urteile, nicht rein mathematische Themen.
Nachrichtenlänge: Längere Nachrichten ermöglichen effizientere Codierung (log n Paritätsbits für n Nachrichtenbits). Aber längere Nachrichten sammeln auch mehr Rauschen an, was das Risiko erhöht, dass ein Doppelfehler als falsche Einzelkorrektur durchgeht.
Ebenen der Korrektur gegenüber der Detektion: Händen eines Fehlerkorrektur für zwei zusätzliche Fehlerdetektionen ab. Die optimale Aufteilung hängt von den Schaltungsmerkmalen des Rauschens ab.
Wert der Feldwartung: Je komplexer die Ausrüstung wird, können Feldtechniker nicht jede Fehlfunktion von Grund auf diagnostizieren. Ein selbstdiagnostisches System verringert die erforderlichen Fähigkeiten für Wartung drastisch. Hamming nannte dies einen der wichtigsten Vorteile, oft wichtiger als der reinen Zuverlässigkeitsgewinn.
Stil: Glück begünstigt den vorbereiteten Geist
Hamming schloss Kapitel 12 mit einer direkten Herausforderung. Er beschrieb die Entdeckung als möglich, dass es drei bis sechs Monate Arbeit, meist in ungewöhnlichen Momenten, während der Hauptaufgaben bei Bell Labs, erforderte.
Er identifizierte drei Dinge, die es möglich gemacht haben:
1. Vorbereitung: tiefe Vertrautheit mit Paritätsprüfungen, binären Arithmetik & Gruppentheorie, bevor das Problem aufgetreten ist.
2. Überprüfung von Erfolgen: habituelles Wiederholen von vergangenen Lösungen, um ihre Art intern zu verinnerlichen. Das Dreieckscode ist ihm während des Pendelns auf dem Weg zur Arbeit gekommen, während er über das Rechteckcode nachdachte.
3. Nicht zufrieden mit ‚sieht gut aus‘: Er verbrühte sich einmal, indem er offensichtliche Optimalität akzeptierte. Er drängte weiter, bis er beweisen konnte, dass der Code am besten war.