Gray-Code

Gray-Code
stetig	ja
Hamming-Abstand	1

Dieser Artikel wurde im Projekt Kryptologie zur Verbesserung eingetragen. Hilf mit, ihn zu bearbeiten, und beteilige dich an der Diskussion!

Folgende Verbesserungen wären gut: Der vorliegenden WP-Artikelseite wird das Attribut einer „mangelnden Allgemeinverständlichkeit“ zugeschrieben. Es wäre daher eine Hilfe, wenn jemand mit Sachverstand sich dieser Thematik mal annehmen könnte. Gruß --A.Abdel-Rahim (Diskussion) 01:58, 22. Feb. 2022 (CET)

Der Gray-Code ist ein stetiger Code, bei dem sich benachbarte Codewörter nur in einer einzigen binären Ziffer unterscheiden, die Hamming-Distanz benachbarter Codewörter ist 1. Übertragungsfehler bei sich kontinuierlich ändernden digitalen Signalen auf mehradrigen Leitungen werden so verringert, da sich unterschiedliche Laufzeiten nicht auswirken können. Er dient als Kodierungsverfahren zur robusten Übertragung digitaler Größen über analoge Signalwege. Der Code ist nach dem Physiker Frank Gray benannt, welcher 1953 das Patent auf dieses Verfahren erhielt.[1]

Die Abfolge des Standard Gray-Codes lässt sich nach einer simplen Regel erzeugen. Beginnend mit 0 (also alle Bits 0) ändert man jeweils das niederwertigste Bit (von 0 auf 1 oder von 1 auf 0), das geändert werden kann, ohne dass dabei eine Zahl entsteht, die schon daran war.

Es kann aber auch ein balancierter Gray-Code konstruiert werden, wobei sich alle Stellen (Bits) der Codewörter gleich häufig von benachbarten Codewörtern unterscheiden. Beim durchgehen aller Codewörter in korrekter Reihenfolge ändert sich dann jede Stelle gleich oft.[2]

Meistens ist der Gray-Code als Binärcode ausgeführt, kann aber auch für mehrstufige Übertragungswege benutzt werden.

Generierung aus Binärcode

Logische Operatoren

Die folgenden Punkte zeigen, wie man Schritt für Schritt aus einem Binärcode eine Gray-codierte Binärzahl erhält:

X1: Dualzahl im Binärcode
X2: Rechts-Shift der Dualzahl um 1 Bit
X3: Modulo-2-Addition (XOR-Verknüpfung) von X1 und X2; dies ist die gewünschte Zahl im Graycode.

Das gleiche als Pseudocode:

Binärcode X1 → Graycode: X3 = (X1 XOR X2)

Und als Formel:

$x_{3}=x_{1}\oplus (x_{1}\gg 1)$

Generatormatrix

Da der Gray-Code ein linearer Code ist, kann man ihn mit einer Generatormatrix $G$ erzeugen. Ein binäres Wort $w$ der Länge $n$ kann man als Vektor eines $n$ -dimensionalen $\mathbb {F} _{2}$ -Vektorraums $\mathbb {F} _{2}^{n}$ betrachten. Sei $w$ nun ein Zeilenvektor, dann lässt sich die Kodierung des Wortes $w$ in das Codewort $c$ wie folgt darstellen:

$c=w\underbrace {\begin{bmatrix}1&1&&0\\&\ddots &\ddots &\\&&\ddots &1\\0&&&1\end{bmatrix}} _{=:G}$

Die Dekodierung erfolgt mit der Multiplikation der Inversen $G^{-1}$ von $G$ . Diese hat folgende Form:

$G^{-1}={\begin{bmatrix}1&\cdots &\cdots &1\\&\ddots &&\vdots \\&&\ddots &\vdots \\0&&&1\end{bmatrix}}\in \mathbb {F} _{2}^{n\times n}$

Der Vektorraum $\mathbb {F} _{2}^{n}$ lässt sich anschaulich mit Hyperwürfeln darstellen.

Generierung als Gray-Zähler

