Hammingov kod

Hammingov kod u telekomunikacijama predstavlja linearni kod za pronalazak i ispravljanje jednobitnih pogrešaka i pronalazak (no ne i ispravljanje) dvobitnih pogrešaka u digitalnim podatcima. Za usporedbu: paritetni bit može pronaći neparni broj bitovnih pogrešaka, ali ne može i ispraviti te pogreške.

Richard W. Hamming izumio je taj kodni sustav 1950. godine da bi automatski ispravljao pogreške u čitačima bušenih kartica. U izvornom je radu dodatno objasnio općenitu ideju, ali se usredotočio na kod Hamming(7,4), koji dodaje tri paritetna bita na četiri podatkovna bita.^[1]

Teorija

Paritetni bit

Podrobniji članak o temi: Paritetni bit

Paritetni je bit onaj bit koji se obično dodaje na početak poruke i koji služi kao osnovna provjera pogreške (poruka uvijek mora imati paran broj jedinica). Ako poruka bez vrijednosti paritetnog bita nema parni broj jedinica, paritetni bit postavlja se na vrijednost 1 kako bi uvjet bio ispunjen – u protivnom vrijednost iznosi 0. Ako se tijekom prijenosa dogodi pogreška i jedan se bit preokrene, paritetni bit neće biti ispravno postavljen i to će primatelja obavijestiti o pogreški. Taj postupak pronalazi pogreške samo u neparnom broju preokrenutih bitova; ako se dva bita okrenu, paritetni će bit biti ispravan iako je došlo do pogreške.

X	0	1
1	0	0
1	1	1

Primjer 8-bitnog podatka. Paritetni bit na mjestu X treba imati vrijednost 1 kako bi poruka sadržavala parni broj jedinica.

Hammingov kod

Hamming je demonstrirao kako uključiti paritetne bitove u samu poruku tako da je moguće pronaći mjesto pogreške: svaka pozicija koja je višekratnik broja 2 (u binarnom zapisu ima samo jednu jedinicu) sadrži paritetni bit (označen crveno), a taj paritetni bit regulira paritet svih mjesta koja na istom položaju binarnog zapisa imaju broj 1.

-	A	B	C	D
E	0 0 (0000)	0 1 (0001)	0 2 (0010)	0 3 (0011)
F	0 4 (0100)	0 5 (0101)	0 6 (0110)	0 7 (0111)
G	0 8 (1000)	0 9 (1001)	0 10 (1010)	0 11 (1011)
H	0 12 (1100)	0 13 (1101)	0 14 (1110)	0 15 (1111)

• Hammingov paritetni bit na poziciji 1 (0001) regulira ukupni paritet stupaca B i D (četvrti bit tih polja je 1)
• bit na poziciji 2 (0010) regulira ukupni paritet stupaca C i D (treći bit tih polja je 1)
• bit na poziciji 4 (0100) regulira ukupni paritet redaka F i H (drugi bit tih polja je 1)
• bit na poziciji 8 (1000) regulira ukupni paritet redaka G i H (prvi bit tih polja je 1)
• bit na poziciji 0 (0000) regulira paritet cijele poruke nakon izračuna svih Hammingovih bitova

Primjer u kojoj je bit na poziciji 11 (1011) pogrešno postavljen (treba biti 0):

-	A	B	C	D
E	1 0 (0000)	0 1 (0001)	0 2 (0010)	1 3 (0011)
F	1 4 (0100)	0 5 (0101)	1 6 (0110)	0 7 (0111)
G	1 8 (1000)	0 9 (1001)	1 10 (1010)	1 11 (1011)
H	1 12 (1100)	0 13 (1101)	0 14 (1110)	1 15 (1111)

• Provjera pariteta pozicije 1 je pogrešna (prisutne su tri jedinice, pa bi vrijednost pozicije 1 trebala biti 1 da očuva paritet)
• Provjera pariteta pozicije 2 je pogrešna (prisutno je pet jedinica, pa bi vrijednost pozicije 2 trebala biti 1 da očuva paritet)
• Provjera pariteta pozicije 4 je ispravna (prisutno je nula jedinica, pa bi vrijednost pozicije 4 trebala biti 0 da očuva paritet)
• Provjera pariteta pozicije 8 je pogrešna (prisutne su četiri jedinice, pa bi vrijednost pozicije 8 trebala biti 0 da očuva paritet)

Ako se pogreška označi s 1, a ispravnost s 0, čitajući odozgo prema gore dobije se 1011, što označava poziciju u kojoj se nalazi pogreška (8+2+1=11=1011).

Svaka kombinacija paritetnih bitova pokriva točno jedno podatkovno mjesto. Ako je samo jedan paritetni bit pogrešan, tada je taj paritetni bit pogrešno postavljen. Općenito govoreći, ako su i nulti bit i pojedinačni pariteti pogrešni, poruka sadrži jednu pogrešku i moguće je otkriti gdje se nalazi. Ako je nulti bit ispravan, a pojedinačni pariteti pogrešni, tada poruka sadrži dvije pogreške i nije moguće odrediti gdje se nalaze.

Povezani članci

• Hammingova udaljenost