Quelltext der Seite Gray-Code

{{Infobox Binärcode
| Name            = 
| Stellenzahl     = 
| bewertbar       = 
| stetig          = ja
| Gewicht         = 
| Minimaldistanz  = 
| Maximaldistanz  = 
| Hamming-Abstand = 1
| Redundanz       = 
}}
Der '''Gray-Code''' ist eine spezielle Art der  [[Code|Codierung]], bei der sich benachbarte Zahlen nur in einer einzigen Stelle unterscheiden. Dies bedeutet, dass beim Wechsel von einer Zahl zur nächsten nur ein Bit (eine binäre Ziffer) geändert wird. Diese Eigenschaft hilft, Übertragungsfehler zu reduzieren, insbesondere bei [[Digitales Signal|digitalen Signalen]], die sich schnell ändern. So können unterschiedliche [[Laufzeit (Elektrotechnik)|Laufzeiten]] in mehradrigen Kabeln keinen Einfluss auf die Datenübertragung haben.

Der Gray-Code wurde ursprünglich für [[Elektromechanisch|elektromechanische]] [[Sensor]]en und Schalter entwickelt, die anfällig für Fehler sind. Heute wird dieser Code auch in modernen digitalen Übertragungssystemen eingesetzt, wie zum Beispiel im [[DVB-T|digitalen Fernsehen]] (DVB-T) und im [[Kabelfernsehen]]. Der Code ist nach dem US-amerikanischen Physiker [[Frank Gray (Physiker)|Frank Gray]] benannt, der 1953 das [[Patent]] für dieses Verfahren erhielt.<ref name="US2632058">{{Patent| Land=US| V-Nr=2632058A| A-Datum=1947-11-13| V-Datum=1953-03-17| Titel=Pulse code communication| Anmelder=Bell Telephone Labor Inc| Erfinder=Frank Gray}}</ref>

== Generierung ==
Beginne mit einer [[Binärzahl]], die nur aus Nullen besteht. Ändere dann immer die am weitesten rechts stehende Ziffer (das niederwertigste Bit) von 0 zu 1 oder umgekehrt, solange dadurch keine Kombination entsteht, die bereits vorkam.

