Hamming-koodi: virheenkorjaava lohkokoodi – periaate ja (7,4)-esimerkki

Hamming-koodi: virheenkorjaava lohkokoodi, periaate ja (7,4)-esimerkki — opi pariteettibittien, redundanssin ja yksittäisvirheen korjauksen toiminta digitaalisessa tiedonsiirrossa.

Tekijä: Leandro Alegsa

09-10-2025 23:36

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} $2^{k}-1$ .

Tällöin käyttäjädatan bittien määrä on 2^k−1 − k, ja koodia merkitään muodossa (N,n), jossa N = 2^k−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.

Kysymyksiä ja vastauksia

K: Mikä on Hamming-koodi?

A: Hamming-koodi on Richard Hammingin 1950-luvulla kehittämä virheitä korjaava lohkokoodi. Sitä käytetään digitaalisessa signaalinkäsittelyssä ja televiestinnässä virheiden havaitsemiseen ja korjaamiseen.

K: Miten Hamming-koodi toimii?

V: Hamming-koodi käyttää useita pariteettibittejä kattamaan jokaisen databitin, minkä ansiosta se pystyy havaitsemaan virheet ja tietyissä tapauksissa myös korjaamaan ne. Siinä käytetään myös redundanssia, mikä tarkoittaa, että koodisanan kokonaispituuden on oltava 2^k - 1, jossa k on pariteettibittien lukumäärä.

K: Kuka keksi Hammingin koodin?

V: Hamming-koodin keksi Richard Hamming 1950-luvulla.

K: Mihin Richard Hamming käytti keksintöään?

V: Kehittämisajankohtana Richard Hamming käytti keksintöään korjaamaan virheitä reikäkorteissa, joita käytettiin paljon releillä varustetuissa koneissa. Nykyään sitä käytetään pääasiassa digitaalisessa signaalinkäsittelyssä ja televiestinnässä.

Kysymys: Mitä kirjoitetaan (N,n), kun puhutaan Hamming-koodista?

V: Hamming-koodista puhuttaessa (N,n) tarkoittaa koodisanan kokonaispituutta (ensimmäinen luku) ja käyttäjätiedon bittien määrää (toinen luku). Esimerkiksi (7,4) tarkoittaa, että bittejä on yhteensä 7, joista 4 on käyttäjädatabittejä.

Kysymys: Mikä on lyhin mahdollinen hamming-koodi?

V: Lyhin mahdollinen hamming-koodi on (3,1), mikä tarkoittaa, että kokonaisbittejä on kolme ja yksi on käyttäjätietobitti.

Etsiä