Nederlands
Menu

Wat is Hamming-afstand?

Het aantal posities waarop twee bitreeksen (of tekenreeksen) van dezelfde lengte verschillen. Ze is gelijk aan het aantal enen in de exclusieve OF van de twee bitreeksen. De Hamming-afstand tussen 1011010 en 0110011 is bijvoorbeeld 4. De kleinste afstand tussen twee codewoorden van een code is haar minimale Hamming-afstand; een code met minimale Hamming-afstand d kan fouten tot d − 1 bits detecteren en fouten tot (d − 1) ÷ 2 bits, naar beneden afgerond, corrigeren.

Japanse benaming: ハミング距離

“Hamming-afstand” komt voor in 3 oefenvragen uit 1 onderwerpen, bijv. Basis van informatietheorie en codering.

Vakgebied: Basis van informatietheorie en codering

Vermogen om fouten te detecteren en te corrigeren

Hoe verder de codewoorden uit elkaar liggen, hoe kleiner de kans dat een fout het ene in het andere verandert. In een code met minimale Hamming-afstand d kan een fout van d − 1 bits of minder geen ander codewoord opleveren en dus worden gedetecteerd, en als de fout hoogstens (d − 1) ÷ 2 bits is, is het codewoord dat het dichtst bij het ontvangen woord ligt het oorspronkelijke, zodat ze kan worden gecorrigeerd. De herhalingscode die elke bit drie keer verstuurt, heeft bijvoorbeeld d = 3 en corrigeert een fout van 1 bit met een meerderheidsbeslissing.

Bepalen voor een lineaire code

In een lineaire code, waarin de exclusieve OF van twee codewoorden ook een codewoord is, is de afstand tussen twee codewoorden gelijk aan het aantal enen in het codewoord dat hun exclusieve OF is. De minimale Hamming-afstand kan daarom worden gevonden als het kleinste aantal enen (gewicht) in een codewoord dat niet nul is, zonder elk paar te vergelijken.

Gebruik in andere vakgebieden

De Hamming-afstand wordt gebruikt als algemene maat die de verschillen tussen twee gegevens telt. Bij de beoordeling van PUF's (physically unclonable functions) worden afzonderlijke chips als beter te onderscheiden beschouwd naarmate de Hamming-afstand tussen de responsen van verschillende chips dichter bij 50% van alle bits ligt. Bij het coderen van toestandsmachines vermindert een Hamming-afstand van 1 tussen naburige toestanden het aantal bits dat bij een overgang verandert.

Nu oefenen: vragen over Hamming-afstand

De minimale Hamming-afstand van een code (de kleinste Hamming-afstand tussen twee willekeurige codewoorden) is 5. Beschouw het gebruik ervan alleen voor foutdetectie of alleen voor foutcorrectie. Welke combinatie van het aantal bitfouten dat altijd kan worden gedetecteerd en het aantal bitfouten dat altijd kan worden gecorrigeerd, is juist?

  1. ADetectie tot 4 bit, correctie tot 2 bit
  2. BDetectie tot 5 bit, correctie tot 2 bit
  3. CDetectie tot 4 bit, correctie tot 4 bit
Antwoord en toelichting tonen

Antwoord: A. Detectie tot 4 bit, correctie tot 2 bit

In een code met minimale Hamming-afstand d verandert een fout van hoogstens d − 1 bits een codewoord nooit in een ander codewoord, dus ze kan worden gedetecteerd. Bij correctie wordt de ontvangen bitreeks vervangen door het dichtstbijzijnde codewoord; is het aantal fouten hoogstens (d − 1) ÷ 2, naar beneden afgerond, dan blijft het oorspronkelijke codewoord het dichtstbijzijnde. Voor d = 5 werkt detectie tot 4 bit en correctie tot 2 bit.

Veelgestelde vragen

Zijn Hamming-afstand en Hamming-code hetzelfde?

Nee. De Hamming-afstand is een maat die de verschillen tussen twee bitreeksen telt, terwijl een Hamming-code een code is die zo is opgebouwd dat ze een minimale Hamming-afstand van 3 heeft en een fout van 1 bit kan corrigeren. Beide zijn naar Hamming genoemd.

Kan de Hamming-afstand tussen bitreeksen van verschillende lengte worden bepaald?

De Hamming-afstand is alleen gedefinieerd tussen reeksen van dezelfde lengte. Om verschillen te tellen inclusief ingevoegde en verwijderde tekens, gebruikt men de bewerkingsafstand (Levenshtein-afstand).

“Hamming-afstand” in de toelichting

Vragen met “Hamming-afstand” (3)

  1. Wat is de Hamming-afstand tussen de twee codewoorden van 7 bits 1011010 en 0110011?
  2. De minimale Hamming-afstand van een code (de kleinste Hamming-afstand tussen twee willekeurige codewoorden) is 5. Beschouw het gebruik ervan alleen voor foutdetectie of alleen voor foutcorrectie. Welke combinatie van het aantal bitfouten dat altijd kan worden gedetecteerd en het aantal bitfouten dat altijd kan worden gecorrigeerd, is juist?
  3. Welke combinatie van de minimale Hamming-afstand van de code die bestaat uit de vier codewoorden 00000, 01011, 10101 en 11110, en het aantal bitfouten dat ze altijd kan corrigeren, is juist?

Verwante termen

Binair symmetrisch kanaal Compressie met verlies Forward error correction (FEC) Gemiddelde codelengte Hamming-code Huffman-code Informatie-entropie Informatie-inhoud Ongelijkheid van Kraft Pariteitsbit

Naar de woordenlijst