Hammingov kod

kod za pronalazak i ispravljanje jednobitnih pogrešaka i pronalazak (no ne ispravljanje) dvobitnih pogrešaka

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 uredi

Paritetni bit uredi

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 uredi

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 uredi

Bilješke uredi

  1. Hamming 1950., str. 153–154.

Izvori uredi

  • Hamming, Richard Wesley. 1950. Error detecting and error correcting codes (PDF). Bell System Technical Journal. 29 (2): 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x
  • Moon, Todd K. 2005. Error Correction Coding. John Wiley & Sons. New Jersey. ISBN 978-0-471-64800-0
  • MacKay, David J.C. Rujan 2003. Information Theory, Inference and Learning Algorithms. Cambridge University Press. Cambridge. ISBN 0-521-64298-1
  • D.K. Bhattacharryya, S. Nandi. "An efficient class of SEC-DED-AUED codes". pp. 410–415. doi:10.1109/ISPAN.1997.645128 
  • Mathematical Challenge April 2013 Error-correcting codes (PDF). swissQuant Group Leadership Team. Travanj 2013. Inačica izvorne stranice (PDF) arhivirana 12. rujna 2017. Pristupljeno 25. prosinca 2021.