Vad är Hammingavståndet?

Hamming Distance

Hamming Distance är ett mått för att jämföra två binära datasträngar. När man jämför två binära strängar av samma längd är Hammingavståndet antalet bitpositioner där de två bitarna är olika.

Hammingavståndet mellan två strängar, a och b, betecknas som d(a,b).

Det används för feldetektering eller felkorrigering när data överförs via datornätverk. Det används också i kodningsteori för att jämföra dataord av samma längd.

Beräkning av Hammingavståndet

För att beräkna Hammingavståndet mellan två strängar, och , utför vi deras XOR-operation, (a⊕ b), och räknar sedan det totala antalet 1:or i den resulterande strängen.

Exempel

Antag att det finns två strängar 1101 1001 och 1001 1101.

11011001 ⊕ 10011101 = 01000100. Eftersom detta innehåller två 1:or är Hammingavståndet d(11011001, 10011101) = 2.

Minimalt Hammingavstånd

I en uppsättning strängar av samma längd är det minsta Hammingavståndet det minsta Hammingavståndet mellan alla möjliga par av strängar i den uppsättningen.

Exempel

Förutsatt att det finns fyra strängar 010, 011, 101 och 111.