3-Bit-Binärwürfel
3-Bit-Binärwürfel zur Berechnung der Hamming-Distanz
Beispiele für die Hamming-Distanz des binären Kubus mit 3 Bit
Zwei Beispieldistanzen: 100→011 hat die Distanz 3; 010→111 hat die Distanz 2
Der minimale Abstand zwischen zwei beliebigen Knotenpunkten ist der Hamming-Abstand zwischen den beiden Binärstrings.

In der Informationstheorie bezeichnet die Hamming-Distanz zwischen zwei Zeichenketten oder Vektoren gleicher Länge die Anzahl der Positionen, an denen sich die entsprechenden Symbole unterscheiden. Anders ausgedrückt: Sie misst die minimale Anzahl an Ersetzungen, die nötig sind, um eine Zeichenkette in die andere zu überführen, oder äquivalent dazu die minimale Anzahl an Fehlern , die bei der Transformation einer Zeichenkette in die andere auftreten können. Allgemeiner betrachtet ist die Hamming-Distanz eine von mehreren Metriken zur Messung der Editierdistanz zwischen zwei Sequenzen. Sie ist nach dem amerikanischen Mathematiker Richard Hamming benannt .

Eine wichtige Anwendung findet sich in der Codierungstheorie , insbesondere bei Blockcodes , bei denen die gleichlangen Zeichenketten Vektoren über einem endlichen Körper sind .

Definition

Die Hamming-Distanz zwischen zwei gleichlangen Symbolketten ist die Anzahl der Positionen, an denen sich die entsprechenden Symbole unterscheiden. [ 1 ]

Beispiele

Die Symbole können unter anderem Buchstaben, Bits oder Dezimalziffern sein. Zum Beispiel die Hamming-Distanz zwischen:

  • " ka rol in " und " ka thr in " ist 3.
  • " karol in " und " k e r st in " ist 3.
  • „ k athr in “ und „ k erst in “ ist 4.
  • 0000 und 1111 ist 4.
  • 2 17 3 8 96 und 2 23 3 7 96 ist 3.

Eigenschaften

Für eine feste Länge n ist die Hamming-Distanz eine Metrik auf der Menge der Wörter der Länge n (auch Hamming-Raum genannt ), da sie die Bedingungen der Nichtnegativität und Symmetrie erfüllt. Die Hamming-Distanz zweier Wörter ist genau dann 0, wenn die beiden Wörter identisch sind. Außerdem erfüllt sie die Dreiecksungleichung : [ 2 ] Sind drei Wörter a , b und c fest definiert, so gilt: Wenn sich der i -te Buchstabe von a und der i -te Buchstabe von c unterscheiden , dann muss sich auch der i -te Buchstabe von a und der i -te Buchstabe von b oder der i- te Buchstabe von b und der i -te Buchstabe von c unterscheiden . Daher ist die Hamming-Distanz zwischen a und c nicht größer als die Summe der Hamming-Distanzen zwischen a und b sowie zwischen b und c . Der Hamming-Abstand zwischen zwei Wörtern a und b kann auch als Hamming-Gewicht von a − b bei geeigneter Wahl des −-Operators angesehen werden, ähnlich wie die Differenz zwischen zwei ganzen Zahlen als Abstand von Null auf der Zahlengeraden angesehen werden kann.

Für Binärstrings a und b entspricht die Hamming-Distanz der Anzahl der Einsen ( Populationshäufigkeit ) in a XOR b . [ 3 ] Der metrische Raum der Binärstrings der Länge n mit der Hamming-Distanz wird als Hamming-Würfel bezeichnet ; er ist als metrischer Raum äquivalent zur Menge der Abstände zwischen den Knoten eines Hyperwürfelgraphen . Man kann einen Binärstring der Länge n auch als Vektor betrachten , indem man jedes Symbol im String als reelle Koordinate behandelt; mit dieser Einbettung bilden die Strings die Knoten eines n- dimensionalen Hyperwürfels , und die Hamming-Distanz der Strings ist äquivalent zur Manhattan-Distanz zwischen den Knoten.

Fehlererkennung und Fehlerkorrektur

Der minimale Hamming-Abstand ( üblicherweise mit d<sub> min</sub> bezeichnet ) dient zur Definition einiger grundlegender Begriffe der Codierungstheorie , wie z. B. fehlererkennender und fehlerkorrigierender Codes . Insbesondere heißt ein Code C k -fehlererkennend, wenn der minimale Hamming-Abstand zwischen je zwei seiner Codewörter mindestens k + 1 beträgt. [ 2 ]

