Hammingkoodeja

Hammingkoodeja ovat virheenkorjauskoodit, joita käytetään tietojen virheettömän tallentamisen ja siirtämisen tukena. Ne ovat lineaarisia blokikoodeja, joiden tarkoituksena on havaita ja korjata yksittäisiä bittivirheitä sekä mahdollisesti havaita useampia virheitä riippuen versiosta. Koodit on kehitetty Richard W. Hammingin toimesta vuonna 1950.

Perusidea perustuu siihen, että koodi muodostuu n:sta bitistä, joista osa on pariteettibittejä. Valittu m määrää pariteettibittien lukumäärän, ja n = 2^m - 1 sekä k = n - m. Pariteettibitti sijoitetaan paikkoihin, joiden indeksit ovat 2^i (1, 2, 4, 8, …). Data bittit täyttävät loput paikat. Koodin tarkistusmatriisi H luodaan siten, että jokaisen sarakkeen binääriesitys vastaa koodikohtaa 1..n.

Lähetyksessä koodi muodostetaan lisäämällä pariteettibitit niin, että Hx^T = 0. Dekoodauksessa lasketaan syndrooma s = Hy^T vastaanotetulle bitti-koordinaatistolle y. Jos s ≠ 0, syndrooma osoittaa virheen sijainnin ja kyseinen bitti voidaan vaihtaa oikeaksi. Tämä mahdollistaa yksittäisen virheen korjaamisen. Laajennetut versiot, kuten SECDED, lisäävät yleisen paritybitin, jonka avulla kahden samanaikaisen virheen havaitseminen on mahdollista. Näin voidaan erottaa korjattavat ja havaitut virheet.

Esimerkki on (7,4) Hamming-koodi, jossa koodin pituus on 7 bittiä ja dataa 4 bittiä; pariteettibittejä on 3, ja minimietäisyys on 3, joten voidaan korjata yksi virhe ja havaita kaksi samanaikaista virhetilannetta laajennetussa muodossa.

Sovelluksissa Hammingkoodit ovat yleisiä virheenkorjauksessa muistipiireissä ja tiedonsiirrossa, joissa pienikokoiset ja tehokkaat korjaustoiminnot ovat tärkeitä. Niiden sovellukset ovat usein rajallisia, mutta ne tarjoavat yksinkertaisen ratkaisun luotettavuuden parantamiseen.