Kod Hamminga | Teleinf Edu

Problem: uszkodzenie danych

Podczas transmisji dane cyfrowe przechodzą przez fizyczne medium (kanał), w którym 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 obsługi tych błędów.

Podstawowym podejściem jest wykrywanie błędów. Do najstarszych technik należy kontrola parzystości. Do bloku danych dodawany jest pojedynczy , ale ma on poważne ograniczenie. Potrafi wykryć, że wystąpiła nieparzysta liczba błędów, lecz nie wskazuje, który bit jest błędny i nie umożliwia jego korekcji. Kody Hamminga dostarczają dodatkowych informacji kontrolnych potrzebnych do zlokalizowania i skorygowania pojedynczego błędu bitowego.

Wprowadzenie do kodów Hamminga

Kody Hamminga to rodzina liniowych kodów korekcyjnych opisana przez Richarda Hamminga w 1950 roku. W porównaniu z pojedynczym bitem parzystości ich bity kontrolne tworzą syndrom, który wskazuje pojedynczy błędny bit i umożliwia korygowanie błędów pojedynczych. W standardowym kodzie odległość minimalna pozwala również wykryć każdy błąd dwóch bitów. Osiąga się to przez dodanie do danych starannie skonstruowanej .

Odległość Hamminga i zdolność kodu

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

Wykryć do $e$ błędów, jego minimalna odległość musi wynosić $d_{min} \ge e + 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 $e = d_{min} - 1 = 2$ błędów. Przy takiej odległości słowo z jednym zmienionym bitem ma jednoznacznie wyznaczalne prawidłowe słowo w zasięgu korekcji, więc odbiornik może zidentyfikować i poprawić ten błąd.

Kod Hamminga (7,4) jest kodem korygującym pojedynczy błąd (SEC) o $d_{min} = 3$ . Dodanie jednego globalnego bitu parzystości tworzy rozszerzony kod Hamminga (8,4) o $d_{min} = 4$ . Konwencjonalny dekoder SEC-DED koryguje błędy jednego bitu i wykrywa błędy dwóch bitów bez ich korygowania. Dla trzech lub większej liczby błędów wynik korekcji dekodera nie jest gwarantowany.

Analiza przypadku: kod Hamminga (7,4)

Kod Hamminga (7,4) jest standardowym przykładem przedstawiającym 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. Prezentujemy bity od lewej do prawej jako pozycje od 1 do 7 (pozycja 1 po lewej, pozycja 7 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_1, D_2, D_3, D_4$ ) zajmują 4 bity danych wejściowych i są umieszczane na pozostałych pozycjach (3, 5, 6, 7).

Pozycja (lewo→prawo):       1   2   3   4   5   6   7
Bit:                        P₁  P₂  D₁  P₄  D₂  D₃  D₄

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

Diagram Venna przedstawia te zależności. Każde koło reprezentuje zbiór bitów kontrolowanych przez jeden bit parzystości. Przy parzystości parzystej celem jest zapewnienie, aby w każdym kole znajdowała się parzysta liczba jedynek.

Przecięcia pokazują, które kontrole parzystości obejmują poszczególne bity danych. Na przykład bit danych $D_4$ (na pozycji 7) jest we wszystkich trzech kołach, więc jest sprawdzany przez wszystkie trzy bity parzystości ( $P_1, P_2, P_4$ ). To nakładanie się obszarów pozwala syndromowi wskazać dokładne miejsce pojedynczego 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.

Umieść bity danych od lewej do prawej na pozycjach od 1 do 7: Dane (D₁, D₂, D₃, D₄) to 1, 0, 1, 1.
_ _ 1 _ 0 1 1
Oblicz $P_1$ (sprawdza 1,3,5,7): $P_1 \oplus D_1 \oplus D_2 \oplus D_4 = P_1 \oplus 1 \oplus 0 \oplus 1 = 0$ . Aby suma była parzysta, $P_1$ musi być 0.
0 _ 1 _ 0 1 1
Oblicz $P_2$ (sprawdza 2,3,6,7): $P_2 \oplus D_1 \oplus D_3 \oplus D_4 = P_2 \oplus 1 \oplus 1 \oplus 1 = 0$ . Aby suma była parzysta, $P_2$ musi być 1.
0 1 1 _ 0 1 1
Oblicz $P_4$ (sprawdza 4,5,6,7): $P_4 \oplus D_2 \oplus D_3 \oplus D_4 = P_4 \oplus 0 \oplus 1 \oplus 1 = 0$ . Aby suma była parzysta, $P_4$ musi być 0.
0 1 1 0 0 1 1
Przesyłane słowo (pozycje od 1 do 7, od lewej do prawej): 0110011

Krok 2: wykrywanie i korekcja błędu

Załóżmy, że podczas transmisji szum zmienia bit na pozycji 5 z '0' na '1'. Odbiornik otrzymuje uszkodzone słowo 0110111.

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). Wykryto 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). Kontrola poprawna. 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). Wykryto błąd. Bit syndromu S₄ = 1.

Łączymy bity syndromu tak, aby $S_4$ był bitem najbardziej znaczącym, a $S_1$ najmniej znaczącym, otrzymując liczbę binarną 101. Dziesiętnie, $101_2 = 4 + 0 + 1 = 5$ . To jest pozycja błędu w słowie kodowym.

Syndrom wskazuje więc pozycję 5 jako pozycję uszkodzonego bitu.

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