Problem: Uszkodzenie Danych

Kiedy przesyłamy dane cyfrowe, podróżują one przez fizyczne medium (kanał), gdzie są narażone na szumy i zakłócenia. Te zaburzenia mogą uszkodzić dane, powodując zamianę bitu '0' na '1' lub odwrotnie. Aby zapewnić niezawodną komunikację, potrzebujemy metod radzenia sobie z tymi błędami.

Najprostszym podejściem jest wykrywanie błędów. Jedną z najstarszych i najprostszych technik jest kontrola parzystości. Do bloku danych dodawany jest pojedynczy bit parzystości, ale ma on poważne ograniczenie: potrafi wykryć, że wystąpił pojedynczy błąd, ale nie jest w stanie powiedzieć nam, który bit jest błędny, a co za tym idzie, nie potrafi go naprawić. W tym miejscu wkraczają bardziej zaawansowane kody, takie jak kody Hamminga.

Wprowadzenie do Kodów Hamminga

Kody Hamminga to rodzina liniowych kodów korekcyjnych, wynalezionych przez Richarda Hamminga w latach 50. XX wieku. Stanowią one znaczący krok naprzód w stosunku do prostej kontroli parzystości, ponieważ potrafią nie tylko wykrywać błędy pojedyncze i podwójne, ale także korygować błędy pojedyncze. Jest to możliwe dzięki dodaniu do danych starannie skonstruowanej redundancji.

Potęga Odległości Hamminga

Zdolność kodu do korygowania błędów jest określana przez jego minimalną odległość Hamminga. Aby kod mógł:

• Wykryć do $d$ błędów, jego minimalna odległość musi wynosić $d_{min} \ge d + 1$.
• Poprawić do $t$ błędów, jego minimalna odległość musi wynosić $d_{min} \ge 2t + 1$.

Standardowy kod Hamminga ma minimalną odległość $d_{min} = 3$. Oznacza to, że potrafi poprawić $t = \lfloor (3-1)/2 \rfloor = 1$ błąd pojedynczy oraz wykryć do $d = 3 - 1 = 2$ błędów podwójnych. Dzięki temu, że prawidłowe słowa kodowe są od siebie "daleko", pojedynczy błąd spowoduje powstanie uszkodzonego słowa, które wciąż będzie "bliżej" swojej oryginalnej, prawidłowej formy niż jakiegokolwiek innego prawidłowego słowa kodowego, co pozwoli odbiorcy je naprawić.

Analiza Przypadku: Kod Hamminga (7,4)

Najbardziej klasycznym przykładem jest kod Hamminga (7,4), który demonstruje wszystkie podstawowe zasady. Notacja (n, k) oznacza:

• $k = 4$: liczba bitów danych w oryginalnej wiadomości.
• $n = 7$: całkowita liczba bitów w finalnym zakodowanym słowie.
• Oznacza to, że dodajemy $n-k = 3$ nadmiarowe bity parzystości.

Standardowa Konstrukcja: Bity Parzystości na Pozycjach Potęg Dwójki

Aby skonstruować 7‑bitowe słowo kodowe, rozmieszczamy bity danych i parzystości w określonym porządku. Pozycje bitów są numerowane od 1 do 7. Dla spójności z interaktywnym przykładem i diagramami na tej stronie, prezentujemy bity od lewej do prawej jako 7 → 1 (bit 7 po lewej, bit 1 po prawej).

• Bity Parzystości ($P_1, P_2, P_4$) są umieszczane na pozycjach będących potęgami dwójki (1, 2, 4).
• Bity Danych ($D_3, D_5, D_6, D_7$) są umieszczane na pozostałych pozycjach (3, 5, 6, 7).

Reguły Kontroli Parzystości

Każdy bit parzystości sprawdza unikalny zestaw pozycji (włączając swoją własną). Zasada jest następująca: bit parzystości na pozycji $2^i$ sprawdza wszystkie pozycje bitowe $j$, których reprezentacja binarna ma '1' na $i$-tym miejscu.

• $P_1$ (pozycja 1, binarnie 001): Sprawdza pozycje 1, 3, 5, 7 (te z '1' na ostatniej pozycji binarnej).
• $P_2$ (pozycja 2, binarnie 010): Sprawdza pozycje 2, 3, 6, 7 (te z '1' na środkowej pozycji binarnej).
• $P_4$ (pozycja 4, binarnie 100): Sprawdza pozycje 4, 5, 6, 7 (te z '1' na pierwszej pozycji binarnej).

