Hamming-Distanz

Anfang der Woche zeigte die Leuchtanzeige oben auf dem Gesundheitsamt im Wechsel die Uhrzeit an, danach:

28_07

gefolgt von:

28_grad_c

Fragte mich, wie groß die Hamming-Distanz zwischen den letzten beiden Anzeigen sei. Heißt, wieviele Segmente geswitcht werden müssen, um von der einen auf die nächste zu kommen. Nicht viele, dachte ich.

Guckt man sich das genauer an, werden die drei unteren Segmente der 0 aus- und das mittlere eingeschaltet – macht vier – und von der 7 werden die beiden rechten aus- und zwei linke und das untere eingeschaltet – macht fünf. Zusammen macht das 9 Veränderungen. Das Hamming-Gewicht der ersten Anzeige war HG(„2807“) = HG(„2“) + HG(„8“) + HG(„0“) + HG(„7“) = 5 + 7 + 6 + 3 = 21. Das Hamming-Gesicht der zweiten Anzeige HG(„28°C“) = HG(„2“) + HG(„8“) + HG(„°“) + HG(„C“) = 5 + 7 + 4 + 4 = 20.

In diesem Fall also ist der Hamming-Abstand zweier Anzeigen größer als die Differenz ihrer Gewichte. Ist das immer so? Nein: HG(„0“) = 6, HG(„8“) = 7, |HG(„0“) – HG(„8“)| = |6 – 7| = |-1| = 1, aber HA(„0“, „8“) auch 1. Also „größer“ abschwächen zu „größer gleich“, gilt es dann? Ein Abstand von 1 bedeutet, dass ein eingeschaltetes Sement aus- oder aber ein ausgeschaltetes Segment eingeschaltet wird. Im ersten Fall verringert sich das Gewicht um 1, im zweiten erhöht es sich um 1. Ein Abstand von 2 aber kann bedeuten, dass ein Segment aus-, ein anderes aber eingeschaltet wurde, was das Gewicht nicht verändert. Daher der Abstand der Hamming-Gewichte kleiner gleich dem Hamming-Abstand. Beweis: Teile die Veränderungen in der Segment-Anzeige in zwei Klassen auf: m Ausschaltungen von eingeschalteten Segmenten und n Einschaltungen von ausgeschalteten Segmenten. Dann beträgt der Hamming-Abstand m + n und die Differenz der Hamming-Gewichte |m – n|. Betrachte die Fälle m >= n => |m – n| = m – n <= m – n + 2*n = m + n, sowie m < n => |m – n| = n – m <= n – m + 2*m = n + m = m + n. In beiden Fällen ist |m – n| <= m + n.

Metriken recht interessant. Abstände können willkürlich gewählt werden, solange sie skalar sind, nicht negativ und der Dreiecksungleichung genügen. Beispiel: der Abstand zwischen mir und einem Arbeitskollegen, die wir uns über das Thema unterhalten (also mehr ich, aber er hört zu). Gewohntester Abstand der in Metern oder Zentimetern zwischen uns. Mathematischer gesprochen, das Mininum aller Abstände zwischen jedem Hautpartikel von mir und jedem Hautpartikel von ihm. Ungewöhnlicher die Differenz unserer Körpergrößen. Unsere Altersdifferenz. Diffizil wird es bei Farbdifferenzen, unserer Augenfarben etwa. Da müssen Unterschiede in einem mehrdimensionalen Farbraum auf einen Skalar gebracht werden, durch euklidischen Abstand etwa. Wären es Farben aus dem Regenbogen nur, könnte man die Wellenlängendifferenz in Nanometern als Abstand nehmen.

*

Der Gray-Code zeichnet sich dadurch aus, dass aufeinanderfolgende Werte sich in nur einem Bit unterscheiden. Ihre Hamming-Distanz ist 1. In Lara Croft konnte ich das vor Jahrzehnten ausnutzen. Da gab es drei Schalter ein Stück voneinander entfernt. Jeder Schalter konnte nach oben oder nach unten gelegt werden. Es waren also 2^3 = 8 Schalterstellungen möglich. Nur eine dieser Kombinationen öffnete die Tür. Statt jetzt von 0 bis 7 hochzuzählen und die entsprechende Kombination (z.B. 5 = 101 binär, heißt ersten Schalter nach unten, zweiten nach oben, dritten nach unten legen und hören, ob die Tür aufgeht) einzustellen, suchte ich nach einer weniger aufwändigen Methode. Denn z.B. der Schritt von 3 = 011 nach 4 = 100 bedeutete, alle drei Schalter umzulegen, weil die Hamming-Distanz 3 ist. Da bot sich der Gray-Code an, welcher die acht Zahlen in einer anderen Reihenfolge durchläuft, nämlich:

000 = 0
001 = 1
011 = 3
010 = 2
110 = 6
111 = 7
101 = 5
100 = 4

Ziemlich zufrieden war ich, dass ich mit nur sieben Schalterumlegungen alle Kombinationen abgrasen konnte. Aber eine andere Lebenssituation fällt mir leider gerade nicht ein, wo ich einen Gray-Code mal nutzen konnte, schade.

Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s


%d Bloggern gefällt das: