Gray-Code
Du möchtest wissen, was ein Gray-Code ist? Im folgenden Beitrag zeigen wir dir, wie du einen Gray-Code bilden kannst und was es genauer mit diesem auf sich hat.
Inhaltsübersicht
Gray-Kodierung
Ein binärer Code besteht aus Nullen und Einsen und kann beispielsweise so aussehen. Die einzelnen Stellen heißen Bits. Das niederwertigste Bit steht ganz rechts, es hat die Wertigkeit 2 hoch Null. Das vorderste Bit steht an der achten Stelle und hat die Wertigkeit 2 hoch sieben.
Eine binäre Folge von 8 Bit heißt übrigens Byte. Unser Codewort besteht aus 8 Bit und ist folglich also genau 1 Byte groß. Wir versenden nun unser Codewort an einen Empfänger. Er empfängt 1010 0100. Da stimmt ja was nicht. Das letzte Bit ist falsch, an der niederwertigsten Stelle müsste eine eins stehen. Umgangssprachlich bezeichnet man dies auch als gekipptes Bit.
Auch das dritte Bit ist falsch. Die Hamming-Distanz zwischen dem gesendeten und dem empfangenen Wort ist 2. Denn zwei Bits unterscheiden sich vom Original. Die Hamming-Distanz steht also für die Anzahl an unterschiedlichen Bits zwischen zwei gleich langen Codewörtern.
Definition Gray-Code
Was ist ein Gray-Code eigentlich? Der Merksatz dafür lautet: Der Gray-Code ist ein stetiger binärer Code, bei dem sich benachbarte Codewörter nur in einem einzigen Bit unterscheiden. Die Hamming-Distanz benachbarter Codewörter ist 1.
Stetig bedeutet dabei, dass das letzte und das erste Codewort auch „Nachbarn“ sind und ihre Hamming-Distanz demnach eins sein muss.
Bildung Gray-Code mit zehn verschiedenen Codewörtern
Um den Gray-Code zu bilden, brauchen wir einen Spiegel. Du hast richtig verstanden – einen Spiegel, der dir das abbildet, was du bereits schon siehst, nur eben spiegelverkehrt.
Wir nehmen ein Blatt und schreiben darauf eine Null und darunter eine Eins. Nun legen wir einen Spiegel darunter und schreiben auf, was wir im Spiegel sehen. Auf unserem Blatt steht jetzt null eins eins null. Die Kästchen davor füllen wir oberhalb des Spiegels mit einer Null und unterhalb mit einer Eins.
Du hast nun deinen ersten Gray-Code entworfen. Allerdings besteht dein Gray-Code nur aus vier Codewörtern – wir hätten aber gerne 10 verschiedene Codewörter.
Spiegeln wir also unseren Gray-Code erneut an der Spiegelachse. Diese befindet sich immer horizontal unter dem letzten Codewort. Damit unser Code eindeutig ist, also jedes Codewort nur einmal vorkommt, füllen wir die Kästchen oberhalb der Spiegelachse wieder mit Nullen und unterhalb mit Einsen. Jedes Codewort kommt jetzt genau einmal vor.
Der Gray-Code ist einschrittig. Das heißt: wenn wir von Codewort zu Codewort springen, dann verändert sich immer nur ein Bit. Auch zwischen dem letzten und dem ersten Codewort verändert sich nur ein Bit. Wir können den Gray-Code also auch kreisförmig darstellen und das Startwort an jeder beliebigen Stelle wählen. Die Gray-Kodierung besteht nun aber immer noch nur aus acht Codewörtern. Wir sind also immer noch nicht ganz fertig. Holen wir nochmal unseren Spiegel raus und gehen nach dem gleichen Schema wie gerade eben vor. Zuerst spiegeln wir horizontal unter dem letzten Codewort alle bisherigen Codewörter.
Da jedes Codewort nun zweimal vorkommt, füllen wir wieder mit Nullen oberhalb der Spiegelachse und mit Einsen unterhalb der Spiegelachse auf.
Unser Gray-Code hat nun 16 Codewörter. Wir haben unser Ziel somit erreicht. Was ist nun aber, wenn du genau zehn Codewörter brauchst und dein Code immer noch stetig sein soll? Dann kannst du fünf Codewörter oberhalb und fünf Wörter unterhalb der Spiegelachse nehmen, dann ist dein Code immer noch stetig. Die Hammingdistanz zwischen deinem ersten und letzten Codewort ist dann also eins.
Übrigens: auf den Graycode kannst du natürlich auch durch Herumprobieren kommen. Aber mal ehrlich, wer hat schon Zeit solange zu testen, bis ein einschrittiger, stetiger Code rauskommt. Der Gray-Code eignet sich sehr gut zu Fehlererkennung in aufeinander folgenden Abläufen. Dein System erkennt sofort, wenn mehr als ein Bit kippt und weiß somit, wann das Codewort falsch ist. Jetzt kannst du Fehler optimal erkennen.