Wizualizacja Logiki: Diagram Venna

Te złożone zależności można łatwo zwizualizować za pomocą diagramu Venna. Każde koło reprezentuje zbiór bitów kontrolowanych przez jeden bit parzystości. Celem (przy użyciu parzystości parzystej) jest zapewnienie, że w każdym kole znajduje się parzysta liczba jedynek.

Zauważ, jak bity danych znajdują się na przecięciach kół. Na przykład bit danych $D_7$ jest we wszystkich trzech kołach, więc jest sprawdzany przez wszystkie trzy bity parzystości ($P_1, P_2, P_4$). To sprytne nakładanie się na siebie obszarów pozwala nam zlokalizować dokładne miejsce błędu.

Przykładowe Działanie: Kodowanie i Korekcja Błędu

Krok 1: Kodowanie Wiadomości

Zakodujmy 4-bitowe słowo danych 1011. Używamy parzystości parzystej, co oznacza, że każdy bit parzystości jest ustawiany na '0' lub '1', aby całkowita liczba jedynek w jego grupie była parzysta.

1. Umieść bity danych (lewo→prawo 7→1): Dane (D3, D5, D6, D7) to 1, 0, 1, 1.
   1 1 0 _ 1 _ _
2. Oblicz $P_1$ (sprawdza 1,3,5,7): $P_1 \oplus D_3 \oplus D_5 \oplus D_7 = P_1 \oplus 1 \oplus 0 \oplus 1 = 0$. Aby suma była parzysta, $P_1$ musi być 0.
   1 1 0 _ 1 _ 0
3. Oblicz $P_2$ (sprawdza 2,3,6,7): $P_2 \oplus D_3 \oplus D_6 \oplus D_7 = P_2 \oplus 1 \oplus 1 \oplus 1 = 0$. Aby suma była parzysta, $P_2$ musi być 1.
   1 1 0 _ 1 1 0
4. Oblicz $P_4$ (sprawdza 4,5,6,7): $P_4 \oplus D_5 \oplus D_6 \oplus D_7 = P_4 \oplus 0 \oplus 1 \oplus 1 = 0$. Aby suma była parzysta, $P_4$ musi być 0.
   1 1 0 0 1 1 0
5. Przesyłane słowo (lewo→prawo 7→1): 1100110

Krok 2: Wykrywanie i Korekcja Błędu

Teraz wyobraź sobie, że słowo kodowe jest przesyłane, ale szum zmienia 3. bit od lewej (pozycja 5) z '0' na '1'. Odbiornik otrzymuje uszkodzone słowo 1110110.

Odbiornik wykonuje te same sprawdzenia parzystości na otrzymanym słowie:

• Sprawdzenie 1 (dla $P_1$; pozycje 1,3,5,7): $0 \oplus 1 \oplus 1 \oplus 1 = 1$. Liczba jedynek jest nieparzysta (3). Błąd! Bit syndromu S₁ = 1.
• Sprawdzenie 2 (dla $P_2$; pozycje 2,3,6,7): $1 \oplus 1 \oplus 1 \oplus 1 = 0$. Liczba jedynek jest parzysta (4). OK. Bit syndromu S₂ = 0.
• Sprawdzenie 3 (dla $P_4$; pozycje 4,5,6,7): $0 \oplus 1 \oplus 1 \oplus 1 = 1$. Liczba jedynek jest nieparzysta (3). Błąd! Bit syndromu S₄ = 1.

Łączymy bity syndromu, od największej do najmniejszej pozycji ($S_4 S_2 S_1$), tworząc liczbę binarną: 101. Dziesiętnie, $101_2 = 4 + 0 + 1 = 5$. Jest to klasyczny indeks Hamminga (1..7, liczony od prawej). W naszym układzie prezentacji 7 → 1 odpowiada to 3. bitowi od lewej.

Ten wynik, 5, to dokładna pozycja uszkodzonego bitu!

Aby poprawić błąd, odbiornik po prostu odwraca bit na 5. pozycji w otrzymanym słowie 1110110, co zamienia je z powrotem w oryginalne, prawidłowe słowo kodowe: 1100110.

Interaktywny Hamming (7,4)