Bell Labs, 1947
Richard Hamming dołączył do Bell Telephone Laboratories w 1946 roku. Komputery przekaźowe działały tylko w dni robocze, gdy technicy mogli je zresetować po błędach. W weekendy maszyny zatrzymywały się, gdy coś się psulo - pozostawiając zadaniami do poniedziałku.
Hamming był zły. "Jeśli maszyna może wykryć błąd", myślał, "dlaczego nie może go zlokalizować i sprostać?" Ta frustracja, połączona z głębokim zapoznaniem się z arytmetyką binarną i sprawdzaniem parzystości, zapoczątkowała cały proces.
Pierwszy Wgląd: Kwadratowe Kody
Pierwsza idea Hamminga: ułóż bitów wiadomości w prostokątnym układzie m×n, dodaj sprawdzanie parzystości do każdej wiersza i kolumny. Błąd pojedynczy powoduje, że tylko jeden sprawdzanie parzystości w wierszu i kolumnie zawodzi. Ich punkt przecięcia wskazuje pozycję błędu.
Stosunek nadmiarowy: (m+1)(n+1) / mn. Kalkulus mówi Ci, że kwadrat minimalizuje ten stosunek dla stałego rozmiaru wiadomości. Ale gdy m i n rosną, dwukrotny błąd staje się bardziej prawdopodobny - sąd inżynierski bez uniwersalnej odpowiedzi.
Zmniejszanie Nadmiarowości Kwadratowej
4×4 prostokąt przewozi 16 bitów wiadomości z 4 kontrolami wiersza i 4 kontrolami kolumny, plus 1 bit kontrolny rogowy = 9 bitów kontrolnych dla 16 bitów wiadomości.
Stosunek nadmiarowości: (m+1)(n+1) / mn = 25/16 ≈ 1.56.
Dla 10×10 prostokąta: 100 bitów wiadomości, 121 bitów ogółem, nadmiarowość ≈ 1.21.
Syndrom jako Liczba Binarna
Parę tygodni po odkryciu prostokątnego kodu, Hamming jechał w kierunku Nowego Jorku przez pola New Jersey, przemyślają się swoje sukcesy. Wtedy przyszło mu na myśl trójkątne, potem sześcian, potem 4-wymiarowy, 5-wymiarowy...
Każde dodatkowe wymiar poprawiało nadmiar. Kwadrat o boku 2 w n wymiarach używa tylko n+1 kontrolnych bitów dla 2^n wierzchołków. Czy to było optymalne?
Argument liczbowy
n+1 bitów kontrolnych wydziela syndrom: liczbę binarną o (n+1) bitach. Ten syndrom musi zidentyfikować 2^n + 1 różne wyniki: każdą z 2^n pozycji błędów, plus specjalny wynik 'brak błędów'.
2^(n+1) = 2·2^n - prawie wystarczająco. O 1 mniej. Hamming zatrzymał problem.
Kluczowe odkrycie
Później, Hamming wrócił z nową ideą: użyć syndromu samych bitów kontrolnych jako liczby binarnej nazwującej pozycję błędu. Pozycja 1 = 001 binarnie, pozycja 2 = 010 binarnie, pozycja 3 = 011 binarnie itd. Rezerwować zera wszystkie dla 'brak błędów'.
To przekształca syndrom z wyjścia kontrolnych bitów w adres. Kontrolne bity są zaprojektowane tak, aby wygenerować dokładnie ten właściwy adres, gdy pojedynczy bit zostanie przewrócony.
Projektowanie kodu (7,4)
Dla 7-bitowego kodu (3 bitów kontrolnych, 4 bitów wiadomości) pozycje od 1 do 7 w systemie binarnym to: 001, 010, 011, 100, 101, 110, 111.
Kontrolne bit 1 obejmuje pozycje, gdzie bit 0 = 1: pozycje 1, 3, 5, 7.
Kontrolne bit 2 obejmuje pozycje, gdzie bit 1 = 1: pozycje 2, 3, 6, 7.
Kontrolne bit 3 obejmuje pozycje, gdzie bit 2 = 1: pozycje 4, 5, 6, 7.
Bitów kontrolnych zajmują pozycje potęg liczby 2: 1, 2, 4. Bitów wiadomości zajmują resztę: 3, 5, 6, 7.
Jeśli bit 6 przewróci się, kontrolne bity 2 & 3 zawiodą (110 w systemie binarnym = 6). Syndrom toczy 110 = 6. Obróć pozycję 6. Zrobione.
Korekta pojedynczego błędu, detekcja dwóch błędów
Kod Hamminga (7,4) koreluje pojedyncze błędy. Co zrobić, jeśli dwa bity się zakręcą? Bez dodatkowej ochrony dekoder stosuje regułę syndromu i 'korektuje' słowo kodujące na błędne wiadomość - wytłumaczonej korekty ciszy.
SECDED: Dodatkowy bit parzystości
Dodaj pojedynczy bit parzystości p₀, który obejmuje całe słowo kodujące (wszystkie 7 bitów). Teraz syndrom ma 4 wejścia: oryginalne 3 kontrole plus p₀.
``
stary syndrom nowy p₀ znaczenie
000 0 poprawne
000 1 błąd tylko w p₀
xxx 1 pojedynczy błąd, stary syndrom nazywa to
xxx 0 dwukrotny błąd - zflaguj to
``
Cztery przypadki są wyczerpujące. Dwukrotny błąd zakręca dwa razy: stary syndrom nie odczytuje 000 (dwa bity razem zakręcają dwa z jego kontrolnych sprawdzianów), ale p₀ zakręca dwukrotnie i wraca do 0. Oznaczenie xxx + 0 jest nieodwracalne.
Dlaczego SECDED działa
Zasada SECDED wykorzystuje modułową strukturę parzystości. Z parzystością równą 0, każdy pojedynczy zakręcenie zmienia p₀. Każde dwukrotne zakręcenie pozostawia p₀ niezmienionym. Dlatego p₀ liczy błędy modulo 2.
Obraz geometryczny
Hamming doszedł do tego samego miejsca z innego kierunku: geometria analityczna. Przedstaw każdą ciągłą n-bitową jako wierzchołek n-wymiarowego hiperkostki. Jeden obrót bitu przesunie punkt o długość jednego krawędzi wzdłuż jednej osi. Dwa obroty: dwie krawędzi. Odległość między punktami jest odległością Hamminga.
Zdefiniuj sferę Hamminga promienia t wokół słowa kodującego c: wszystkie punkty w odległości t obrotów od c. Dla korekty pojedynczego błędu, t = 1.
Warunek korekty pojedynczego błędu: sfery o promieniu 1 wokół każdego para różnych słów kodujących nie powinny się nakładać. Jeśli się nakładają, otrzymany słowo w przecięciu można przypisać dowolnemu słowu kodującemu, a dekoderek zawodzi.
To przenosi się bezpośrednio na odległość minimalną: sfery o promieniu 1 nie nakładają się, jeśli słowa kodujące są co najmniej 3 odległe (d_min ≥ 3).
Kod (7,4) osiąga d_min = 3. Względność Hamminga: 2^7 / (1 + 7) = 16 = 2^4. Dokładnie 16 słów kodujących. Doskonały kod: 16 sfery o promieniu 1 pokrywają {0,1}^7 bez przestrzeni ani przecięć.
Oceny inżynierskie
Hamming był wyraźny: kodeki korekujące błędy dotyczą ocen inżynierskich, a nie czystej matematyki.
Długość komunikatu: dłuższe komunikaty pozwalają na bardziej efektywne kodowanie (log n bitów parzystości dla n bitów komunikatu). Ale dłuższe komunikaty także gromadzą więcej szumu, zwiększając ryzyko pojedynczego błędu uchylającego się jako fałszywe korekta pojedynczego błędu.
Poziom korekty wobec wykrywania błędów: wymiana jednej korekty błędu na dwie dodatkowe wykrywania błędów. Optymalny podział zależy od charakterystyk szumu kanału.
Wartość utrzymania w polu: gdy sprzęt staje się coraz bardziej złożony, technicy pola nie mogą diagnozować każdego awarii od pierwszych zasad. System samodiagnozujący znacznie zmniejsza wymaganą umiejętność konserwacji. Hamming nazywał to jednym z najważniejszych korzyści, często ważniejszym niż sam wzrost niezawodności.
Sztuka: Szczęście Sprzyja Przygotowanej Mysli
Hamming zakończył rozdział 12 bezpośrednim wyzwaniem. Opisał odkrycie, które wymagało od trzech do sześciu miesięcy pracy, głównie w niezwykłe momenty podczas wykonywania głównych obowiązków w Bell Labs.
Zidentyfikował trzy rzeczy, które to zrobiły:
1. Przygotowanie: głęboka znajomość sprawdzania parności, arytmetyki binarnej & teorii grup, przed pojawieniem się problemu.
2. Przeglądanie sukcesów: świadome powtarzanie poprzednich rozwiązań. Kodek trojkowy przydarzył mu się podczas przemyślania kodu prostokątnego podczas podróży do pracy.
3. Nie przyjmowanie 'wygląda dobrze': raz poparzył palce, przyjmując wyglądające optymalność. Dążył, aż udało mu się udowodnić, że kod jest najlepszy.