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.
Teorija 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 DE 00 (0000) 01 (0001) 02 (0010) 03 (0011)F 04 (0100) 05 (0101) 06 (0110) 07 (0111)G 08 (1000) 09 (1001) 010 (1010) 011 (1011)H 012 (1100) 013 (1101) 014 (1110) 015 (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 DE 10 (0000) 01 (0001) 02 (0010) 13 (0011)F 14 (0100) 05 (0101) 16 (0110) 07 (0111)G 18 (1000) 09 (1001) 110 (1010) 111 (1011)H 112 (1100) 013 (1101) 014 (1110) 115 (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
Bilješke
Izvori
Kategorija:Računalno pohranjivanje podataka Kategorija:Telekomunikacije