Hamming-Distanz
Mithilfe der Hemming Distanz, kannst du festlegen, inwieweit du gekippte Bits in einem Code erkennen, beziehungsweise korrigieren kannst.
Inhaltsübersicht
Was ist die Hamming-Distanz?
Benannt ist sie nach dem amerikanischen Mathematiker Richard Wesley Hamming (1915-1998). Sie wird auch Hamming-Abstand oder Hamming-Gewicht genannt und ist ein Maß für die Unterschiedlichkeit von Codewörtern. Sie kann für sämtliche Alphabete und Zahlensysteme genutzt werden, am häufigsten ist jedoch die Nutzung am Binärsystem. Damit beschäftigen wir uns auch in diesem Beitrag.
Wie berechnet sich die Hamming-Distanz?
Damit du die Hamming-Distanz verstehst, codieren wir nun acht Codewörter, die den dezimalen Werten Null bis Sieben entsprechen.
Die Anzahl der sich unterscheidenden Bits zweier Codewörter ist die Hamming-Distanz. Wir erweitern unsere Tabelle um eine neue Spalte, in die wir den Hamming-Abstand aller Codewörter zum ersten Codewort mit dem dezimalen Wert 0 eintragen.
Fangen wir mit der ersten Zeile an: Das Codewort 0-0-0 unterscheidet sich in keinem Bit von dem Codewort 0-0-0. Die Hamming-Distanz eines Codewortes zu sich selbst ist also immer 0. Das zweite Codewort 0-0-1 unterscheidet sich nur in einem Bit von dem ersten Codewort 0-0-0 – der Hamming-Abstand ist also 1. Genauso ist es beim dritten Codewort 0-1-0. Beim vierten Codewort 0-1-1 ist den Hamming-Abstand dementsprechend 2. Du musst also einfach nur die Anzahl der unterschiedlichen Bits zählen.
Um jetzt bei zwei etwas längeren Codewörtern den Hamming-Abstand zu ermitteln musst du einfach abzählen an wie vielen Stellen sich die Codes unterscheiden.
Die Hamming-Distanz in der Praxis
Aber was bringt uns diese Distanz eigentlich? Der Hamming-Abstand wird zur Fehlererkennung und Fehlerkorrektur genutzt. Bitfehler können zum Beispiel beim Übertragen von Codewörtern entstehen. Ob ein fehlerhaftes Codewort erkannt oder korrigiert wird, hängt von der Hamming-Distanz ab.
Dazu schauen wir die Tabelle mit den Hamming-Distanzen an und suchen den minimalen Wert zwischen zwei gültigen Codewörtern. Bei einer minimalen Hamming-Distanz von d gilt:
• Es sind d-1 Fehler erkennbar.
• Es sind e gleich d minus 1 durch 2 Bitfehler korrigierbar.
Beispiel Getränke Automat
Das findest du noch etwas verwirrend? Stell dir einfach einmal vor, du bist Ingenieur in einer großen Firma und entwirfst einen Getränkeautomaten mit vielen verschiedenen Zuständen. Der Zustand Null ist üblicherweise der Ruhezustand, also der Zustand in dem der Getränkeautomat zwar läuft aber niemand eine Taste gedrückt hat oder Geld eingeworfen hat. Damit beim Kauf einer Cola auch Cola rauskommt müssen die Bits stets überprüft werden. Der Zustand „Cola-Preis anzeigen“ hat nun das Codewort 0-0-1-1, das Codewort für den Zustand „Cola ausgeben“ ist 1-0-1-1. Bei deiner Codierung sollen nun mindestens zwei Bitfehler korrigierbar sein, und mindestens drei gekippte Bits erkannt werden.
Aber was bringt es einen Fehler zu erkennen und diesen nicht zu korrigieren? Wenn ein Bitfehler erkannt wird, dann kann der Automat verhindern, dass eine falsche Aktion ausgeführt wird, indem er das möglicherweise schon eingeworfene Geld zurückgibt und danach zurück in den Ruhezustand 0-0-0-0 geht.
Minimale Hamming-Distanz berechnen
Wenn du die gegebenen Formeln mit der minimalen Hamming-Distanz umformst, ergibt sich:
Da im Getränkeautomaten drei Bitfehler erkannt werden sollen, ist die minimal erlaubte Hamming-Distanz zwischen deinen Codewörtern 4. Für die Korrektur von zwei Bits braucht deine Codierung einen minimalen Hamming-Abstand von 5. Letztendlich müssen die Codewörter zur Definition deiner Zustände also eine Hamming-Distanz von 5 haben und damit kannst du sogar 4 Bitfehler erkennen. Wie du siehst, muss für eine Fehlererkennung der Hamming-Abstand also möglichst groß sein. Unsere Codierung der dezimalen Werte null bis sieben eignet sich bei einer minimalen Hamming-Distanz von eins also weder zur Fehlererkennung noch zu deren Korrektur.