Betrachten wir beispielsweise einen Code, der aus den beiden Codewörtern „000“ und „111“ besteht. Der Hamming-Abstand zwischen diesen beiden Wörtern beträgt 3, daher ist die Fehlererkennung k = 2. Das bedeutet, dass ein Fehler erkannt werden kann, wenn ein oder zwei Bits invertiert werden. Werden jedoch drei Bits invertiert, wird aus „000“ „111“, und der Fehler ist nicht mehr erkennbar.

Ein Code C heißt k-fehlerkorrigierend , wenn es für jedes Wort w im zugrundeliegenden Hamming-Raum H höchstens ein Codewort c (aus C ) gibt, dessen Hamming-Abstand höchstens k beträgt . Anders ausgedrückt: Ein Code ist k -fehlerkorrigierend, wenn der minimale Hamming-Abstand zwischen je zwei seiner Codewörter mindestens 2k + 1 beträgt . Geometrisch lässt sich dies auch so verstehen, dass alle abgeschlossenen Kugeln mit Radius k um verschiedene Codewörter disjunkt sind. [ 2 ] Diese Kugeln werden in diesem Kontext auch Hamming-Sphären genannt . [ 4 ]

Betrachten wir beispielsweise denselben 3-Bit-Code, bestehend aus den beiden Codewörtern „000“ und „111“. Der Hamming-Raum umfasst die acht Wörter 000, 001, 010, 011, 100, 101, 110 und 111. Das Codewort „000“ und die Einzelbitfehlerwörter „001","010","100“ haben alle einen Hamming-Abstand von maximal 1 zu „000“. Ebenso liegen das Codewort „111“ und seine Einzelbitfehlerwörter „110","101“ und „011“ alle innerhalb eines Hamming-Abstands von 1 zum ursprünglichen „111“. In diesem Code liegt ein Einzelbitfehler stets innerhalb eines Hamming-Abstands von 1 zum ursprünglichen Code, und der Code ist fehlerkorrigierend ( k = 1) . Da der Hamming-Abstand zwischen "000" und "111" 3 beträgt und diese die gesamte Menge der Codewörter im Code umfassen, ist der minimale Hamming-Abstand 3, was 2k+1 = 3 erfüllt .

Ein Code mit minimalem Hamming-Abstand d zwischen seinen Codewörtern kann somit höchstens d - 1 Fehler erkennen und ⌊( d - 1)/2⌋ Fehler korrigieren . [ 2 ] Letztere Zahl wird auch als Packungsradius oder Fehlerkorrekturfähigkeit des Codes bezeichnet. [ 4 ]

Geschichte und Anwendungen

Die Hamming-Distanz ist nach Richard Hamming benannt, der das Konzept 1950 in seiner grundlegenden Arbeit über Hamming-Codes , „Error detecting and error correcting codes“ , einführte. [ 5 ] Die Hamming-Gewichtsanalyse von Bits wird in verschiedenen Disziplinen verwendet, darunter Informationstheorie , Codierungstheorie und Kryptographie . [ 6 ]

In der Telekommunikation wird die Hamming-Distanz verwendet , um die Anzahl der invertierten Bits in einem Binärwort fester Länge als Fehlerschätzung zu zählen. Daher wird sie manchmal auch als Signaldistanz bezeichnet . [ 7 ] Für q -äre Zeichenketten über einem Alphabet der Größe q  ≥ 2 wird im Fall des q-ären symmetrischen Kanals die Hamming-Distanz verwendet , während die Lee-Distanz für die Phasenumtastung oder allgemeiner für Kanäle, die anfällig für Synchronisationsfehler sind, verwendet wird, da die Lee-Distanz Fehler von ±1 berücksichtigt. [ 8 ] Wenn q ≥ 2, stimmen die Hamming-Distanzen oder beide Distanzen überein, da sich jedes Paar von Elementen aus q ≥ 2 um 1 unterscheidet, sind die Distanzen für größere q ≥ 2 jedoch unterschiedlich .

The Hamming distance is also used in systematics as a measure of genetic distance.[9]

However, for comparing strings of different lengths, or strings where not just substitutions but also insertions or deletions have to be expected, a more sophisticated metric such as the Levenshtein distance may be more appropriate.[10]: 32

Algorithm example

The following function, written in Python 3, returns the Hamming distance between two strings: 

defhamming_distance(string1:str,string2:str)->int:"""Return the Hamming distance between two strings."""iflen(string1)!=len(string2):raiseValueError("Strings must be of equal length.")dist_counter=0forninrange(len(string1)):ifstring1[n]!=string2[n]:dist_counter+=1returndist_counter