Man kann auch direkt einen Gray-Code-Zähler in Hardware (z. B. in HDL) programmieren. Hierzu ist es hilfreich, ein Hilfsregister zu benutzen, das mit jedem Taktzyklus toggelt.

 Q_h [n+1] = !Q_h [n]
 Q_h [0  ] =  0     wenn der Gray-Code-Zähler mit Null startet also Q[0]=0, oder Q[0] eine gerade Anzahl an Einsen hat. Bei anderer Initialisierung würde der Zähler rückwärts laufen.

Damit wird die Kombinatorik recht übersichtlich:

 Q₀[n+1] = !(Q₀[n] ^   Q_h[n] )
 Q₁[n+1] =   Q₁[n] ^ ( Q₀[n] &  Q_h[n] )
 Q₂[n+1] =   Q₂[n] ^ ( Q₁[n] & !Q₀[n] &  Q_h [n] )
 Q₃[n+1] =   Q₃[n] ^ ( Q₂[n] & !Q₁[n] & !Q₀ [n] & Q_h [n] )
        …
 Q_k-1[n+1] =   Q_k-1[n] ^ ( Q_k-2[n] & !Q_k-3[n] & …  & !Q₁ [n] & !Q₀ [n] & Q_h [n])
 Q_k[n+1] =   Q_k[n] ^ (!Q_k-2[n] &         …  & !Q₁ [n] & !Q₀ [n] & Q_h [n])

Der Unterschied zwischen den Formel für das größte Bit Q_k und den kleineren Bits Q_k-1 ist nötig, damit der Zähler zyklisch ist, also der Zähler nach dem letzten Wert Q=100…00 auf den Anfangswert Q=000…00 springt. Bei einem unendlichen Zähler gäbe es keinen Unterschied.

 ^ := Exklusiv Oder / XOR / Antivalenz

 ! := Inverter / NOT / Negation

 & := Und / AND / Konjunktion

Bedeutung

Motivation für die Entwicklung dieses Codes ist das folgende Problem: Auf mehreren Adern einer elektrischen Datenleitung sollen Daten parallel übertragen werden, die sich stetig (also immer nur um ein Digit) ändern, typisch dafür sind z. B. Signale eines Temperatursensors oder eines Drehwinkelgebers. Als Dualzahl übertragen, ändern sich die Bits bei einem neuen Messwert auf jeder betroffenen Leitung theoretisch exakt gleichzeitig, und zwar sowohl am Eingang der Leitung als auch am Ausgang. Tatsächlich aber ändern sich die Bits auf der Leitung nicht gleichzeitig. Das kann verschiedene Ursachen haben: Bauteilestreuung, Laufzeiten, Asymmetrien usw. Dadurch kommt es zu ungewollten Zwischenzuständen und kurzzeitig (zwischen den roten Linien) falsch empfangenen Werten:

2-Bit-Gray-Code:

3-Bit-Gray-Code:

4-Bit-Gray-Code:

5-Bit-Gray-Code:

6-Bit-Gray-Code:

Problem bei Dualcode-Signalen

Während das theoretische Signal in der Reihenfolge

{0000}, {0001}, {0010}, {0011}, {0100}, {0101}, {0110}, {0111} usw.

abgesendet wird, kommen am Ausgang kurzzeitig andere Signalzustände an:

{0000}, {0001}, {0000}, {0010}, {0011}, {0100}, {0101}, {0111}, {0110}, {0111} usw.

Lösung mit Gray-Code

Um das zu vermeiden, werden die Steuersignalzustände mittels Gray-Code abgesendet, sodass sich immer nur ein Bit gleichzeitig ändert:

Abgesendete Sequenz: {0000}, {0001}, {0011}, {0010}, {0110}, {0111}, {0101}, {0100} usw.
Ankommende Sequenz: {0000}, {0001}, {0011}, {0010}, {0110}, {0111}, {0101}, {0100} usw.

Hier kommt also am Ausgang auch dann die gleiche Sequenz wie am Eingang an, wenn beachtliche Zeitfehler (rote Linien) auftreten.

Karnaugh-Veitch-Diagramm

Im Karnaugh-Veitch-Diagramm erkennt man den Graycode – es sind mehrere Sequenzen möglich – daran, dass Übergänge nur zwischen (horizontal oder vertikal) benachbarten Feldern vorkommen.

Reihenfolge Dualcode
	¬X₀	X₀	X₀	¬X₀
