Kod Hamminga
Kod Hamminga to liniowy kod korekcyjny wynaleziony przez Richarda Hamminga.
Właściwości
[edytuj | 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 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 | 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 | 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 | 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 | edytuj kod]Przyjmijmy, że bity parzystości znajdują się na pozycjach będących potęgami 2. Algorytm jest następujący:
- wszystkie pozycje będące potęgami 2 (1, 2, 4, 8, 16,...) są bitami parzystości,
- wszystkie pozycje niebędące potęgami 2 (3, 5, 6, 7, 9, 10,...) to bity informacyjne,
- 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).
Pozycja bitu 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ... Bit parzystości (p), danych (d) p1 p2 d1 p4 d2 d3 d4 p8 d5 d6 d7 d8 d9 d10 d11 p16 d12 d13 d14 d15 Sekwencja
sprawdzanych
bitówp1 × × × × × × × × × × p2 × × × × × × × × × × p4 × × × × × × × × × p8 × × × × × × × × p16 × × × × ×
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 | 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 | edytuj kod]![](http://178.128.105.246/content-http-upload.wikimedia.org/wikipedia/commons/thumb/b/b0/Hamming%287%2C4%29.svg/300px-Hamming%287%2C4%29.svg.png)
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:
Linki zewnętrzne
[edytuj | edytuj kod]- Grant Sanderson, Hamming codes and error correction, kanał 3blue1brown na YouTube, 4 września 2020 [dostęp 2021-03-15].