Hvad er Hamming Distance?

Hamming Distance

Hamming Distance er en måleenhed til sammenligning af to binære datastrømme. Ved sammenligning af to binære strenge af samme længde er Hamming-afstanden det antal bitpositioner, hvor de to bits er forskellige.

Hamming-afstanden mellem to strenge, a og b, betegnes d(a,b).

Det bruges til fejlfinding eller fejlkorrektion, når data overføres over computernetværk. Den bruges også i kodningsteori til at sammenligne dataord af samme længde.

Beregning af Hamming-afstanden

For at beregne Hamming-afstanden mellem to strenge, og , udfører vi deres XOR-operation, (a⊕ b), og tæller derefter det samlede antal 1’er i den resulterende streng.

Eksempel

Sæt, at der er to strenge 1101 1001 og 1001 1101.

11011001 ⊕ 10011101 = 01000100. Da dette indeholder to 1’ere, er Hamming-afstanden d(11011001, 10011101) = 2.

Minimal Hamming-afstand

I et sæt af strenge af samme længde er den minimale Hamming-afstand den mindste Hamming-afstand mellem alle mulige par af strenge i det pågældende sæt.

Eksempel

Sæt, at der er fire strenge 010, 011, 101 og 111.