¬X₂	0	1	3	2	¬X₃
X₂	4	5	7	6	¬X₃
X₂	12	13	15	14	X₃
¬X₂	8	9	11	10	X₃
	¬X₁	¬X₁	X₁	X₁

Reihenfolge Graycode
	¬X₀	X₀	X₀	¬X₀
¬X₂	0	1	2	3	¬X₃
X₂	7	6	5	4	¬X₃
X₂	8	9	10	11	X₃
¬X₂	15	14	13	12	X₃
	¬X₁	¬X₁	X₁	X₁

Der Code eignet sich auch für zyklische Anwendungen wie der unten abgebildeten Scheibe, da sich auch beim Übergang von der höchsten Zahl auf die Null nur eine Stelle ändert.

Die Wertigkeit einer 1 an der Position $n$ im Gray-Code Zahlensystem ist $2^{n}-1$ (wobei n ab 1 zählt, also … 31, 15, 7, 3, 1). Die einzelnen Einsen werden, im Gegensatz zum normalen Binärsystem, nicht addiert, sondern von rechts beginnend subtrahiert. Beispiel: 111_Gray = 7 - (3 - 1) = 5 oder 1111_Gray = 15- (7 - (3 - 1)) = 10. Stellen, die 0 sind, werden dabei ausgelassen, Beispiel: 101_Gray = 7 - 1 = 6.

Bei der Generierung von Gray-Code wird symmetrisch vorgegangen.

Da sich benachbarte Werte nur in einer Ziffer unterscheiden, ist der Gray-Code geeignet, um Fehler in seriellen Prozessen aufzudecken.

Geometrische und graphentheoretische Darstellung

Bild 1: Würfel
Bild 2: Würfel mit Koordinatensystem
Bild 3: Die 6 Pfade zu dem Gray-Code in der Tabelle. Es handelt sich um einen Hamiltonkreis. Startpunkt: 000 (grüner Kreis jeweils links oben), Fortsetzung: grüne→blaue→rote→schwarze Linie, Endpunkt: am Startpunkt

Bild 1 zeigt den Hexaeder für 3 Variablen und Bild 2 den gleichen Würfel mit dazugehörigem Koordinatensystem. Die Knoten (Eckpunkt oder Kreise) am Einheitswürfel entsprechen jeweils einer Zeile im Gray-Code. Die Übergänge (Nachbarschaft der Zeilen) sind durch die Kanten des Würfels symbolisiert. Beim Wandern auf der Kante entsteht ein Gray-Code.

geschlossener 3-Bit-Gray-Code
a)	b)	c)	d)	e)	f)
000	000	000	000	000	000
001	100	010	010	001	100
101	101	110	011	011	110
100	001	100	001	010	010
110	011	101	101	110	011
111	111	111	111	111	111
011	110	011	110	101	101
010	010	001	100	100	001

Auf jeder Kante ändert sich genau 1 Bit. Der Gray-Code hat so viel Nachbarschaften, wie der Würfel Kanten hat. Aus dem Würfel in Bild 1 können die möglichen Pfade auf 6 verschiedenen Wegen durchschritten werden. Somit ergeben sich 6 Möglichkeiten, um einen 3-Bit-Gray-Code zu erzeugen, der die Bedingungen des Gray-Codes erfüllt (Tabelle und Bild 3). Abgesehen davon ist der Gray-Code zyklisch und der Startpunkt könnte deshalb auch an einer anderen Zeile sein. Wegen seiner einfachen rekursiven Generierungsvorschrift wird meist der binäre reflektierte Gray-Code (binary-reflected Gray code) angegeben (Spalte „e“ – vorletzte Spalte in der Tabelle). Es gibt für eine bestimmte Bitlänge eine ganze Klasse von Graycodes.

Es gibt für einen n-Bit-Gray-Code exakt so viel Varianten, wie es Hamiltonkreise auf einem n-dimensionalen Hyperwürfel gibt. Die Anzahl dieser Hyperwürfel ist in der On-Line Encyclopedia of Integer Sequences als Sequenz A003042 angegeben und (Stand Februar 2022) bis zu 6 Dimensionen bekannt.[3]

Für 3 bit gibt es beispielsweise 12 mögliche Gray-Codes:

000 001 011 010 110 111 101 100
000 001 011 111 101 100 110 010
000 001 101 100 110 111 011 010
000 001 101 111 011 010 110 100
000 010 011 001 101 111 110 100
000 010 011 111 110 100 101 001
000 010 110 111 011 001 101 100
000 010 110 100 101 111 011 001
000 100 101 111 110 010 011 001
000 100 101 001 011 111 110 010
000 100 110 111 101 001 011 010
000 100 110 010 011 111 101 001

Anwendungen

Schemazeichnung einer Scheibe mit Gray-Codierung. Die gelben Punkte stellen Lichtsensoren dar.

Ein Gray-Code Absolutwertgeber mit 13 bits

Eine Anwendungsmöglichkeit ist die Bestimmung der absoluten Position einer Scheibe oder Leiste, die mit schwarzen und weißen Balken markiert ist, die mit Lichtschranken oder anderen Sensoren abgetastet werden. Diese Position wird dann zur Winkel- oder Drehgeschwindigkeitsmessung verwendet.

Eine weitere Anwendung ist die Streifenprojektion. Dort wird eine Folge von Mustern aus parallelen Streifen auf ein Objekt projiziert. Die Nummer der Streifen ist Gray-kodiert und kann von einer beobachtenden Kamera für jeden Bildpunkt berechnet werden.

Eine andere Anwendung ist das asynchrone Einlesen von Daten. Beispielsweise wird der Gray-Code genutzt, um in Korrelatoren die Zählerstände fehlerfrei einzulesen. Selbst im ungünstigsten Fall, wenn während eines kippenden Bits eingelesen wird, ist das Ergebnis immer korrekt, da ein kippendes Bit nicht definiert ist und es zudem nur einen Unterschied von ±1 ausmacht. Diese Art des Einlesens erfordert keine Synchronisation und nur sehr wenig CPU-Zeit.

Weitere Anwendungsmöglichkeiten sind Windrichtungsmesser oder Wasserniveaumesser, Abbildung des Fahrkorbstands bei Aufzügen.

Der reflektierte Gray-Code hat eine enge Beziehung zur Lösung des Problems der Türme von Hanoi, und er beschreibt auch den Lösungsweg der Chinesischen Ringe.

Beispiel

Die Dezimalzahl $4_{10}=100_{2}$ entspricht dem Gray-Code $6_{10}=110_{2}$ . Die Dekodierung in die Dezimaldarstellung folgt dann der Regel $1\cdot 7_{10}-(1\cdot 3_{10}-0\cdot 1_{10})=4_{10}$ . Wenn mehrere Einsen in einer Gray-Code-Zahl vorkommen, werden diese voneinander subtrahiert: Der Gray-Code $7_{10}=111_{2}$ wird wie folgt dekodiert: $1\cdot 7_{10}-(1\cdot 3_{10}-1\cdot 1_{10})=5_{10}$ .

Allgemeines Verfahren: Bei einer Umwandlung ist entscheidend, an welcher Position die Einser stehen. Die Position hat Einfluss auf die Rechnung. Wenn wir uns die Zahl 100 anschauen, dann steht die Eins auf Position 3 (von rechts nach links). Den Faktor für die Eins bekommt man, indem man sich überlegt, welche Dezimalzahl maximal in einer 3-Bit Zahl binär gespeichert werden kann. In 3 Bit Binärcode kann maximal die Zahl 7 (111) gespeichert werden. Nehmen wir jetzt eine größere Binärzahl, funktioniert das praktisch analog. Binärzahl: 11010 (1 an Position 5,4 und 2). 5 Bit Binärzahl: max. 31 4 Bit Binärzahl: max. 15 2 Bit Binärzahl: max. 3

Berechnung: $31_{10}-(15_{10}-3_{10})=19$

Einen Gray-Code zurückrechnen

  for I := NumBits - 1 downto 0 do        // jedes einzelne Bit vom letzten bis zum ersten
    Value := Value or (                   // das Ergebnis jedes errechneten Bits dem Gesamtergebnis hinzufügen
      (((1 shl (I + 1)) and Value) shr 1) // das Bit der Stelle zuvor im Ergebnis
      xor                                 // xor mit
      ((1 shl I) and GrayCode)            // der aktuellen Stelle des Codes
                       );

Spezielle Gray-Codes

Gray-Codes mit m bits und Länge kleiner als 2^m

