Digitaltechnik

Hamming-Distanz

Inhaltsübersicht

Mithilfe der Hemming Distanz, kannst du festlegen, inwieweit du gekippte Bits in einem Code erkennen, beziehungsweise korrigieren kannst.

 

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.

Binärcode aufstellen
Binärcode aufstellen

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.

Hamming-Distanz
Hamming-Distanz

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.

Beispiel Hamming-Distanz
Beispiel Hamming-Distanz

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:

Minimale Hamming-Distanz berechnen
Minimale Hamming-Distanz berechnen

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.


Andere Nutzer halten diese Inhalte aus dem Bereich „Digitaltechnik“ für besonders klausurrelevant

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.