Mi a Hamming-távolság?

Hamming-távolság

A Hamming-távolság két bináris adatsor összehasonlítására szolgáló metrika. Két azonos hosszúságú bináris karakterlánc összehasonlítása során a Hamming-távolság azon bitpozíciók száma, amelyekben a két bit eltér egymástól.

A Hamming-távolságot két karakterlánc, a és b között d(a,b)-ként jelöljük.

A számítógépes hálózatokon történő adatátvitel során hibadetektálásra vagy hibajavításra használják. A kódoláselméletben is használják egyenlő hosszúságú adatszavak összehasonlítására.

A Hamming-távolság kiszámítása

A Hamming-távolság kiszámításához két karakterlánc, és , között XOR műveletet végzünk, (a⊕ b), majd megszámoljuk a kapott karakterláncban lévő 1-ek számát.

Példa

Tegyük fel, hogy van két string 1101 1001 és 1001 1101.

11011001 ⊕ 10011101 = 01000100. Mivel ez két 1-est tartalmaz, a Hamming-távolság, d(11011001, 10011101) = 2.

Minimális Hamming-távolság

Egyenlő hosszúságú karakterláncok halmazában a minimális Hamming-távolság a legkisebb Hamming-távolság a halmazban lévő összes lehetséges karakterlánc-pár között.

Példa

Tegyük fel, hogy van négy karakterlánc: 010, 011, 101 és 111.