Kody Hamminga: jak komputery wyłapują własne błędy

Dane są kruche. Promień kosmiczny odwraca bit w pamięci RAM. Szum elektryczny zakłóca sygnał. Rysa uszkadza dysk. W świecie, gdzie pojedynczy odwrócony bit może zawiesić system lub uszkodzić plik, jak komputery wciąż działają?

Odpowiedzią jest jedna z najbardziej eleganckich idei w informatyce: kody korekcyjne.

Dlaczego nie można po prostu wysłać danych dwukrotnie?

Naiwne podejście do korekcji błędów to powtarzanie. Każdy bit wysyła się trzy razy: 0 staje się 000, 1 staje się 111. Jeśli odebrane zostanie 010, głosowanie większościowe wskazuje, że prawdopodobnie chodzi o 0.

To działa, ale jest marnotrawne. Aby wysłać 4 bity informacji, trzeba przesłać 12 bitów. To 33% wydajności.

Richard Hamming, pracując w Bell Labs w 1950 roku, zadał lepsze pytanie: Jaka jest minimalna redundancja potrzebna nie tylko do wykrycia, ale i do skorygowania błędów?

Jego odpowiedź zmieniła informatykę na zawsze.

Jak działa kod Hamming(7,4)?

Odkrycie Hamminga miało charakter geometryczny. Zamiast brutalnego powtarzania, bity parzystości umieszcza się na strategicznych pozycjach, gdzie mogą pełnić podwójną funkcję: każdy bit parzystości jednocześnie sprawdza wiele pozycji danych.

Position:   1   2   3   4   5   6   7
Binary:    001 010 011 100 101 110 111
Type:       P1  P2  D1  P4  D2  D3  D4
            ↑   ↑       ↑
         Parity bits at powers of 2

Magia: pozycje 1, 2 i 4 to bity parzystości. Każdy z nich sprawdza wszystkie pozycje, które mają odpowiadający bit ustawiony w swojej reprezentacji binarnej:

• P1 (pozycja 1 = 001) sprawdza pozycje 1, 3, 5, 7 (wszystkie pozycje nieparzyste)
• P2 (pozycja 2 = 010) sprawdza pozycje 2, 3, 6, 7
• P4 (pozycja 4 = 100) sprawdza pozycje 4, 5, 6, 7

Gdy wystąpi błąd, każde sprawdzenie parzystości albo przechodzi (0), albo nie (1). Trzy wyniki tworzą liczbę binarną wskazującą bezpośrednio na pozycję błędu.

Wypróbuj: interaktywny symulator Hamminga

Wprowadź 4 bity danych, zakoduj je, a następnie kliknij dowolny bit, aby zasymulować błąd. Obserwuj, jak detekcja syndromu precyzyjnie wskazuje dokładną lokalizację błędu.

Dlaczego syndrom wskazuje na pozycję błędu?

To jest najpiękniejsza część. Gdy wykonamy operację XOR na wszystkich pozycjach zawierających wartość 1, otrzymujemy bezpośrednio pozycję błędu.

Załóżmy, że bit na pozycji 5 zostaje odwrócony. Pozycja 5 w zapisie binarnym to 101: - Bit 0 jest ustawiony → sprawdzenie P1 nie przechodzi - Bit 1 nie jest ustawiony → sprawdzenie P2 przechodzi - Bit 2 jest ustawiony → sprawdzenie P4 nie przechodzi

Syndrom = 101 = 5. Błąd jest na pozycji 5.

To nie przypadek — Hamming zaprojektował pozycje tak, aby ich reprezentacje binarne kodowały tę informację. Każda pozycja ma unikalną sygnaturę binarną, a sprawdzenia parzystości odczytują tę sygnaturę.

Co się dzieje przy dwóch błędach?

Hamming(7,4) może: - ✓ Wykryć i skorygować dowolny błąd jednobitowy - ✓ Wykryć (ale nie skorygować) błędy dwubitowe - ✗ Trzy lub więcej błędów może zostać błędnie skorygowanych

Dla wyższej niezawodności rozszerzona wersja o nazwie SECDED (Single Error Correction, Double Error Detection) dodaje jeszcze jeden bit parzystości obejmujący wszystkie pozycje. Pamięć ECC RAM w komputerze wykorzystuje właśnie to rozwiązanie.

Gdzie kody Hamminga są stosowane dzisiaj?

Związek z teorią informacji

Praca Hamminga powstała równolegle z przełomową publikacją Claude’a Shannona na temat teorii informacji (1948). Shannon udowodnił, że dla każdego zaszumionego kanału istnieje kod korekcyjny, który pozwala przesyłać dane z dowolnie niskim prawdopodobieństwem błędu — pod warunkiem zaakceptowania pewnej utraty wydajności.

Granica Shannona określa teoretyczne maksimum. Kody Hamminga go nie osiągają, ale są praktyczne, szybkie i eleganckie. Nowoczesne kody, takie jak kody turbo i kody LDPC, zbliżają się do granicy Shannona i napędzają wszystko — od sieci komórkowych 4G/5G po telewizję satelitarną.

Odkrycie stojące za odkryciem

Genialność rozwiązania Hamminga nie polega tylko na tym, że działa — pozycja błędu wyłania się ze struktury. Bity parzystości nie „wiedzą”, gdzie jest błąd; ich wzajemne relacje kodują tę informację w sposób niejawny.

To schemat powtarzający się w wielkiej inżynierii: nie buduj skomplikowanej logiki detekcji. Zaprojektuj system tak, aby odpowiedź wynikała z matematyki.

Najczęściej zadawane pytania

Krótkie podsumowanie

Kody Hamminga rozwiązują problem korekcji błędów przy minimalnej redundancji, umieszczając bity parzystości na potęgach liczby 2, gdzie każdy bit sprawdza określony podzbiór pozycji. Gdy wystąpi błąd, nieudane sprawdzenia parzystości tworzą liczbę binarną wskazującą bezpośrednio na pozycję błędu — bez skomplikowanej logiki, wyłącznie za pomocą operacji XOR. To eleganckie podejście, wynalezione przez Richarda Hamminga w 1950 roku, pozostaje fundamentem wszystkiego — od pamięci ECC, przez kody QR, po komunikację w przestrzeni kosmicznej.

Dalsze lektury

• The Art of Doing Science and Engineering — Richard Hamming — Książka, która zainspirowała ten wpis
• A Mathematical Theory of Communication — Claude Shannon (1948) — Fundament teorii informacji
• Interactive visualization of error-correcting codes — Doskonały film 3Blue1Brown

Ten wpis jest częścią serii Interaktywne eksploracje, w tym Gra w życie Conwaya i Reguła 110. Więcej o podstawach informatyki w archiwum.