Kod Hamminga — definicja, zasada działania i przykład (7,4)

Kod Hamminga: definicja, zasada działania i przykład (7,4) — praktyczny przewodnik wyjaśniający generowanie bitów parzystości, wykrywanie i korekcję błędów w transmisji danych.

Kod Hamminga (potocznie zwany też kodem młotkowym) jest kodem blokowym korygującym błędy. Nazwa pochodzi od Richarda Hamminga, który opracował ten typ kodów w latach pięćdziesiątych XX wieku, pracując z ówczesnymi maszynami opartymi na przekaźnikach i wykrojonych kartach, narażonych na uszkodzenia i błędy odczytu. Kody Hamminga są powszechnie stosowane w cyfrowym przetwarzaniu sygnału i w telekomunikacji, wszędzie tam, gdzie konieczne jest wykrywanie i automatyczna korekcja pojedynczych błędów bitowych.

Zasada działania

Kod Hamminga wykorzystuje nadmiarowe bity parzystości – czyli bity dodane do danych, które pozwalają sprawdzić, czy pewne zbiory bitów mają parzystą (lub nieparzystą) sumę jedynek. Liczba bitów parzystości oznaczana jest zwykle przez k i spełnia warunek, że słowo kodowe ma długość 2^k−1, gdyż dla k bitów parzystości można wskazać 2^k−1 możliwych pozycji (z czego jedna to stan "braku błędu"). W zapisie z artykułu występuje ten zapis matematyczny przedstawiony także graficznie: 2 k - 1 {\i1 ^{k}-1} . Dla przykładu przy k = 3 bity parzystości i bity danych mieszczą się w słowie długości 2^3 − 1 = 7, z czego 4 bity to dane użytkownika — stąd oznaczenie (7,4).

W praktyce parzystości umieszcza się na pozycjach, które są potęgami dwójki: 1, 2, 4, 8, ... (licząc pozycje od 1). Pozostałe pozycje zajmują bity danych. Każdy bit parzystości kontroluje parzystość podzbioru bitów, których numery pozycji w zapisie binarnym mają odpowiedni bit ustawiony. Dzięki temu po odebraniu słowa można obliczyć tzw. syndrom — wektor, który wskazuje (w postaci liczby binarnej) pozycję pojedynczego błędu; jeśli syndrom jest zerowy, przyjmujemy brak błędu.

Właściwości

• Odległość Hamminga: Minimalna odległość między dwoma słowami kodowymi w standardowym kodzie Hamminga wynosi 3, co oznacza, że kod może skorygować wszystkie pojedyncze błędy i wykryć (ale nie zawsze poprawić) podwójne błędy.
• Redundancja: Kod (7,4) dodaje 3 bity nadmiarowe do 4 bitów danych; stosunek informacji użytkownika do długości słowa to 4/7.
• Kod doskonały: Standardowe kody Hamminga są tzw. kodami doskonałymi — pokrywają wszystkie możliwe wektory błędów jednego bitu bez nakładania się koszyków korekcyjnych.

Przykład (7,4) — kod Hamminga: kodowanie i dekodowanie

W wersji (7,4) mamy 3 bity parzystości na pozycjach 1, 2 i 4 oraz 4 bity danych na pozycjach 3, 5, 6 i 7. Oznaczmy bity danych jako d1, d2, d3, d4 i umieśćmy je kolejno w pozycjach 3, 5, 6, 7. Bity parzystości p1 (poz. 1), p2 (poz.2) i p4 (poz.4) oblicza się następująco (przy założeniu parzystości parzystej):

• p1 kontroluje pozycje: 1, 3, 5, 7 (wszystkie pozycje, których numer w zapisie binarnym ma LSB = 1), więc p1 = d1 ⊕ d2 ⊕ d4;
• p2 kontroluje pozycje: 2, 3, 6, 7 (drugi bit w zapisie binarnym = 1), więc p2 = d1 ⊕ d3 ⊕ d4;
• p4 kontroluje pozycje: 4, 5, 6, 7 (trzeci bit w zapisie binarnym = 1), więc p4 = d2 ⊕ d3 ⊕ d4.

Przykład kodowania: niech dane użytkownika to 1011 (czyli d1=1, d2=0, d3=1, d4=1).

• Obliczamy p1 = d1 ⊕ d2 ⊕ d4 = 1 ⊕ 0 ⊕ 1 = 0;
• p2 = d1 ⊕ d3 ⊕ d4 = 1 ⊕ 1 ⊕ 1 = 1;
• p4 = d2 ⊕ d3 ⊕ d4 = 0 ⊕ 1 ⊕ 1 = 0.

Zatem słowo kodowe (pozycje 1..7) to: p1 p2 d1 p4 d2 d3 d4 = 0 1 1 0 0 1 1, czyli 0110011.

Przykład dekodowania i korekcji błędu: załóżmy, że podczas transmisji uległ odwróceniu bit na pozycji 6 (z 1 na 0). Odebrane słowo to 0110001. Aby znaleźć pozycję błędu, obliczamy syndrom S = (s4 s2 s1), gdzie:

• s1 = parzystość nad pozycjami 1,3,5,7 = 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0;
• s2 = parzystość nad pozycjami 2,3,6,7 = 1 ⊕ 1 ⊕ 0 ⊕ 1 = 1;
• s4 = parzystość nad pozycjami 4,5,6,7 = 0 ⊕ 0 ⊕ 0 ⊕ 1 = 1.

Syndrom w zapisie binarnym daje 110, czyli liczbę 6 — to wskazuje, że błąd wystąpił na pozycji 6. Korygujemy bit na tej pozycji (zamieniamy 0 z powrotem na 1) i otrzymujemy pierwotne słowo kodowe 0110011, po czym odczytujemy bity danych z pozycji 3,5,6,7 = 1 0 1 1, czyli oryginalne 1011.

Ograniczenia i rozszerzenia

Standardowy kod Hamminga (np. (7,4)) jest jednobitowo korygujący i dwubitowo wykrywający

Kody Hamminga mają proste algorytmy implementacji zarówno sprzętowej, jak i programowej (obliczanie XOR‑ów, macierze kontrolne), dlatego są szeroko używane tam, gdzie wymagane jest tanie i szybkie korygowanie pojedynczych błędów.