Kod Hamminga to liniowy kod korekcyjny wynaleziony przez Richarda Hamminga.

Właściwości

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 ${\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

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 Hamminga

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.

Kod Hamminga z dodatkowym bitem parzystości (SECDED)

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)

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:

${\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}}}

${\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}}.}

Linki zewnętrzne

• Grant Sanderson, Hamming codes and error correction, kanał 3blue1brown na YouTube, 4 września 2020 [dostęp 2021-03-15].