Kod Hamminga to liniowykod korekcyjny wynaleziony przezRicharda Hamminga.
Kod Hamminga wykrywa i koryguje błędy polegające na przekłamaniu jednego bitu(ang.)single error correction. Dlaniezawodnejtransmisji wymagane jest, abyodległ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 zkontrolą 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ż jednymbicie.
W sensie matematycznym kody Hamminga są klasą liniowychkodów binarnych. Dla każdejliczby 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).
Richard Hamming pracował dlaBell Labs na komputerzeBell Model V. Dane wejściowe do tego urządzenia były umieszczane nakartach 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.
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.
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 nazywanejodległ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.
Przyjmijmy, że bity parzystości znajdują się na pozycjach będących potęgami 2. Algorytm jest następujący:
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ów | p1 | × | × | × | × | × | × | × | × | × | × | |||||||||||
| 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.
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).
.svg)
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: