Signaalinkäsittelytekniikan laboratorio
Digitaalitekniikan perusteet

Hamming -koodaus

Hamming -koodauksessa käytetään montaa pariteettibittiä yhtäaikaa, jolloin virheellinen bitti voidaan myös paikallistaa ja korjata. (Eli kyseessä on virheenkorjaava koodaus.) Koodauksesta havaitaan kaikki yhden bitin virheet, muut virheet eivät tule ilmi.

  • n:lle databitille tarvitaan k pariteettibittiä siten, että n + k + 1 = < 2k
  • bittipaikat numeroidaan 1 ... n + k
  • pariteettibitit sijoitetaan kakkosen potenssin mukaisille bittipaikoille: 1, 2, 4, 8, jne
  • Esim: b1, b2,b3, b4, b5, b6, b7, b8, ..
  • Kukin pariteettibitti muodostetaan osalle databiteistä käyttäen parillista pariteettia.
    • b1 muodostetaan databiteille, joiden paikkanumeron binääriesityksen vähiten merkitsevä bitti on 1 (b3,b5, b7, b9..)
    • b2 muodostetaan biteille, joiden paikkanumeron binääriesityksen toiseksi vähiten merkitsevä bitti on 1 (b3,b6,b7,b10..)
  • Koodia tulkittaessa muodostetaan pariteettibittejä vastaavat tarkastusbitit C1, C2, C4.. kustakin pariteettibitistä ja sen muodostamiseen käytetyistä databiteistä.
  • Tarkistusbitti muodostetaan kuin se olisi pariteettibitti.
  • Jos kaikki tarkistusbitit ovat nollia, koodi on virheetön. Jos eivät, voidaan tarkistusbittien arvoista päätellä virheen paikka.
Monimutkaista siis. Kannatti lukea yleissivistyksen vuoksi.. Jos aihe kiinnostaa enemmän, löytyy esimerkiksi Internetistä paljonkin asiaa Hamming koodauksesta. Todella innokkaille mainittakoon, että käytännön harjoituksena Hamming-kooderin ohjelmointi esimerkiksi C-kieltä käyttäen ei ole mikään mahdoton urakka.

Esimerkki 1 Lähetetään saman bittijonon alku kuin pariteettiesimerkissämme eli sanan 'Digis' ensimmäinen kirjain 'D' ASCII-muodossa. Lähetetään se kahteen eri vastaanottopaikkaan, joista toiseen on hyvä ja toiseen huono yhteys.
Saadaan: 100 0100

Nyt meillä on 7 databitin ryhmä. Tarvitaan siis k pariteettibittiä siten, että n + k + 1 = < 2k
Mikäli k = 3. Tällöin n + k + 1 = 7 + 3 + 1 = 11 ja 2k = 23 = 8. Todetaan, että 11 < 8 mikä ei pidä paikkaansa!
Mikäli k = 4. Tällöin n + k + 1 = 7 + 4 + 1 = 12 ja 2k = 24 = 16. Todetaan, että 12 < 16 mikä on totta.

Numeroidaan bittipaikat 1 --> 11, jolloin saadaan : b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11.

Sijoitetaan pariteettibitit kakkosen potenssin mukaisille paikoille eli 1,2,4, ja 8
Tällöin saadaan seuraava bittijono: b1,b21,b4,000,b8100 (Tummennetut bitit ovat alkuperäiset ASCII-koodista saadut bitit järjestyksessä)

Parillista pariteettia käyttäen
b1 muodostetaan databiteille (b3,b5,b7,b9,b11). Kyseiset bitit ovat 10010.
Parillista pariteettia käyttäen saadaan b1=0

Vastaavasti
b2 muodostetaan databiteille (b3,b6,b7,b10,b11). Kyseiset bitit ovat 10000.
Parillista pariteettia käyttäen saadaan b1=1

Edelleen
b4 muodostetaan databiteille (b5,b6,b7). Kyseiset bitit ovat 000.
Parillista pariteettia käyttäen saadaan b1=0

Lopuksi
b8 muodostetaan databiteille (b9,b10,b11). Kyseiset bitit ovat 100.
Parillista pariteettia käyttäen saadaan b1=1

Lopullinen Hamming-koodattu bittijono on siis: 01100001100

Vastaanotto 1: Vastaanotetaan bittijono 01100001100
Tarkastetaan pariteettibitit:

b1 muodostetaan databiteille (b3,b5,b7,b9,b11). Kyseiset bitit ovat 10010.
Parillista pariteettia käyttäen saadaan b1=0

b2 muodostetaan databiteille (b3,b6,b7,b10,b11). Kyseiset bitit ovat 10000.
Parillista pariteettia käyttäen saadaan b1=1

jne. jne. Lopuksi saadaan seuraavat pariteettibitit:

  • b1 = 0
  • b2 = 1
  • b4 = 0
  • b8 = 1
Nämä vastaavat täysin niitä pariteettibittejä jotka oli muodostettukin lähetyspäässä. Siis vastaanotto on onnistunut.

Vastaanotto 2: Vastaanotetaan bittijono 01100101100
Tarkastetaan pariteettibitit:

b1 muodostetaan databiteille (b3,b5,b7,b9,b11). Kyseiset bitit ovat 10010.
Parillista pariteettia käyttäen saadaan b1=0

b2 muodostetaan databiteille (b3,b6,b7,b10,b11). Kyseiset bitit ovat 11000.
Parillista pariteettia käyttäen saadaan b1=0

b4 muodostetaan databiteille (b5,b6,b7). Kyseiset bitit ovat 010.
Parillista pariteettia käyttäen saadaan b1=1

b8 muodostetaan databiteille (b9,b10,b11). Kyseiset bitit ovat 100.
Parillista pariteettia käyttäen saadaan b1=1

Lopuksi saadaan seuraavat pariteettibitit:

  • b1 = 0
  • b2 = 0
  • b4 = 1
  • b8 = 1
Huomataan, että b2 ja b4 ovat väärin!. Seuraavaksi tarkastellaan mikä bitti on kääntynyt:

  • b2 huomioi databitit (b3,b6,b7,b10,b11). Joku näistä on mennyt väärin.
  • b4 huomioi databitit (b5,b6,b7). Joku näistä on mennyt väärin. Kun huomioidaan myös b2:n bitit voidaan sanoa, että jompikumpi biteistä (b6,b7) on väärin.
  • b1 huomioi databitit (b3,b5,b7,b9,b11). Tämä pariteettibitti oli oikein, joten myös bitti b7 on oikein.
  • Voidaan lopuksi päätellä siis, että bitti b6 on kääntynyt ympäri ja tämä voidaan nyt korjata kun tiedetään missä kohtaa virhe sijaitsee!!
Tämän sivun sisällöstä vastaa aura@wooster.hut.fi
URL: http://signal.hut.fi/digis/luento3/hamming.html
Sivua on viimeksi päivitetty 18.10.2004.