Mikä on Hammingin etäisyys?

Hammingin etäisyys

Hammingin etäisyys on metriikka, jolla verrataan kahta binääristä merkkijonoa. Verrattaessa kahta yhtä pitkää binäärijonoa Hamming-etäisyys on niiden bittipaikkojen lukumäärä, joissa kaksi bittiä eroaa toisistaan.

Kahden merkkijonon, a ja b, välistä Hamming-etäisyyttä merkitään d(a,b).

Mittaria käytetään virheiden havaitsemiseen tai korjaamiseen, kun dataa siirretään tietoverkoissa. Sitä käytetään myös koodausteoriassa samanpituisten datasanojen vertailuun.

Hammingin etäisyyden laskeminen

Kahden merkkijonon, ja , välisen Hammingin etäisyyden laskemiseksi suoritetaan niiden XOR-operaatio, (a⊕ b), ja sen jälkeen lasketaan tuloksena syntyvässä merkkijonossa olevien ykkösten kokonaismäärä.

Esimerkki

Esitellään, että on kaksi merkkijonoa 1101 1001 ja 1001 1101.

11011001 ⊕ 10011101 = 01000100. Koska tässä on kaksi ykköstä, Hammingin etäisyys d(11011001, 10011101) = 2.

Minimi Hammingin etäisyys

Yhtä pitkien merkkijonojen joukossa minimi Hammingin etäisyys on pienin Hammingin etäisyys kaikkien mahdollisten merkkijonoparien välillä kyseisessä joukossa.

Esimerkki

Esitettäkö, että on neljä merkkijonoa: 010, 011, 101 ja 111.