Hammingetäisyyteen

Hammingetäisyys on kahden samanpituisen merkkijonon eroavaisuuksien lukumäärä. Se lasketaan vertaamalla jokaisen sijainnin merkkiä ja laskemalla, kuinka monta kohtaa poikkeaa. Merkkijonojen tulee olla yhtä pituisia, ja käytettävän merkkialfabetin on oltava kiinteä.

Merkkijonojen eroja mitataan usein binäärisessä tai yleisessä q-ulosmerkistöä käyttävässä kontekstissa. Merkkijonot voivat olla esimerkiksi bittijonoja tai sanasarjoja, joiden pituus on sama. Esimerkki: d(0101, 1100) = 3, koska kolmannessa, neljännessä ja toisessa paikassa merkit eroavat.

Binary-tapauksessa Hammingetäisyyden voi nähdä XOR-toiminnon tuloksen 1-lukumääränä. Toisin sanoen d(x,y) = wt(x XOR y), jossa wt kertoo tuloksen Hamming- tai bitin weightin eli yhdensien määrän. Tämä tekee Hammingetäisyydestä kätevän mittarin digitaalisten tietojen virhetilanteissa.

Kooditeoriassa minimi etäisyys d_min on tärkeä käsite. Se määrittää, kuinka monta virhettä koodin koodijonoihin voidaan havaita tai korjata. Yleisesti, jos d_min on suurempi, koodi on virheenkestävämpi: sitä voidaan havaita useampi virhe ja osaksi jopa korjata; täsmällinen korjauskyky on floor((d_min - 1)/2).

Hammingetäisyyden nimen taustalla on Richard Hamming, joka esitteli sitä Hamming-koodeissa 1950-luvulla. Käytännössä etäisyyden käsite yhdistää mittauksen virheiden lukumäärään ja mahdollisen virheenkorjauksen kapasiteetin erityyppisissä koodauksissa sekä tiedonsiirrossa että tallennuksessa.

Rajoitukset: Hammingetäisyys soveltuu ainoastaan samanpituisille merkkijonoille eikä huomioi lisäyksiä tai poistamisia. Sitä vastaa muunlaisia etäisyyksiä, kuten Levenshtein-etäisyys, kun käsitellään muunnoksia, joissa merkkijonojen pituudet voivat muuttua.