Hammingafstand

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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

Het is een maat voor de afstand tussen "woorden" van gelijke lengte. De Hammingafstand 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.

We kunnen eenvoudig vaststellen dat de Hammingafstand gelijk is aan het aantal letters in het ene woord dat je moet veranderen 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 Amerikaans 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]

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