Hammingafstand

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

De hammingafstand is een begrip uit de informatietheorie, vooral toegepast in de coderingstheorie.

De hammingafstand is een maat voor de afstand tussen "woorden" van gelijke lengte die is gedefinieerd als het aantal posities waarin twee binaire of letterwoorden verschillen. Neem de woorden '1001' en '0011'. De woorden verschillen in twee posities, namelijk 1 en 3, zodat de hammingafstand tussen '1001' en '0011' gelijk aan 2 is. De hammingafstand is niet beperkt tot binaire woorden, maar is ook geldig voor woorden in een algemener alfabet. Als we kijken naar codewoorden ter lengte 6, waarbij de (code)symbolen afkomstig zijn uit de verzameling {0, 1, 2, 3, 4, 5, 6}, dan geldt bijvoorbeeld dat de woorden '310201' en '615204' verschillen op de eerste, derde en zesde positie, zodat de hammingafstand gelijk is aan 3.

Eenvoudig is vast te stellen dat de hammingafstand gelijk is aan het aantal letters in het ene woord dat verandert moet worrden om het andere woord te verkrijgen. Of anders gezegd, de hammingafstand is gelijk aan het aantal 'fouten' dat men in het ene woord moet maken om het andere woord te verkrijgen.

De afstandsmaat is genoemd naar Richard Hamming, een Amerikaanse wiskundige, die de eerste foutencorrigerende code heeft bedacht, de hammingcode. Een code is een verzameling van codewoorden. De minimum hammingafstand van een code is de kleinste afstand tussen twee (verschillende) woorden in de code. De minimum hammingafstand is van belang voor de foutencorrigerende capaciteit van de code.

Zie ook[bewerken | brontekst bewerken]

  • Levenshteinafstand (of “bewerkingsafstand”), een generalisatie van de hammingafstand
  • Lee-afstand, een andere afstandsmaat uit de codetheorie voor niet-binaire woorden