Eine alternative Methode, welche leichter zu merken und anzuwenden ist, besteht aus folgenden Schritten:<ref>EE Times: [https://www.eetimes.com/gray-code-fundamentals-part-2/ Gray Code Fundamentals – Part 2]</ref>
# Beginne mit dem einfachsten Gray-Code-Werten: 0 und 1. Schreibe diese übereinander:  
# Ziehe eine Linie unter die geschriebenen Zahlen und ergänze mit den gespiegelten vorhandenen Werten.
# Setze vor die ursprünglichen Werte eine 0, vor die gespiegelten eine 1.
# Wiederhole Schritte 2 und 3, bis die gewünschte Länge erreicht ist.
  1.  <math>\begin{array}{|c|} x_0 \\ \hline 0\\ 1\\ \end{array}</math>     2.  <math>\begin{array}{|c|} x_0 \\ \hline 0\\ 1\\ \hline 1 \\ 0 \end{array}</math>      3.   <math>\begin{array}{|c|c|} x_1 & x_0 \\ \hline 0 & 0  \\ 0 & 1 \\ \hline 1 & 1 \\ 1 & 0 \end{array}</math>
Der so erzeugte Code hat die Eigenschaft, dass sich niederwertige Bits häufiger ändern als höherwertige. Es kann aber auch ein balancierter Gray-Code konstruiert werden, in dem 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.<ref>{{Literatur |Autor=Girish S. Bhat, Carla D. Savage |Titel=Balanced Gray Codes |Sammelwerk=The Electronic Journal of Combinatorics |Datum=1996-08-28 |ISSN=1077-8926 |DOI=10.37236/1249 |Seiten=R25–R25 |Online=https://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i1r25 |Abruf=2021-05-22}}</ref>

Der Gray-Code wird hauptsächlich als [[Binärcode]] verwendet, kann jedoch auch für mehrstufige [[Kanal (Informationstheorie)|Übertragungswege]] eingesetzt werden.

=== 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)
oder anders ausgedrückt:
* Binärcode X1 → Graycode: X3 = (X1 XOR (X1 SHR 1))
wobei SHR der rechts Shiften Operator ist.

Und als Formel:

:<math>x_3 = x_1 \oplus (x_1 \gg 1)</math>

=== Generatormatrix ===
Da der Gray-Code ein [[linearer Code]] ist, kann man ihn mit einer [[Generatormatrix]] <math>G</math> erzeugen. Ein binäres Wort <math>w</math> der Länge <math>n</math> kann man als Vektor eines <math>n</math>-dimensionalen <math>\mathbb F_2</math>-Vektorraums <math>\mathbb F_2^n</math> betrachten. Sei <math>w</math> nun ein Zeilenvektor, dann lässt sich die Kodierung des Wortes <math>w</math> in das Codewort <math>c</math> wie folgt darstellen:

:<math>c = w \underbrace{
\begin{bmatrix}
1 & 1 &   & 0 \\
  & \ddots & \ddots  &   \\
  &   & \ddots  & 1  \\
 0 &   &   &  1  \end{bmatrix}}_{=:G}</math>

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

:<math>
G^{-1} =
\begin{bmatrix}
1 & \cdots & \cdots & 1 \\
  & \ddots &  &   \vdots \\
  &  & \ddots &   \vdots \\
0 &   &   & 1 \end{bmatrix} \in \mathbb F_2^{n\times n}
</math>

Der Vektorraum <math>\mathbb F_2^n</math> lässt sich anschaulich mit [[Hyperwürfel]]n darstellen.

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

  Q<sub>h</sub> [n+1] = !Q<sub>h</sub> [n]
  Q<sub>h</sub> [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<sub>0  </sub>[n+1] = !(Q<sub>0  </sub>[n] ^   Q<sub>h  </sub>[n] )
  Q<sub>1  </sub>[n+1] =   Q<sub>1  </sub>[n] ^ ( Q<sub>0  </sub>[n] &  Q<sub>h  </sub>[n] )
  Q<sub>2  </sub>[n+1] =   Q<sub>2  </sub>[n] ^ ( Q<sub>1  </sub>[n] & !Q<sub>0  </sub>[n] &  Q<sub>h</sub> [n] )
  Q<sub>3  </sub>[n+1] =   Q<sub>3  </sub>[n] ^ ( Q<sub>2  </sub>[n] & !Q<sub>1  </sub>[n] & !Q<sub>0</sub> [n] & Q<sub>h</sub> [n] )
   <sub>   </sub>      …
  Q<sub>k-1</sub>[n+1] =   Q<sub>k-1</sub>[n] ^ ( Q<sub>k-2</sub>[n] & !Q<sub>k-3</sub>[n] & …  & !Q<sub>1</sub> [n] & !Q<sub>0</sub> [n] & Q<sub>h</sub> [n])
  Q<sub>k  </sub>[n+1] =   Q<sub>k  </sub>[n] ^ (!Q<sub>k-2</sub>[n] &   <sub>   </sub>      …  & !Q<sub>1</sub> [n] & !Q<sub>0</sub> [n] & Q<sub>h</sub> [n])

Der Unterschied zwischen den Formeln für das größte Bit Q<sub>k</sub> und den kleineren Bits Q<sub>k-1</sub> 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 / [[XOR-Verknüpfung|Antivalenz]]<br />
  ! := Inverter / NOT / [[Aussagenlogik#Verneinte Aussage – Negation|Negation]]<br />
  & := Und / AND / [[Aussagenlogik#Und-verknüpfte Aussagen – Konjunktion|Konjunktion]]

== Eigenschaften ==
Die [[Hamming-Distanz]] benachbarter Codewörter ist 1, d. h. die Werte unterscheiden sich in genau einem Bit. Das ist das höchstwertige Bit, das sich in der [[Binärdarstellung]] der mit 0 beginnenden Zeilennummern ändert. Zum Beispiel haben Zeile 11 und Zeile 12 die Binärdarstellungen 001011 und 001100. Es ändern sich also die letzten drei Bits. Die Codewörter von Zeile 11 und 12, nämlich 001110 und 001010, unterscheiden sich daher im drittletzten Bit.

Die absolute Differenz benachbarter Codewörter ist also eine [[Zweierpotenz]]. Diese Zweierpotenz ist die größte Zweierpotenz, durch die sich die Zeilennummer des zweiten Codeworts teilen lässt. Ist der größte ungerade [[Teilbarkeit|Teiler]] der Zeilennummer von der Form 4k&#8239;+&#8239;1, also 1, 5, 9, ..., dann ist die Differenz positiv. Ist der größte ungerade Teiler von der Form 4k&#8239;+&#8239;3, also 3, 7, 11, ..., dann ist die Differenz negativ. Zum Beispiel hat die Zeile 12 die Zahl 2<sup>2</sup> = 4 als größte Zweierpotenz und die Zahl 3 als größte ungerade Teiler. Die Differenz der Codewörter von Zeile 11 und Zeile 12 ist also gleich &minus;4.

== Bedeutung ==
Ein Ziffernschritt sei nachfolgend der kleinstmögliche Unterschied, die kleinste Differenz, das kleinste Intervall zwischen zwei digitalisierten Werten. Eine zeitliche Veränderung eines Zahlenwertes um einen Ziffernschritt wird nachfolgend als stetige Veränderung bezeichnet. Signale werden über Datenübertragungsstrecken übertragen. Typische Signalgeber sind z.&nbsp;B. Signale eines Temperatursensors oder eines [[Absolutwertgeber|Drehwinkelgebers]].

Die Motivation für die Entwicklung dieses Codes ist das folgende Problem: Signalübertragungsstrecken und Signalgeber unterliegen Störeinflüssen, die dazu führen können, dass sich einzelne oder mehrere Stellen eines Codewortes (codierte Zahl) unbeabsichtigterweise verändern oder falsch interpretiert werden können. Physische Schalter sind beispielsweise nicht ideal. Es ist sehr unwahrscheinlich, dass physische Schalter ihren Zustand exakt synchron ändern.

Auf mehreren Adern einer elektrischen Datenleitung sollen nun beispielsweise Daten parallel übertragen werden, die sich stetig ändern. 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:

{| border="0" cellpadding="5" align="right"
|-
|
{| width="45" cellpadding="5" border="1" style="border-collapse:collapse; line-height:100%"
|-
| align="center" | <small>2-Bit-<br>Gray-Code</small>
 00
 01
 11
 10
|-
| align="center" | <small>3-Bit-<br>Gray-Code</small>
 000
 001
 011
 010
 110
 111
 101
 100
|-
| align="center" | <small>4-Bit-<br>Gray-Code</small>
 0000
 0001
 0011
 0010
 0110
 0111
 0101
 0100
 1100
 1101
 1111
 1110
 1010
 1011
 1001
 1000
|-
| align="center" | <small>5-Bit-<br>Gray-Code</small>
 00000
 00001
 00011
 00010
 00110
 00111
 00101
 00100
 01100
 01101
 01111
 01110
 01010
 01011
 01001
 01000
 11000
 11001
 11011
 11010
 11110
 11111
 11101
 11100
 10100
 10101
 10111
 10110
 10010
 10011
 10001
 10000
|}
|
{| width="70" cellpadding="5" border="1" style="border-collapse:collapse; line-height:100%"
| align="center" | <small>6-Bit-<br>Gray-Code</small>
 <span style="color:#FF0000">0</span>00000
 00000<span style="color:#FF0000">1</span>
 0000<span style="color:#FF0000">1</span>1
 00001<span style="color:#FF0000">0</span>
 000<span style="color:#FF0000">1</span>10
 00011<span style="color:#FF0000">1</span>
 0001<span style="color:#FF0000">0</span>1
 00010<span style="color:#FF0000">0</span>
 00<span style="color:#FF0000">1</span>100
 00110<span style="color:#FF0000">1</span>
 0011<span style="color:#FF0000">1</span>1
 00111<span style="color:#FF0000">0</span>
 001<span style="color:#FF0000">0</span>10
 00101<span style="color:#FF0000">1</span>
 0010<span style="color:#FF0000">0</span>1
 00100<span style="color:#FF0000">0</span>
 0<span style="color:#FF0000">1</span>1000
 01100<span style="color:#FF0000">1</span>
 0110<span style="color:#FF0000">1</span>1
 01101<span style="color:#FF0000">0</span>
 011<span style="color:#FF0000">1</span>10
 01111<span style="color:#FF0000">1</span>
 0111<span style="color:#FF0000">0</span>1
 01110<span style="color:#FF0000">0</span>
 01<span style="color:#FF0000">0</span>100
 01010<span style="color:#FF0000">1</span>
 0101<span style="color:#FF0000">1</span>1
 01011<span style="color:#FF0000">0</span>
 010<span style="color:#FF0000">0</span>10
 01001<span style="color:#FF0000">1</span>
 0100<span style="color:#FF0000">0</span>1
 01000<span style="color:#FF0000">0</span>
 <span style="color:#FF0000">1</span>10000
 11000<span style="color:#FF0000">1</span>
 1100<span style="color:#FF0000">1</span>1
 11001<span style="color:#FF0000">0</span>
 110<span style="color:#FF0000">1</span>10
 11011<span style="color:#FF0000">1</span>
 1101<span style="color:#FF0000">0</span>1
 11010<span style="color:#FF0000">0</span>
 11<span style="color:#FF0000">1</span>100
 11110<span style="color:#FF0000">1</span>
 1111<span style="color:#FF0000">1</span>1
 11111<span style="color:#FF0000">0</span>
 111<span style="color:#FF0000">0</span>10
 11101<span style="color:#FF0000">1</span>
 1110<span style="color:#FF0000">0</span>1
 11100<span style="color:#FF0000">0</span>
 1<span style="color:#FF0000">0</span>1000
 10100<span style="color:#FF0000">1</span>
 1010<span style="color:#FF0000">1</span>1
 10101<span style="color:#FF0000">0</span>
 101<span style="color:#FF0000">1</span>10
 10111<span style="color:#FF0000">1</span>
 1011<span style="color:#FF0000">0</span>1
 10110<span style="color:#FF0000">0</span>
 10<span style="color:#FF0000">0</span>100
 10010<span style="color:#FF0000">1</span>
 1001<span style="color:#FF0000">1</span>1
 10011<span style="color:#FF0000">0</span>
 100<span style="color:#FF0000">0</span>10
 10001<span style="color:#FF0000">1</span>
 1000<span style="color:#FF0000">0</span>1
 10000<span style="color:#FF0000">0</span>
|}
|}

=== Problem bei Dualcode-Signalen ===
[[Datei:Dualcode-1.svg|400px|Dualcodesignal]]

Erklärung zu den Abbildungen:

Als steigende Flanke wird nachfolgend der Übergang vom Wert 0 („Aus“) auf 1 („Ein“) eines Signals auf einer Datenleitung bezeichnet. In der oberen Abbildung sind theoretische Dualcode ([[BCD-Code|BCD]]) Signale auf vier parallelen Leitungen dargestellt sowie reale Dualcode Signale in der Abbildung darunter wie sie in der Praxis auftreten können. Die realen Signale auf der Leitung 1 sind im Vergleich zu dem theoretischen Signal zeitlich verschoben. Die erste steigende Flanke des realen Signals auf Datenleitung 1 kommt hier im Vergleich zu dem theoretischen Signal um das Zeitintervall t<sub>2</sub>&minus;t<sub>1</sub> später am Ausgang an, während die zweite steigende Flanke um das Intervall t<sub>4</sub>&minus;t<sub>3</sub> früher am Ausgang anliegt. Die Signale „0“ und „1“ auf den Leitungen werden nachfolgend als Tetrade (vier-stelliges Codewort) geschrieben, wobei der Kanal 3 an der Stelle ganz links und der Kanal 0 an der Stelle ganz rechts notiert wird. Die dazugehörigen Werte, die theoretisch vor der Codierung bei dem Signalgeber vorhanden waren, lauten im Dezimalsystem: 0, 1, 2, 3, 4, 5, 6, 7 usw. Die Werte des Gebers ändern sich in diesem Beispiel also stetig, das heißt immer nur um das kleinstmögliche Intervall von 1, also ohne größere Sprünge zwischen zwei aufeinanderfolgenden Werten.

Während das theoretische Signal in der Reihenfolge
* {0000}, {0001}, {0010}, {0011}, {0100}, {0101}, {0110}, {0111} usw.

abgesendet wird, kommen am Ausgang des realen Signals kurzzeitig andere Signalzustände an:
* {0000}, {0001}, '''{0000}''', {0010}, {0011}, {0100}, {0101}, '''{0111}''', {0110}, {0111} usw.
Während sich der Dezimalwert des Gebers zwischen zwei aufeinanderfolgenden Werten theoretisch maximal um 1 ändert, entsteht hier auf der Empfängerseite verursacht durch einen Laufzeitfehler ein Sprung mit einem Betrag von 2 (dezimal) und zwar verursacht durch die Signalfolge {0000} und {0010}, die der Zahlenfolge 0 und 2 im Dezimalsystem entspricht. Ein weiterer Sprung um den Betrag von 2 (dezimal) entsteht durch die Signalfolge {0101} und {0111} (dezimal: 5 und 7). Der theoretisch richtige Dezimalwert des Gebers betrug 3 zwischen den Zeitpunkten t<sub>1</sub> und t<sub>2</sub>. Der Laufzeitfehler des realen Signals führt allerdings dazu, dass der Wert in diesem Intervall als 1 interpretiert wird. Der Betrag des Fehlers zwischen theoretischem und realem gestörten Signal beträgt also zwei, wie auch der Fehler zwischen den Zeitpunkten t<sub>3</sub> und t<sub>4</sub>.

=== Lösung mit Gray-Code ===
[[Datei:Graycodesignal.svg|400px|Graycodesignal]]

Die theoretischen Ausgangswerte des Signalgebers lauten wie oben im Dezimalsystem: 0, 1, 2, 3, 4, 5, 6, 7 usw. Die Dezimalwerte sind allerdings nun mithilfe des Gray-Codes codiert bzw. werden mithilfe des Gray-Codes gesendet. Zwischen zwei aufeinanderfolgenden Eingangswerten ändert sich dabei immer nur ein Bit (eine Stelle im Codewort):

* 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.

Die gestörte Tetrade zwischen den Zeitpunkten t<small>1</small> und t<small>2</small> lautet hier {0001}, die anstatt dem theoretischen Codewort {0011} empfangen worden ist, was im Dezimalsystem dem Empfang einer 1 anstatt der 2 entspricht. Die gestörte Tetrade zwischen den Zeitpunkten t<small>3</small> und t<small>4</small> lautet {0101}, anstatt dass {0111} empfangen worden ist. Das entspricht dezimal dem Empfang einer 6 anstatt 5.

Der Dezimalbetrag des Fehlers zwischen dem „wahren“ Wert des Gebers im Vergleich zu dem gestörten Signal entspricht bei Verwendung des Gray Codes also nur 1 und ist somit geringer als im oberen Beispiel, bei dem der Dezimalwert des Gebers BCD (dual) codiert wurde.

Abweichungen an einer oder wenigen Stellen eines Codewortes werden bei der Verwendung des Gray Codes also zwar nicht erkannt, resultieren aber nicht in gravierenden Abweichungen des ursprünglichen Eingangswertes. Die Verwendung des Gray Codes erlaubt auch keine Fehlerkorrektur.

=== 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.

{|
|
{| class="wikitable"
|+ Reihenfolge Dualcode
|-
!
! ¬X<sub>0</sub>
! X<sub>0</sub>
! X<sub>0</sub>
! ¬X<sub>0</sub>
!
|-
! ¬X<sub>2</sub>
| 0 || 1 || 3 || 2
! ¬X<sub>3</sub>
|-
! X<sub>2</sub>
| 4 || 5 || 7 || 6
! ¬X<sub>3</sub>
|-
! X<sub>2</sub>
| 12 || 13 || 15 || 14
! X<sub>3</sub>
|-
! ¬X<sub>2</sub>
| 8 || 9 || 11 || 10
! X<sub>3</sub>
|-
!
! ¬X<sub>1</sub>
! ¬X<sub>1</sub>
! X<sub>1</sub>
! X<sub>1</sub>
!
|}
|
{| class="wikitable"
|+ Reihenfolge Graycode
|-
!
! ¬X<sub>0</sub>
! X<sub>0</sub>
! X<sub>0</sub>
! ¬X<sub>0</sub>
!
|-
! ¬X<sub>2</sub>
| 0 || 1 || 2 || 3
! ¬X<sub>3</sub>
|-
! X<sub>2</sub>
| 7 || 6 || 5 || 4
! ¬X<sub>3</sub>
|-
! X<sub>2</sub>
| 8 || 9 || 10 || 11
! X<sub>3</sub>
|-
! ¬X<sub>2</sub>
| 15 || 14 || 13 || 12
! X<sub>3</sub>
|-
!
! ¬X<sub>1</sub>
! ¬X<sub>1</sub>
! X<sub>1</sub>
! X<sub>1</sub>
!
|}
|}

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 <math>n</math> im Gray-Code Zahlensystem ist <math>2^n-1</math> (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<sub>Gray</sub> = 7 &minus; (3 &minus; 1) = 5 oder 1111<sub>Gray</sub> = 15 &minus; (7 &minus; (3 &minus; 1)) = 10.
Stellen, die 0 sind, werden dabei ausgelassen, Beispiel: 101<sub>Gray</sub> = 7 &minus; 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.
<div style="clear:both;"></div>

== Programmierung ==
Folgendes Beispiel zeigt eine Implementierung in der [[Programmiersprache]] [[C++]], die die Zeilen des Gray-Codes mit 6 Bits [[Iterative Programmierung|iterativ]] erzeugt und auf der Konsole ausgibt.<ref>GeeksforGeeks: [https://www.geeksforgeeks.org/generate-n-bit-gray-codes/ Generate n-bit Gray Codes]</ref><ref>Rosetta Code: [https://rosettacode.org/wiki/Gray_code Gray code]</ref>
<syntaxhighlight lang="c++">
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void writeGrayCode (int const bits)           // Diese Funktion erzeugt den bits-Bit-Gray-Code und gibt ihn auf der Konsole aus
{
    vector<string> GrayCode {""};             // Ergebnis-Vektor mit initialer leerer Zeile

    // Diese for-Schleife wird bits-mal durchlaufen und erzeugt iterativ die Text für den 1-Bit-, 2-Bit-, ..., n-Bit-Gray-Code.
    // Die Schleifenvariable pos durchläuft die jeweiligen Bitpositionen 1, 2, 4, ..., 2^(n-1)
    for (int pos = 1; pos < (1 << bits); pos *= 2)
    {
        for (int i = pos; --i >= 0; )         // Hänge die zuletzt erzeugten Zeilen in umgekehrter Reihenfolge am Ende noch mal an.
            GrayCode.push_back (GrayCode[i]); // Die Anzahl der Zeilen verdoppelt sich dadurch.

        for (int i = 0*pos; i < 1*pos; i++)   // Füge eine '0' am Anfang der Zeilen der ersten Hälfte hinzu.
            GrayCode[i] = "0" + GrayCode[i];

        for (int i = 1*pos; i < 2*pos; i++)   // Füge eine '1' am Anfang der Zeilen der zweiten Hälfte hinzu.
            GrayCode[i] = "1" + GrayCode[i];
    }

    for (auto & E : GrayCode)                 // Diese for-Schleife durchläuft alle Zeilen des Gray-Code
        cout << E << endl;                    // Ausgabe auf der Konsole
}

int main()                                    // Eintrittspunkt beim Aufruf eines C++-Programms
{
    writeGrayCode(6); // Aufruf der Funktion, die hier den 6-Bit-Gray-Code erzeugt und auf der Konsole ausgibt
}
</syntaxhighlight>

=== Zwei- und mehrdimensionale Graycodes ===

In mehrdimensionalen Vektorräumen sind mehrdimensionale Graycodes möglich.
In <math>N</math>-dimensionalen Graycodes mit jeweils <math>n\geq4</math> Codeworten pro Dimension hat jedes Codewort <math>2N</math> Nachbarn in <math>2N</math> Richtungen, die sich um maximal 1 Bit unterscheiden.
In <math>N</math>-dimensionalen Graycodes mit jeweils <math>n=2</math> Codeworten pro Dimension hat jedes Codewort <math>N</math> Nachbarn in <math>2N</math> Richtungen (die entgegengesetzten Nachbarn sind die gleichen), die sich um maximal 1 Bit unterscheiden.

Genutzt werden diese in der Digitalen Kodierung, [[#Reduktion von Bitfehlern in digital PSK-, APSK- und QAM-modulierten Signalen|siehe hier]].

== Geometrische und graphentheoretische Darstellung ==

<gallery widths="165" heights="165">
Karnaugh map KV Nachbarschaft 1.svg|Bild 1: 3-Bit-Gray-Code als Ecken eines (3D-)Würfels
Karnaugh map KV Nachbarschaft 10.svg|Bild 2: Koordinatensystem hinzugefügt
</gallery>

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.

:{| class="wikitable float-right"
|+ 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
|}
<gallery widths="440" heights="300">
Karnaugh map KV Nachbarschaft 9.svg|Bild 3: Die 6 Pfade zu dem Gray-Code in der Tabelle. Es handelt sich um einen [[Hamiltonkreisproblem|Hamiltonkreis]]. '''Startpunkt:''' 000 (grüner Kreis jeweils hinten links oben), '''Verlauf:''' grüne→blaue→rote→schwarze Linie, '''Endpunkt:''' am Startpunkt<br>Fehler in Bild b) Linie 101→111 und in Bild d) 011→111
</gallery>

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 12 Möglichkeiten (jeder Weg vorwärts und rückwärts), 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 [[Hamiltonkreisproblem|Hamiltonkreise]] auf einem n-dimensionalen [[Hyperwürfel]] gibt. Die Anzahl dieser Hyperwürfel ist in der [[On-Line Encyclopedia of Integer Sequences]] als Sequenz [[OEIS:A003042|A003042]] angegeben und (Stand Februar 2022) bis zu 6 Dimensionen bekannt.<ref>[https://oeis.org/A003042 A003042: Number of directed Hamiltonian cycles (or Gray codes) on n-cube. (Formerly M2053)]</ref>

Für 1 bit gibt es 1 möglichen Gray-Code, für 2 bit gibt es 2 mögliche Gray-Codes und für 3 bit gibt es 12 mögliche Gray-Codes:

:{| style="line-height:99%; background:#F0F0F0; font-family:courier; font-weight:900"
|style="background:white;color:blue;width:60px"|Nr.&nbsp;1||0||1
|}
:{| style="line-height:99%; background:#F5F5F5; font-family:courier; font-weight:900"
|style="background:white;color:blue;width:60px"|Nr.&nbsp;1||00||01||11||10
|-
|style="background:white;color:blue;width:60px"|Nr.&nbsp;2||00||10||11||01
|}
:{| style="line-height:99%; background:#FAFAFA; font-family:courier; font-weight:900"
|style="background:white;color:blue;width:60px"|Nr.&nbsp;1||000||001||011||010||110||111||101||100
|-
|style="background:white;color:blue;width:60px"|Nr.&nbsp;2||000||001||011||111||101||100||110||010
|-
|style="background:white;color:blue;width:60px"|Nr.&nbsp;3||000||001||101||100||110||111||011||010
|-
|style="background:white;color:blue;width:60px"|Nr.&nbsp;4||000||001||101||111||011||010||110||100
|-
|style="background:white;color:blue;width:60px"|Nr.&nbsp;5||000||010||011||001||101||111||110||100
|-
|style="background:white;color:blue;width:60px"|Nr.&nbsp;6||000||010||011||111||110||100||101||001
|-
|style="background:white;color:blue;width:60px"|Nr.&nbsp;7||000||010||110||111||011||001||101||100
|-
|style="background:white;color:blue;width:60px"|Nr.&nbsp;8||000||010||110||100||101||111||011||001
|-
|style="background:white;color:blue;width:60px"|Nr.&nbsp;9||000||100||101||111||110||010||011||001
|-
|style="background:white;color:blue;width:60px"|Nr. 10||000||100||101||001||011||111||110||010
|-
|style="background:white;color:blue;width:60px"|Nr. 11||000||100||110||111||101||001||011||010
|-
|style="background:white;color:blue;width:60px"|Nr. 12||000||100||110||010||011||111||101||001
|}

Darüber steigt die Zahl steil an:<br>
Für 4 bit sind es 2688, für 5 bit 1813091520 und für 6 bit 71676427445141767741440.

== Balancierte Gray-Codes ==
<!-- unverständlich, wahrscheinlich unverstanden aus einem Mathebuch abgetippt, wie wäre es mit einem Beispiel eines balancierten und eines unbalancierten Codes? -->
Ein balancierter Gray-Code ist ein Gray-Code, bei dem sich die Anzahl der Änderungen für alle <math>n</math> Bits höchstens um 2 unterscheidet. Wenn <math>TC(i)</math> und <math>TC(j)</math> die Anzahl der Änderungen für die Bits mit den Indizes <math>i</math> und <math>j</math> ist, dann gilt für jeden balancierten Gray-Code die [[Ungleichung]] <math>|TC(i) - TC(j)| \leq 2</math>.

Ein balancierter Gray-Code mit <math>n</math> Bits kann folgendermaßen konstruiert werden:

* Aus einem beliebigen <math>(n - 2)</math>-Bit Gray-Code mit den Zeilen <math>s = (s_1, s_2, \ldots, s_{2^{n - 2}})</math> wird eine [[Teilfolge]] <math>t = (t_1, t_2, \ldots, t_l)</math> ausgewählt, wobei <math>l</math> gerade ist und <math>t_1</math>, <math>t_2</math> und <math>t_{l - 1}</math>, <math>t_l</math>  direkt aufeinanderfolgende Zeilen sind.
* Die vier Kopien des <math>(n - 2)</math>-Würfels. In jedem dieser Würfel betrachtet man den definierten Gray-Code mit den Zeilen <math>s = s^{(00)} = s^{(01)} = s^{(11)} = s^{(10)}</math> und löscht die Übergänge zwischen direkt aufeinanderfolgenden Zeilen auf folgende Weise: Aus <math>s^{(00)}</math> werden die entsprechenden Elemente von den Zeilen mit ungeraden Indexen <math>t_1, t_3, \ldots, t_{l - 1}</math> gelöscht. Aus <math>s^{(01)}</math> werden die entsprechenden Elemente von <math>t_2, t_3, \ldots, t_l</math> gelöscht. Aus <math>s^{(11)}</math> werden die entsprechenden Elemente von den Zeilen mit geraden Indexen <math>t_2, t_4, \ldots, t_l</math> gelöscht. Aus <math>s^{(10)}</math> wird nur das entsprechenden Elemente von <math>t_1</math> gelöscht.
* Die vier Teilwürfel werden miteinander verbunden.

Es kann überprüft werden, dass die oben beschriebene Konstruktion tatsächlich einen balancierten <math>n</math>-Bit-Gray-Code ergibt. Die Verteilung der Anzahl der Änderungen für die Bits in diesem Code hängt von der Wahl der ausgewählten [[Teilfolge]] <math>t</math> ab.<ref>Girish S. Bhat, Carla D. Savage, North Carolina State University: [https://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i1r25/pdf Balanced Gray Codes]</ref>

== Anwendungen ==
[[Datei:BCD-Scheibe.svg|miniatur|Schemazeichnung einer Scheibe mit Gray-Codierung. Die gelben Punkte stellen Lichtsensoren dar.]]
[[Datei:Gray code rotary encoder 13-track opened.jpg|miniatur|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 Balken werden mit Lichtschranken oder anderen Sensoren abgetastet. Diese Position wird dann zur Winkel- oder Drehgeschwindigkeitsmessung verwendet.<ref name="doran2007-S">{{Literatur |Autor=Robert W. Doran |Titel=The Gray Code |Datum=2007 |Sammelwerk=Journal of Universal Computer Science |Band=13 |Nummer=11 |Seiten=1575, 1577}}</ref>

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 [[Korrelator]]en 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.

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 [[Chinesische Ringe|Chinesischen Ringe]].

=== Reduktion von Bitfehlern in digital PSK-, APSK- und QAM-modulierten Signalen ===

In moderner [[Digitale Kommunikation]] spielen 1D- and 2D-Gray-Codierungen eine bedeutende Rolle beim Verhindern von Mehrfachbitfehlern bei Übertragungen. Sie machen damit  [[Fehlerkorrektur]]-Verfahren effizienter. Sie finden Verwendung bei allen PSK-Modulationen wie auch bei geradzahligen (2<sup>2n</sup>) QAM-Modulationen. Benachbarte, durch Rauschen sehr wahrscheinlich auftretende fehlerhafte Codeworte unterscheiden sich nur um 1 Bit. Nicht perfekt lassen sie sich umsetzen bei APSK-Modulationen (z.&nbsp;B. APSK-16 und APSK-32) und bei ungeradzahligen (2<sup>2n+1</sup>) QAM-Modulationen.

<gallery heights="120" mode="packed" style="text-align:left">
 QPSK Gray Coded.svg|Codes 4-PSK
 8PSK Gray Coded.svg|Codes 8-PSK
 16QAM Gray Coded.svg|Codes 16-QAM
</gallery>

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

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: <math>31_{10} - (15_{10} - 3_{10}) = 19</math>

== Gray-Code zurückrechnen ==
Eine Zeile des Gray-Codes kann in die Zeilennummer zurückgerechnet werden, indem alle Bits vom höchstwertigen Bit bis zum aktuellen Bit mit einem [[Exklusives Oder|exklusiven Oder]] verknüpft werden. Dazu werden die Bits der Zeile mit jedem [[Iteration]]sschritt jeweils um 1 Bit nach rechts [[Logische Verschiebung|verschoben]] und mit dem Zwischenergebnis mit einem exklusiven Oder verknüpft.<ref>Lénárd Szolnoki's programming site: [https://leni536.github.io/2019/09/26/Gray_encode_decode.html Implementations for Gray code encoding and decoding]</ref>

Das folgende Beispiel zeigt die Implementierung einer Funktion, die die Zeile eines (beliebigen n-Bit) binären reflektierten Gray-Codes decodiert:
<syntaxhighlight lang="c++">
int GrayDecode (int const CodeWort)
{
    int res  = CodeWort;
    int mask = CodeWort;  // Die Bitmaske ist der Gray-Code res mit einer Rechtsverschiebung der Bits

    while (mask)          // Solange nicht alle gesetzten Bits nach rechts verschoben sind und der Wert ungleich 0 ist ...
    {
        mask >>= 1;       // Rechtsverschiebung um 1 Bit
        res  ^= mask;     // Exklusives Oder mit der Bitmaske
    }
    return res;
}
</syntaxhighlight>

== Spezielle Gray-Codes ==
=== Gray-Codes mit m bits und Länge kleiner als 2<sup>m</sup> ===
Es existieren auch Gray-Codes mit <math>m</math> Bits mit einer Länge von weniger als <math>2^m</math>. 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<ref>{{Cite web|url=https://www.eetimes.com/how-to-generate-gray-codes-for-non-power-of-2-sequences/|title=How to generate Gray Codes for non-power-of-2 sequences|date=2007-06-29|access-date=2023-02-25|last=Maxfield|first=Max|language=en}}</ref>. Die [[OEIS]]-Folge A290772<ref>[https://oeis.org/A290772 A290772: Number of cyclic Gray codes of length 2n which include all-0 bit sequence and use the least possible number of bits.]</ref> zählt die Anzahl der möglichen Gray-Codes der Länge <math>2 n</math> auf, wofür jeweils die minimale Anzahl von Bits verwendet werden.

=== Excess-Gray-Code ===
Wird aus einem Gray-Code ein Ausschnitt herausgetrennt, beispielsweise die letzten 3 Bit eines 4-Bit-Gray-Codes, so erhält man einen sogenannten Excess-Gray-Code. Dieser Code zeichnet sich dadurch aus, dass die betroffenen, herausgetrennten Bits bei weiterem Hochzählen des originalen Codewortes rückwärts zählen. Dies ist dadurch bedingt, dass bei einer Gray-Codierung kein Überlauf bei der höchsten Zahl entsteht, wie man ihn aus dem klassischen [[Dualsystem|Binärsystem]] kennt.<ref>AutomationDirect: [https://support.automationdirect.com/notes/encoder_graycode.html What are Excess Gray Codes?]</ref>

'''Beispiel''': Die höchste mit einem 3-Bit-Gray-Code codierte Zahl, also 7, wird als (0)100 repräsentiert. Weiteres Addieren einer 1 resultiert in einer 8, im Gray-Code 1100. Die letzten 3 Bit erfahren keinen Überlauf und verhalten sich bei weiterem Hochzählen genau entgegengesetzt zur ursprünglichen Zählrichtung.

Bei [[Sensor]]en, die mehrere Werte seriell als Gray-codierte Werte ausgeben, sollte daher darauf geachtet werden, ob es sich um einen zusammengesetzten Gray-Code oder um separate Codeworte handelt, da die ausgegebenen Werte sonst den Anschein erwecken, der Sensor würde rückwärts zählen.

== 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<!-- Datum Patent, Einführung 1878, unklare Quellen geben für den Code das Jahr 1870 an --> für die elektrische [[Telegrafie]]. Er erhielt für seine Arbeit die Auszeichnung der französischen [[Ehrenlegion]].

Namensgebend war allerdings [[Frank Gray (Physiker)|Frank Gray]], Forscher in den [[Bell Laboratories]], der den schon 1941 von [[George Stibitz]] beschriebenen Code<ref name="US2307868">{{Patent| Land=US| V-Nr=2307868A| A-Datum=1941-11-26| V-Datum=1943-01-12| Titel=Binary counter| Anmelder=Bell Telephone Labor Inc| Erfinder=George R. Stibitz}}</ref> 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.<ref name="US2632058" />

== Ähnliche Codes ==
* [[1-aus-10-Code]]
* [[Aiken-Code]]
* [[BCD-Code]]
* [[Gillham-Code]]
* [[Libaw-Craig-Code]]
* [[Stibitz-Code]]

== Literatur ==
* {{Literatur |Autor=Robert W. Doran |Titel=The Gray Code |Datum=2007 |Sammelwerk=Journal of Universal Computer Science |Band=13 |Nummer=11 |Seiten=1573-1597 |Online=http://educypedia.karadimov.info/library/jucs_13_11_1573_1597_doran.pdf |Format=PDF |KBytes=219}}

== Weblinks ==
{{Commonscat|Gray code}}
* {{Webarchiv|url=http://etc.manuel-breitfeld.de/gray-code-java-implementierung.html | wayback=20070930040812| text=Java-Beispiel für die Umwandlung einer Dezimalzahl in Gray-Code Darstellung}}
* [http://combos.org/bits Algorithmen zur Erzeugung des reflektierten Gray-Codes] auf dem [http://combos.org Combinatorial Object Server]

== Einzelnachweise ==
<references />

[[Kategorie:Binärcode]]
[[Kategorie:Kodierungstheorie]]