8.2
⇒ 1 Klasse
für
⇒ 2 Klassen
für
⇒ 4 Klassen
für
-
-
-
-
-
-
-
-
⇒ 8
für
⇒ 16
8.4
Da jeder Knoten in jeder Dimension genau an zwei Positionen sein kann.
Kann man jeden Knoten als binär Zahl mit Zeichen darstellen.
Der Hamming-Abstand ist die Menge an ungleicher Bits zweier gleichlanger binär Zahlen.
Es sind alle Knoten verbunden die sich genau in einem Bit unterscheiden.
Also mit einem Hamming-Abstand von 1.
Also ist jede Reinfolge der Knoten ein Hamming Kreis wenn sich jede binär Zahl zu nächste einen Hemming-Abstand von 1 hat. (Eingeschlossen der ersten zur letzen)
Eine Reinfolge kann man mit der Funktion:
bilden sodass
ein Hamming Kreis ist.
| i | i >> 1 | i xor (i >> 1) |
|---|---|---|
| 000 | 000 | 000 |
| 001 | 000 | 001 |
| 010 | 001 | 011 |
| 011 | 001 | 010 |
| 100 | 010 | 110 |
| 101 | 010 | 111 |
| 110 | 011 | 101 |
| 111 | 011 | 100 |
Defintionen
exklusives oder (XOR) ist ein Boolischer operator mit der Wahrheitstablle:
Um 1 nach rechts verschieben ist ein operator der die binär Zahl um eine stelle nach rechts verschiebt:
Beweis
XOR setzt alle Bits auf 1 die sich in den beiden Zahlen unterschieden.
Der Suffix von hat immer diese Struktur:
also eine Null gefolgt von Einsen.
Wenn die Zahl um 1 erhört wird, wird die Null zu einer Eins und die Einsen zu Nullen.
Daher unterscheiden sich und nur in den unteren Bits.
Wenn man nun betrachtet unterschneien sich hier und nur in den unteren Bits.
Daher wenn man und betrachtet:
- Die oberen Bits sind unverändert.
- Das Bit wird einmal geändert.
- Und die Bits werden zweimal von und geändert und ändern sich damit im XOR nicht.
Somit ändert sich im XOR immer das te Bit.
Dazu ist
und
Beweis ist eine bijektion per kontradiktion
Angenommen
Betrachte die höchste position wo sich die Bits von und unterscheiden.
An der Stelle sind und gleich.
Daher ist