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]
Podrobniji članak o temi: Paritetni bitParitetni 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.
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.
- ↑ Hamming 1950., str. 153–154.
- 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.