Es existieren auch Gray-Codes mit $m$ Bits mit einer Länge von weniger als $2^{m}$ . Hierfür muss Länge gerade sein. Eine Möglichkeit, sie zu konstruieren, besteht in der Verwendung eines Standard-Gray-Codes und dem paarweisen Wegstreichen entweder des ersten und des letzten Eintrags oder von Einträgen in der Mitte[4]. Die OEIS-Folge A290772[5] zählt die Anzahl der möglichen Gray-Codes der Länge $2n$ auf, wofür jeweils die minimale Anzahl von Bits verwendet werden.

Geschichte

Noch bevor die Bezeichnung Gray-Code eingeführt wurde, gab es bereits mathematische Knobelspiele, in denen das Prinzip angewendet wurde. Erst später fand der Code die Beachtung von Ingenieuren. Bereits 1874 wendete Otto Schäffler, der in Wien Telegrafen und Telefone produzierte und verbesserte, den reflektierten Gray-Code an. Der Franzose Jean-Maurice-Émile Baudot verwendete Gray-Codes im Jahr 1874 für die elektrische Telegrafie. Er erhielt für seine Arbeit die Auszeichnung der französischen Ehrenlegion.

Namensgebend war allerdings Frank Gray, Forscher in den Bell Laboratories, der den schon 1941 von George Stibitz beschriebenen Code[6] im Jahre 1947 für seine Zwecke wiederentdeckte. Unter dem Titel Pulse Code Communications wurde im Jahre 1953 ein Patent für eine Gray-kodierende Elektronenröhre erteilt.[1]

Weblinks

Commons: Gray code – Sammlung von Bildern, Videos und Audiodateien

Java-Beispiel für die Umwandlung einer Dezimalzahl in Gray-Code Darstellung (Memento vom 30. September 2007 im Internet Archive)
Algorithmen zur Erzeugung des reflektierten Gray-Codes auf dem Combinatorial Object Server

Einzelnachweise

Patent US2632058A: Pulse code communication. Angemeldet am 13. November 1947, veröffentlicht am 17. März 1953, Anmelder: Bell Telephone Labor Inc, Erfinder: Frank Gray.
Girish S. Bhat, Carla D. Savage: Balanced Gray Codes. In: The Electronic Journal of Combinatorics. 28. August 1996, ISSN 1077-8926, S. R25–R25, doi:10.37236/1249 (combinatorics.org [abgerufen am 22. Mai 2021]).
A003042: Number of directed Hamiltonian cycles (or Gray codes) on n-cube. (Formerly M2053)
Max Maxfield: How to generate Gray Codes for non-power-of-2 sequences. 29. Juni 2007. Archiviert vom Original am 19. Januar 2022. Abgerufen am 29. Januar 2022.
A290772: Number of cyclic Gray codes of length 2n which include all-0 bit sequence and use the least possible number of bits.
Patent US2307868A: Binary counter. Angemeldet am 26. November 1941, veröffentlicht am 12. Januar 1943, Anmelder: Bell Telephone Labor Inc, Erfinder: George R. Stibitz.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[US2632058-1] Patent US2632058A: Pulse code communication. Angemeldet am 13. November 1947, veröffentlicht am 17. März 1953, Anmelder: Bell Telephone Labor Inc, Erfinder: Frank Gray.

[2] Girish S. Bhat, Carla D. Savage: Balanced Gray Codes. In: The Electronic Journal of Combinatorics. 28. August 1996, ISSN 1077-8926, S. R25–R25, doi:10.37236/1249 (combinatorics.org [abgerufen am 22. Mai 2021]).

[3] A003042: Number of directed Hamiltonian cycles (or Gray codes) on n-cube. (Formerly M2053)

[4] Max Maxfield: How to generate Gray Codes for non-power-of-2 sequences. 29. Juni 2007. Archiviert vom Original am 19. Januar 2022. Abgerufen am 29. Januar 2022.

[5] A290772: Number of cyclic Gray codes of length 2n which include all-0 bit sequence and use the least possible number of bits.

[US2307868-6] Patent US2307868A: Binary counter. Angemeldet am 26. November 1941, veröffentlicht am 12. Januar 1943, Anmelder: Bell Telephone Labor Inc, Erfinder: George R. Stibitz.