Kod Hamminga


Kod Hamminga w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Kod Hamminga to liniowy kod korekcyjny wynaleziony przez Richarda Hamminga.

Spis treści

Właściwości | edytuj kod

Kod Hamminga wykrywa i koryguje błędy polegające na przekłamaniu jednego bitu (ang.) single error correction. Dla niezawodnej transmisji wymagane jest, aby odległość Hamminga między słowami transmitowanym i odbieranym, wynosiła 0 lub 1. Kod ten może wykrywać (ale już nie korygować) błędy podwójne (dwa jednocześnie przekłamane bity), (ang.) double error detection.

Dla porównania: prosty kod z kontrolą parzystości nie może korygować żadnych błędów ani też nie może być używany do detekcji błędu na więcej niż jednym bicie.

W sensie matematycznym kody Hamminga są klasą liniowych kodów binarnych. Dla każdej liczby całkowitej m>1 istnieje kod o parametrach 2 m 1 , 2 m m 1 , 3 . {\displaystyle [2^{m}-1,2^{m}-m-1,3].} Macierz kontroli parzystości dla kodu Hamminga tworzy się wypisując wszystkie kolumny o długości m, które są parami niezależne.

Z uwagi na swoją prostotę kody Hamminga są szeroko używane w pamięciach komputerowych (RAM).

Historia | edytuj kod

Richard Hamming pracował dla Bell Labs na komputerze Bell Model V. Dane wejściowe do tego urządzenia były umieszczane na kartach dziurkowanych, które często posiadały błędy. Specjalny kod znajdował te błędy i zapalał lampki ostrzegawcze, aby operatorzy mogli naprawić problem. Jednak po godzinach pracy, kiedy operatorów nie było maszyna sama nie potrafiła skorygować błędów i po prostu zaczynała nowe zadanie.

Hamming pracował w weekendy i był bardzo sfrustrowany koniecznością ciągłego restartowania programów z powodu zawodności czytnika kart. Przez kolejne kilka lat pracował nad problemem korekcji błędów. W roku 1950 opublikował efekt swojej pracy, znany dzisiaj jako kod Hamminga.

Kody poprzedzające kod Hamminga | edytuj kod

Kilka prostych detekcyjnych kodów było używanych wcześniej, ale żaden nie był tak efektywny jak kod Hamminga. Były to między innymi kod parzystości, kod 2z5, powtarzanie.

Kody Hamminga | edytuj kod

Jeśli w wiadomości jest więcej bitów korygujących i jeśli te bity dla różnej kombinacji bitów przekłamanych dają różne rezultaty, wtedy możemy zidentyfikować nieprawidłowe bity. W 7-bitowej wiadomości jest 7 prawdopodobnych błędów pojedynczych, więc trzy bity korygujące wystarczą by potencjalnie wskazać nie tylko że błąd wystąpił, lecz także na której pozycji.

Hamming zauważył problem przy przekłamaniu dwóch lub więcej bitów i wprowadził pojęcie odległości (teraz nazywanej odległością Hamminga). Kod z kontrolą parzystości ma odległość równą 2 (przekłamanie dwóch bitów jest niewidoczne – kod nie zgłasza błędów, ale słowo jest inne niż przesłane).

Hamming skupił się na dwóch problemach: zwiększeniu odległości między słowami jak to tylko możliwe, i jednocześnie jak największym stosunku liczby bitów informacyjnych do długości słowa. Główną ideą zastosowanych przez niego schematów kodowania jest nakładanie się bitów parzystości, tak, aby mogły sprawdzać siebie nawzajem.

Główny algorytm | edytuj kod

Przyjmijmy, że bity parzystości znajdują się na pozycjach będących potęgami 2. Algorytm jest następujący:

  1. wszystkie pozycje będące potęgami 2 (1, 2, 4, 8, 16,...) są bitami parzystości,
  2. wszystkie pozycje niebędące potęgami 2 (3, 5, 6, 7, 9, 10,...) to bity informacyjne,
  3. każdy bit parzystości wskazuje parzystość pewnej grupy bitów w słowie, a jego pozycja określa, które bity ma sprawdzać, a które opuszczać:
  • pozycja 1: opuszcza 0 bitów, sprawdza 1 bit, opuszcza 1 bit, sprawdza 1 bit, opuszcza 1 bit itd. (1, 3, 5, 7, 9,...),
  • pozycja 2: opuszcza 1 bit, sprawdza 2 bity, opuszcza 2 bity sprawdza 2 bity, opuszcza 2 bity itd. (2, 3, 6, 7, 10, 11,...),
  • pozycja 4: opuszcza 3 bity, sprawdza 4 bity, opuszcza 4 bity sprawdza 4 bity, opuszcza 4 bity itd. (4, 5, 6, 7, 12, 13, 14, 15,...)
  • pozycja 8: opuszcza 7 bitów, sprawdza 8 bitów, opuszcza 8 bitów sprawdza 8 bitów, opuszcza 8 bitów itd.,
...
  • pozycja n: opuszcza n-1 bitów, sprawdza n bitów, opuszcza n bitów, sprawdza n bitów itd.

W tabeli przedstawiono zasadę kodowania dla słowa o długości 20 (15 bitów danych, 5 bitów parzystości).

Kluczowe dla kodów Hamminga jest to, że każdy bit ma unikalną kombinację sprawdzających go bitów parzystości, np. tylko bit 12 jest sprawdzany przez parę p4 i p8. Ta unikalność pozwala korygować błędy pojedyncze. Tłumaczy to też, dlaczego błędy podwójne mogą być wykrywane, ale nie korygowane.

Kod Hamminga z dodatkowym bitem parzystości (SECDED) | edytuj kod

Kody Hamminga mają odległość równą 3, to znaczy że mogą wykrywać i korygować błędy pojedyncze, ale błędy podwójne mogą być pomylone z błędem pojedynczym innego ciągu kodowego. Dzięki dodaniu dodatkowego bitu parzystości jest możliwe zwiększenie minimalnej odległości Hamminga do 4, co pozwala kodowi korygować błędy pojedyncze i w tym samym czasie wykrywać błędy podwójne. Bez korekcji kod może wykrywać błędy potrójne.

Ten system kodowania jest popularny w pamięciach komputerowych, jako SECDED (single error correction, double error detection).

Kod Hamminga (7,4) | edytuj kod

Graficzne przedstawienie 4 bitów informacyjnych i trzech bitów parzystości

W roku 1950 Hamming przedstawił kod (7,4), który kodował 4 pozycje informacyjne jako słowo 7-bitowe, dodając 3 bity parzystości.

Macierz generująca G kodu (7,4) i jego macierz kontroli parzystości H są przedstawione poniżej:

G := ( 1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 ) {\displaystyle \mathbf {G} :={\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}}} H := ( 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 ) . {\displaystyle \mathbf {H} :={\begin{pmatrix}1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1&1\end{pmatrix}}.}
Na podstawie artykułu: "Kod Hamminga" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy