Kod Hamminga

W telekomunikacji kod Hamminga jest liniowym kodem korekcyjnym, wynalezionym przez Richarda Hamminga. Kody Hamminga wykrywają i korygują błędy polegające na przekłamaniu jednego bitu. Czyli dla niezawodnej transmisji wymagane jest aby odległość Hamminga między słowami transmitowanymi i odbieranymi wynosiła zero lub jeden. Kody te mogą też wykryć (ale już nie korygować) błędy podwójne (dwa jednocześnie przekłamane bity).

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]$ . 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).

Spis treści

[edytuj] 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 znajdywał 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łedów. W roku 1950 opublikował efekt swojej pracy, znany dzisiaj jako kod Hamminga.

[edytuj] Kody poprzedzające 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.

[edytuj] 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.

[edytuj] Główny algorytm

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 nie bę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. Pozycja na której się znajduje 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 7 bity, sprawdza 4 bity, opuszcza 4 bity sprawdza 4 bity, opuszcza 4 bity, itd. (8, 9, 10, 11, 16, 17, 18, 19,...),
pozycja 8: opuszcza 127 bitów, sprawdza 8 bitów, opuszcza 8 bitów sprawdza 8 bitów, opuszcza 8 bitów, itd.,

...

pozycja n: opuszcza 2^(n-1)-1 bitów, sprawdza n bitów, opuszcza n bitów, sprawdza n bitów, opuszcza 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).

Bit parzystości (p), danych (d)		p1	p2	d1	p3	d2	d3	d4	p4	d5	d6	d7	d8	d9	d10	d11	p5	d12	d13	d14	d15
Pozycja bitu		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	...
Sekwencja sprawdzanych bitów	p1	X		X		X		X		X		X		X		X		X		X
	p2		X	X			X	X			X	X			X	X			X	X
	p3				X	X	X	X					X	X	X	X					X
	p4								X	X	X	X	X	X	X	X
	p5																X	X	X	X	X

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ę p3 i p4. Ta unikalność pozwala korygować błędy pojedyncze. Tłumaczy to też dlaczego błędy podwójne mogą być wykrywane ale nie korygowane.

[edytuj] 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. Dodanie dodatkowego bitu parzystości jest możliwe zwiększenie minimalnej odległości Hamminga do 4. To pozwala kodowi wykrywać i korygować błędy pojedyncze i w tym samym czasie wykrywać błędy podwójne. Może być też używane do detekcji błędów potrójnych (bez korekcji).

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

[edytuj] 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:

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