Hamming-koodi on virheitä korjaava lohkokoodi. Koodi on nimetty sen 1950-luvulla kehittäneen Richard Hammingin mukaan. Hamming työskenteli tuolloin koneiden kanssa, joissa oli releet ja joissa käytettiin reikäkortteja tietojen lukemiseen. Koska niitä käytettiin paljon, reikäkorteissa oli usein virheitä, jotka työntekijöiden oli korjattava.

Periaate

Hamming-koodeja käytetään erityisesti digitaalisessa signaalinkäsittelyssä ja televiestinnässä. Hamming-koodit luodaan tiettyjen sääntöjen mukaisesti: lisätään koodisanaan useita pariteettibittejä, jotka kertovat tiettyjen bittiryhmien pariteetin (parillinen tai pariton). Jokainen käyttäjädataa (databitti) peitetään useilla pariteettibiteillä niin, että yksittäinen bittivirhe voidaan paikantaa ja korjata. Tämän vuoksi Hamming-koodi käyttää redundanssia — eli ylimääräisiä bittejä alkuperäisen datan lisäksi.

Yleinen Hamming-koodin rakenne on sellainen, että jos pariteettibittejä on kpl, koodisanan pituus on

2 k - 1 {\displaystyle 2^{k}-1}{\displaystyle 2^{k}-1}.

Tällöin käyttäjädatan bittien määrä on 2k−1 − k, ja koodia merkitään muodossa (N,n), jossa N = 2k−1 on koodisanan kokonaispituus ja n = N − k on käyttäjädatan bittien määrä. Esimerkiksi k = 3 antaa N = 7 ja n = 4, eli (7,4)-Hamming-koodin.

Esimerkki: (7,4)-Hamming-koodi

Yleisessä (7,4)-rakenteessa seitsemän bittipaikkaa merkitään b1...b7. Pariteettibitit asetetaan paikoille, jotka ovat 2^0, 2^1, 2^2 eli b1, b2 ja b4. Databitit sijoitetaan paikoille b3, b5, b6 ja b7. Pariteettibitit on laskettu siten, että seuraavat yhtälöt toteutuvat (käytetään parillista pariteettia):

  • p1 (b1) kattaa b1, b3, b5 ja b7 — eli b1 ⊕ b3 ⊕ b5 ⊕ b7 = 0
  • p2 (b2) kattaa b2, b3, b6 ja b7 — eli b2 ⊕ b3 ⊕ b6 ⊕ b7 = 0
  • p4 (b4) kattaa b4, b5, b6 ja b7 — eli b4 ⊕ b5 ⊕ b6 ⊕ b7 = 0

Esimerkki koodauksesta: halutaan lähettää databitit d1 d2 d3 d4 = 1 0 1 1. Sijoitetaan ne paikkoihin b3=1, b5=0, b6=1, b7=1. Lasketaan pariteetit:

  • p1 = b3 ⊕ b5 ⊕ b7 = 1 ⊕ 0 ⊕ 1 = 0 → b1 = 0
  • p2 = b3 ⊕ b6 ⊕ b7 = 1 ⊕ 1 ⊕ 1 = 1 → b2 = 1
  • p4 = b5 ⊕ b6 ⊕ b7 = 0 ⊕ 1 ⊕ 1 = 0 → b4 = 0

Tällöin lähetettävä koodisana b1...b7 on 0 1 1 0 0 1 1 (eli 0110011).

Virheen havaitseminen ja korjaus tapahtuu pariteettitarkastuksilla: vastaanottaja laskee samat pariteetit ja muodostaa syndrooman s = (s1, s2, s3), missä

  • s1 = b1 ⊕ b3 ⊕ b5 ⊕ b7
  • s2 = b2 ⊕ b3 ⊕ b6 ⊕ b7
  • s3 = b4 ⊕ b5 ⊕ b6 ⊕ b7

Syndrooma tulkitaan binäärilukuna s1 + 2·s2 + 4·s3, joka antaa suoraan virheellisen bitin indeksin (0 tarkoittaa: ei virhettä). Esimerkiksi, jos bittipaikka 6 muuttuu virheen takia (b6:sta 1 → 0), syndrooma laskee arvoksi 6, jolloin vastaanottaja kääntää bitin 6 takaisin ja korjaa sanan.

Ominaisuudet ja rajoitukset

  • Vähimmäisetäisyys: Hamming-koodin vähimmäisetäisyys on 3, joten se kykenee korjaamaan yhden yksittäisen bittivirheen ja havaitsemaan (mutta ei korjaamaan) kaksi bittiä koskevan virheen.
  • Täydellisyys: Hamming-koodit, joissa N = 2^k − 1 ja n = 2^k − 1 − k, ovat niin sanottuja täydellisiä koodeja: kaikki mahdolliset syndrome-vektorit (0...2^k−1) on käytetty hyödyllisesti siten, että jokainen yhden bitin virhe vastaa jotakin erillistä syndroomaa.
  • Tehokkuus: Hamming-koodin tehokkuus (käyttäjäbitit / kokonaisbitit) kasvaa k:n kasvaessa, mutta samalla pariteettibittien määrä kasvaa loogisesti.
  • Rajoitukset: Hamming-koodi ei korjaa kahta samanaikaista bittivirhettä. On olemassa laajennuksia (esim. lisäpariteettibitti muodostamaan niin kutsutun laajennetun Hamming-koodin), jotka kykenevät myös havaitsemaan kaksibitvirheet luotettammin.

Lyhin Hamming-koodi (3,1)

Lyhin mahdollinen Hamming-koodi on (3,1): yksi databitti ja kaksi pariteettibittiä. Kelvolliset koodisanat ovat tällöin 000 ja 111 (parillinen pariteetti kaikissa kolmessa bitissä). Jos lähetetään esimerkiksi 000 ja vastaanotetaan jokin yksittäinen bittivirhe, mahdolliset tulokset ovat 001, 010 tai 100, jotka kaikki korjataan takaisin 000. Vastaavasti 011, 101 ja 110 korjataan takaisin 111. Tämä kuvastaa perusajatusta: etäisyys kelvollisten sanojen välillä on 3, joten yksittäinen virhe voidaan aina palauttaa lähimpään kelvolliseen sanaan.

Yhteenvetona: Hamming-koodit ovat yksinkertaisia, tehokkaita lohkokoodimenetelmiä yksittäisten bittivirheiden korjaamiseen. Niitä käytetään laajalti tilanteissa, joissa virheiden todennäköisyys ei ole liian suuri ja joissa tarvitaan matalaa monimutkaisuutta sekä nopeaa korjausta.