The following C function will compute the Hamming distance of two integers (considered as binary values, that is, as sequences of bits). The running time of this procedure is proportional to the Hamming distance rather than to the number of bits in the inputs. It computes the bitwiseexclusive or of the two inputs, and then finds the Hamming weight of the result (the number of nonzero bits) using an algorithm of Wegner (1960) that repeatedly finds and clears the lowest-order nonzero bit. Some compilers support the __builtin_popcount function which can calculate this using specialized processor hardware where available. 

inthamming_distance(unsignedx,unsignedy){intdist=0;// Der ^-Operator setzt nur die unterschiedlichen Bits auf 1. for ( unsigned val = x ^ y ; val > 0 ; ++ dist ) { // Anschließend zählen wir die auf 1 gesetzten Bits nach der Peter-Wegner-Methode. val = val & ( val - 1 ); // Die niedrigstwertige 1 von val wird auf Null gesetzt. }// Gibt die Anzahl der unterschiedlichen Bits zurück return dist ; }

Eine schnellere Alternative ist die Verwendung des Assembler-Befehls zur Populationszählung ( popcount ). Bestimmte Compiler wie GCC und Clang stellen diesen über eine intrinsische Funktion zur Verfügung: 

// Hamming-Distanz für 32-Bit-Ganzzahlen int hamming_distance32 ( unsigned int x , unsigned int y ) { return __builtin_popcount ( x ^ y ); }// Hamming-Distanz für 64-Bit-Ganzzahlen int hamming_distance64 ( unsigned long long x , unsigned long long y ) { return __builtin_popcountll ( x ^ y ); }

Siehe auch

Referenzen

  1. ^ Waggener, Bill (1995). Pulscodemodulationsverfahren . Springer. S. 206. ISBN 978-0-442-01436-0Abgerufen am 13. Juni 2020 .
  2. ^ a b c d Robinson, Derek JS (2003). Einführung in die abstrakte Algebra . Walter de Gruyter . S.  255–257 . ISBN 978-3-11-019816-4Die
  3. ^ Warren Jr., Henry S. (2013) [2002]. Hacker's Delight (2. Aufl.). Addison Wesley – Pearson Education, Inc. S.  81–96 . ISBN 978-0-321-84268-80-321-84268-5.
  4. ^ a b Cohen, G. ; Honkala, I.; Litsyn, S.; Lobstein, A. (1997), Covering Codes , North-Holland Mathematical Library, vol. 54, Elsevier , pp.  16–17 , ISBN 978-0-08-053007-9
  5. ^ Hamming, RW (April 1950). „Fehlererkennungs- und Fehlerkorrekturcodes“ ( PDF) . The Bell System Technical Journal . 29 (2): 147–160 . doi : 10.1002/j.1538-7305.1950.tb00463.x . hdl : 10945/46756 . ISSN 0005-8580 . S2CID 61141773. Archiviert (PDF) vom Original am 09.10.2022.  
  6. ^ Jarrous, Ayman; Pinkas, Benny (2009). „Sichere Hamming-Distanz-basierte Berechnung und ihre Anwendungen“. In: Abdalla, Michel; Pointcheval, David; Fouque, Pierre-Alain; Vergnaud, Damien (Hrsg.). Angewandte Kryptographie und Netzwerksicherheit . Lecture Notes in Computer Science. Band 5536. Berlin, Heidelberg: Springer. S.  107–124 . doi : 10.1007/978-3-642-01957-9_7 . ISBN 978-3-642-01957-9Die
  7. ^ Ayala, Jose (2012). Integrated Circuit and System Design . Springer . S. 62. ISBN 978-3-642-36156-2Die
  8. ^ Roth, Ron (2006). Einführung in die Codierungstheorie . Cambridge University Press . S. 298. ISBN 978-0-521-84504-5Die
  9. Pilcher , Christopher D.; Wong, Joseph K.; Pillai, Satish K. (18.03.2008). „Ableitung der HIV-Übertragungsdynamik aus phylogenetischen Sequenzbeziehungen“ . PLOS Medicine . 5 (3): e69. doi : 10.1371/journal.pmed.0050069 . ISSN 1549-1676 . PMC 2267810. PMID 18351799 .   
  10. ^ Navarro, Gonzalo (2001). „Eine geführte Tour zur approximativen String-Suche“ (PDF) . ACM Computing Surveys . 33 (1): 31–88 . CiteSeerX 10.1.1.452.6317 . doi : 10.1145/375360.375365 . S2CID 207551224 .  

Weiterführende Literatur