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.
Studyflix vernetzt: Hier ein Video aus einem anderen Bereich
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.
Hamming-Distanz — häufigste Fragen
(ausklappen)
Hamming-Distanz — häufigste Fragen
(ausklappen)-
Was ist der Unterschied zwischen Hamming-Distanz und Hamming-Gewicht?Die Hamming-Distanz ist die Anzahl der Bitpositionen, an denen sich zwei gleich lange Codewörter unterscheiden. Das Hamming-Gewicht ist dagegen die Anzahl der Einsen in einem einzelnen Codewort. Das Gewicht entspricht der Hamming-Distanz dieses Codeworts zum Nullwort (nur Nullen).
-
Müssen die Codewörter für die Hamming-Distanz gleich lang sein?Für die Hamming-Distanz müssen die Codewörter gleich lang sein, weil man Bits positionsweise miteinander vergleicht und dann die Unterschiede zählt. Bei unterschiedlich langen Bitfolgen ist ohne zusätzliche Festlegung unklar, welche Stellen überhaupt zusammengehören. In Codes verwendet man deshalb feste Wortlängen.
-
Wie bestimmt man die minimale Hamming-Distanz, wenn man mehrere gültige Codewörter hat?Die minimale Hamming-Distanz bestimmt man, indem man den Hamming-Abstand für jedes Paar verschiedener gültiger Codewörter berechnet und anschließend den kleinsten dieser Werte nimmt. Dieser kleinste Abstand ist die „engste Stelle“ zwischen zwei erlaubten Codewörtern. Er entscheidet über die Fehlerfestigkeit des Codes.
-
Warum kann ein Code manchmal Fehler erkennen, aber den richtigen Code nicht eindeutig korrigieren?Ein Code kann Fehler erkennen, aber nicht eindeutig korrigieren, wenn ein verfälschtes Codewort zwar als „ungültig“ auffällt, aber gleich gut zu mehreren gültigen Codewörtern passt. Dann gibt es keine eindeutige beste Rückübersetzung. Eindeutige Korrektur klappt nur, wenn genau ein gültiges Codewort am nächsten liegt.
Nach Beantwortung speichern wir deine Antwort, um Studyflix zu verbessern. Mehr dazu erfährst du in unserer Datenschutzerklärung.
Codierung verstehen
Die Hamming-Distanz gehört zur Codierung und zeigt, wie sich Codewörter voneinander unterscheiden. Wer sich mit Codierung beschäftigt, ordnet Bitmuster, vergleicht Codewörter und betrachtet die Übertragung von Daten. So wird klar, warum ein größerer Abstand zwischen Codewörtern für sichere Fehlererkennung und Fehlerkorrektur wichtig ist. Im Informatikbereich findest du passende Videos zu diesem und verwandten Themen.
