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:
b 1 muodostetaan databiteille (b 3,b 5,b 7,b 9,b 11). Kyseiset bitit ovat 10010.
Parillista pariteettia käyttäen saadaan b 1=0
b 2 muodostetaan databiteille (b 3,b 6,b 7,b 10,b 11). Kyseiset bitit ovat 11000.
Parillista pariteettia käyttäen saadaan b 1=0
b 4 muodostetaan databiteille (b 5,b 6,b 7). Kyseiset bitit ovat 010.
Parillista pariteettia käyttäen saadaan b 1=1
b 8 muodostetaan databiteille (b 9,b 10,b 11). Kyseiset bitit ovat 100.
Parillista pariteettia käyttäen saadaan b 1=1
Lopuksi saadaan seuraavat pariteettibitit:
- b1 = 0
- b2 = 0
- b4 = 1
- b8 = 1
Huomataan, että b 2 ja b 4 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!!
|