Wat is de Hamming-afstand?

Hamming-afstand

Hamming-afstand is een metriek voor het vergelijken van twee binaire gegevensreeksen. Bij het vergelijken van twee binaire reeksen van gelijke lengte is de Hamming-afstand het aantal bitposities waarin de twee bits verschillen.

De Hamming-afstand tussen twee reeksen, a en b, wordt aangeduid als d(a,b).

Hamming-afstand wordt gebruikt voor foutdetectie of foutcorrectie wanneer gegevens via computernetwerken worden verzonden. Zij wordt ook gebruikt in de coderingstheorie voor het vergelijken van datawoorden van gelijke lengte.

Berekening van de Hamming-afstand

Om de Hamming-afstand tussen twee strings, en , te berekenen voeren we hun XOR-bewerking uit, (a⊕ b), en tellen dan het totale aantal 1-en in de resulterende string.

Voorbeeld

Voorstel dat er twee strings zijn, 1101 1001 en 1001 1101.

11011001 ⊕ 10011101 = 01000100. Aangezien deze twee 1-en bevat, is de Hamming afstand, d(11011001, 10011101) = 2.

Minimale Hamming Afstand

In een verzameling van snaren van gelijke lengte, is de minimale Hamming afstand de kleinste Hamming afstand tussen alle mogelijke paren van snaren in die verzameling.

Voorbeeld

Stel dat er vier snaren zijn 010, 011, 101 en 111.