Bell Labs, 1947
Richard Hamming dołączył do Bell Telephone Laboratories w 1946 roku. Komputery przekaźnikowe tam pracowały tylko w dni robocze, gdy technicy mogli je uruchomić ponownie po błędach. W weekendy maszyny zatrzymywały się za każdym razem, gdy coś poszło nie tak — zostawiając zadania w kolejce do poniedziałku.
Hamming był wściekły. „Jeśli maszyna może wykryć błąd" — myślał — „dlaczego nie może go znaleźć i poprawić?" To frustracja, połączona z głęboką znajomością arytmetyki binarnej i bitów parzystości, przygotowała grunt.
Pierwsze Odkrycie: Kody Prostokątne
Pierwsza idea Hamminga: ułożyć bity wiadomości w prostokąt m×n, dodać bit parzystości do każdego wiersza & każdej kolumny. Pojedynczy błąd powoduje dokładnie jedną nieudaną kontrolę wiersza & jedną nieudaną kontrolę kolumny. Ich przecięcie wskazuje pozycję błędu.
Stosunek redundancji: (m+1)(n+1) / mn. Rachunek różniczkowy mówi, że kwadrat minimalizuje to dla stałej wielkości wiadomości. Ale w miarę jak m & n rosną, podwójny błąd staje się bardziej prawdopodobny — inżynieryjna ocena bez uniwersalnej odpowiedzi.
Minimalizacja Redundancji Prostokątnej
Prostokąt 4×4 nosi 16 bitów wiadomości z 4 kontrolami wierszy & 4 kontrolami kolumn, plus 1 bit parzystości rogu = 9 bitów kontrolnych dla 16 bitów wiadomości.
Stosunek redundancji: (m+1)(n+1) / mn = 25/16 ≈ 1,56.
Dla prostokąta 10×10: 100 bitów wiadomości, 121 bitów łącznie, redundancja ≈ 1,21.
Syndrom jako Liczba Binarna
Kilka tygodni po odkryciu kodu prostokątnego Hamming jechał w kierunku Nowego Jorku przez krajobraz New Jersey, myślowo przeglądając swoje sukcesy. Przyszła mu idea kodu trójkątnego — lepsza redundancja. Potem sześcianu. Potem 4-wymiarowego, 5-wymiarowego...
Każdy dodatkowy wymiar poprawiał redundancję. Hipersześcian o boku 2 w n wymiarach używa tylko n+1 bitów parzystości dla 2^n wierzchołków. Ale czy to było optymalne?
Argument Liczenia
n+1 bitów parzystości produkuje syndrom: liczbę binarną (n+1)-bitową. Ten syndrom musi zidentyfikować 2^n + 1 odrębnych wyników: każdą z 2^n pozycji błędu, plus specjalny wynik „brak błędu".
2^(n+1) = 2·2^n — prawie wystarczająco. Różni się o czynnik 2. Hamming odłożył problem.
Kluczowe Odkrycie
Później Hamming powrócił z nową ideą: użyć samego syndromu jako liczby binarnej wskazującej pozycję błędu. Pozycja 1 = binarnie 001, pozycja 2 = binarnie 010, pozycja 3 = binarnie 011, itd. Zarezerwuj same zera dla „brak błędu".
To transformuje syndrom z wyniku kontroli parzystości w adres. Kontrole parzystości są zaprojektowane tak, aby produkować dokładny adres, gdy zmienia się któryś bit.
Projektowanie Kodu (7,4)
Dla kodu 7-bitowego (3 bity parzystości, 4 bity wiadomości), pozycje od 1 do 7 w systemie binarnym to: 001, 010, 011, 100, 101, 110, 111.
Kontrola parzystości 1 obejmuje pozycje, gdzie bit 0 = 1: pozycje 1, 3, 5, 7.
Kontrola parzystości 2 obejmuje pozycje, gdzie bit 1 = 1: pozycje 2, 3, 6, 7.
Kontrola parzystości 3 obejmuje pozycje, gdzie bit 2 = 1: pozycje 4, 5, 6, 7.
Bity parzystości zajmują pozycje potęg 2: 1, 2, 4. Bity wiadomości zajmują resztę: 3, 5, 6, 7.
Jeśli bit 6 się zmieni, kontrole parzystości 2 & 3 nie powiodą się (110 w systemie binarnym = 6). Syndrom odczyta 110 = 6. Zmień pozycję 6. Gotowe.
Korekcja Pojedynczego Błędu, Wykrywanie Podwójnego Błędu
Kod Hamminga (7,4) koryguje pojedyncze błędy. Ale co jeśli dwa bity się zmienią? Bez dodatkowej ochrony dekoder zastosuje regułę syndromu i „poprawi" słowo kodowe na złą wiadomość — cichą błędną korektę.
SECDED: Jeden Dodatkowy Bit Parzystości
Dodaj pojedynczy bit parzystości p₀ obejmujący całe słowo kodowe (wszystkie 7 bitów). Teraz syndrom ma 4 wpisy: oryginalne 3 kontrole plus p₀.
``
stary syndrom nowy p₀ znaczenie
000 0 poprawnie
000 1 błąd tylko w p₀
xxx 1 pojedynczy błąd, stary syndrom go wskazuje
xxx 0 podwójny błąd — oznacz go
``
Cztery przypadki są wyczerpujące. Podwójny błąd zmienia dwa bity: stary syndrom nie będzie czytać 000 (oba bity razem psują dwie jego kontrole), ale p₀ zmienia się dwukrotnie i powraca do 0. Wzór xxx + 0 jest nie do pomylenia.
Dlaczego SECDED Działa
Reguła SECDED wykorzystuje modularną strukturę parzystości. Przy parzystości parzystej, każda zmiana zmienia p₀. Każda zmiana podwójna pozostawia p₀ niezmienione. Zatem p₀ liczy błędy modulo 2.
Geometryczny Obraz
Hamming dotarł do tego samego miejsca z innego kierunku: geometrii analitycznej. Reprezentuj każdy ciąg n-bitowy jako wierzchołek n-wymiarowego hipersześcianu. Zmiana pojedynczego bitu przesunęła punkt o długość krawędzi wzdłuż jednej osi. Dwie zmiany: dwie krawędzie. Metryką jest odległość Hamminga.
Zdefiniuj piłkę Hamminga o promieniu t wokół słowa kodowego c: wszystkie punkty w obrębie t zmian bitów od c. Dla korekcji pojedynczego błędu, t = 1.
Warunek korekcji pojedynczego błędu: piłki o promieniu 1 wokół każdej pary odrębnych słów kodowych nie mogą się nakładać. Jeśli się nakładają, odebrane słowo w obszarze nakładania mogłoby należeć do każdego słowa kodowego, a dekoder zawodzi.
To tłumaczy się bezpośrednio na minimalną odległość: dwie piłki o promieniu 1 się nie nakładają wtedy i tylko wtedy, gdy słowa kodowe są oddalone co najmniej 3 (d_min ≥ 3).
Kod (7,4) osiąga d_min = 3. Granica Hamminga: 2^7 / (1 + 7) = 16 = 2^4. Dokładnie 16 słów kodowych. Kod doskonały: 16 piłek o promieniu 1 pokrywa {0,1}^7 bez luk lub nakładań.
Inżynierskie Oceny
Hamming był wyraźny: kody korekcji błędów obejmują inżynierskie osądy, nie czystą matematykę.
Długość wiadomości: dłuższe wiadomości pozwalają na bardziej efektywne kodowanie (log n bitów parzystości dla n bitów wiadomości). Ale dłuższe wiadomości również gromadzą więcej szumu, zwiększając ryzyko, że podwójny błąd przejdzie jako fałszywa pojedyncza korekta.
Poziom korekcji vs. wykrywania: wymiana jednej korekcji błędu na dwa dodatkowe wykrywania błędów. Optymalny podział zależy od charakterystyki szumu kanału.
Wartość konserwacji terenowej: w miarę jak urządzenia stają się bardziej złożone, technicy terenowi nie mogą zdiagnozować każdego błędu z pierwszych zasad. System samodiagnostyczny drastycznie zmniejsza umiejętności wymagane do konserwacji. Hamming nazwał to jedną z najważniejszych korzyści, często ważniejszą niż czysty wzrost niezawodności.
Styl: Szczęście Sprzyja Przygotowanemu Umysłowi
Hamming zamknął Rozdział 12 bezpośrednim wyzwaniem. Opisał odkrycie jako wymagające trzech do sześciu miesięcy pracy, głównie w dziwnych momentach, podczas pełnienia swoich głównych obowiązków w Bell Labs.
Zidentyfikował trzy rzeczy, które to umożliwiły:
1. Przygotowanie: głęboka znajomość kontroli parzystości, arytmetyki binarnej, & teorii grup, przed pojawieniem się problemu.
2. Przegląd sukcesów: zwyczajowe powtarzanie przeszłych rozwiązań, aby internalizować ich styl. Idea kodu trójkątnego przyszła mu na myśl, gdy myślowo przeglądał kod prostokątny w drodze do pracy.
3. Niezadowolenie się „wygląda dobrze": raz spalił palce, przyjmując pozorną optymalność. Naciskał, aż mógł udowodnić, że kod jest najlepszy.