Hamming-Codes

Wie der Inhalt eines QR-Codes in Wirklichkeit verändert wird um Fehlertoleranz zu erzeugen, ist zu umfangreich um es von Hand zu berechnen. Deshalb verwenden wir eine andere Methode, die zwar einfacher zu berechnen ist, dafür aber nur ein einziges falsches Bit erkennen kann. Dafür erweitern wir unsere Bitfolge und erzeugen sogenannte Hamming Codes.

Unsere Bitfolge:

1 0 1 1 0 0 0 1 0 1 1 1 0 0 1

Zunächst fügen wir in unserer Folge Leerstellen an den Stellen ein, die einer Zweierpotenz (1, 2, 4, 8, usw.) entsprechen:

_ _ 1 _ 0 1 1 _ 0 0 0 1 0 1 1 _ 1 0 0 1

Dann berechnen wir die sogenannten Kontrollbits, die an diesen Stellen in den Code eingefügt werden.

Für das erste Kontrollbit betrachten wir immer abwechselnd ein Bit und zählen die Anzahl der Einsen. Erhalten wir eine ungerade Anzahl ist das Kontrollbit eine 1, bei einer geraden Anzahl eine 0, sodass wir am Ende immer eine gerade Anzahl an Einsen haben.

_ _ 1 _ 0 1 1 _ 0 0 0 1 0 1 1 _ 1 0 0 1 → 4 Einsen → gerade → 1. Kontrollbit = 0

Für das zweite Kontrollbit betrachten wir nun ausgehend von der zweiten Lücke immer 2 Bits, lassen dann 2 aus, betrachten wieder 2, usw. Anschließend zählen wir wieder die Anzahl der Einsen und entscheiden dann wie beim 1. Kontrollbit ob das Kontrollbit eine 1 oder eine 0 sein muss.

0 _ 1 _ 0 1 1 _ 0 0 0 1 0 1 1 _ 1 0 0 1 → 5 Einsen → ungerade → 2. Kontrollbit = 1

Aufgabe 1

Berechne die restlichen Kontrollbits

0 1 1 __ 0 1 1 __ 0 0 0 1 0 1 1 __ 1 0 0 1 → ___ Einsen →     → 3. Kontrollbit =

0 1 1 __ 0 1 1 __ 0 0 0 1 0 1 1 __ 1 0 0 1 → ___ Einsen →     → 4. Kontrollbit =

0 1 1 __ 0 1 1 __ 0 0 0 1 0 1 1 __ 1 0 0 1 → ___ Einsen →     → 5. Kontrollbit =

Codierte Folge:  0 1 1 __ 0 1 1 __ 0 0 0 1 0 1 1 __ 1 0 0 1

Fehler finden

Zur Überprüfung einer gegebenen Folge markieren wir wie zuvor die zu betrachtenden Stellen und zählen die Einsen. Erhalten wir eine gerade Anzahl an Einsen, ist das Kontrollbit in Ordnung. Andernfalls merken wir uns die Stelle, an der das Kontrollbit nicht korrekt ist. Haben wir alle Kontrollbits geprüft, werden alle Stellen, die nicht korrekt waren, addiert und man erhält die Stelle an der das Bit fehlerhaft ist.

Aufgabe 2

Verändere in der folgenden Bitfolge eine Stelle und schreibe die veränderte Folge auf ein Blatt Papier. (Wichtig! Merke dir welche Stelle du verändert hast, oder schreib es dir so auf, dass dein Nachbar es nicht sehen kann) Tausche nun das Blatt mit deinem Nachbarn und finde auf diesem Blatt das falsche Bit, das dein Nachbar verändert hat.

Bitfolge: 1 0 1 1 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0

Tipp: Schreibe dir für jedes Kontrollbit die Bitfolge auf, damit du übersichtlich markieren kannst, welche Bits du beachten musst.

SCHULHOF Beispiel

Für unser SCHULHOF Beispiel von vorher sieht die veränderte Bitfolge dann so aus:

11011000 00001000 00101001 10100001 11010010 00010101 01010011 00010010 00001001 11101000 1100000

Diese Folge wird mit Nullen am Ende aufgefüllt, sodass immer volle Achterblöcke entstehen. Anschließend wird diese Bitfolge zusammen mit Füllworten (im Bild in blau) in den QR-Code eingetragen.

[1]

Anmerkung

Normalerweise werden die Redundanzwerte auch über die Füllworte berechnet. Da das in unserem Fall aber zu aufwendig ist, beschränken wir uns auf die Fehlerbehebung des eigentlichen Inhalts und füllen den QR-Code anschließend mit Füllworten auf.