# Gray-Code

Der Gray-Code ist eine spezielle Art der 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 digitalen Signalen, die sich schnell ändern. So können unterschiedliche Laufzeiten in mehradrigen Kabeln keinen Einfluss auf die Datenübertragung haben.
Der Gray-Code wurde ursprünglich für elektromechanische Sensoren und Schalter entwickelt, die anfällig für Fehler sind. Heute wird dieser Code auch in modernen digitalen Übertragungssystemen eingesetzt, wie zum Beispiel im digitalen Fernsehen (DVB-T) und im Kabelfernsehen. Der Code ist nach dem US-amerikanischen Physiker Frank Gray benannt, der 1953 das Patent für dieses Verfahren erhielt.

## 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, die leichter zu merken und anzuwenden ist, besteht aus folgenden Schritten:
* Beginne mit dem einfachsten Gray-Code-Werten: 0 und 1.
* Ergänze die Codefolge mit den gespiegelten vorhandenen Werten (schreibe sie in umgekehrter Reihenfolge auf).
* 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.
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.
Der Gray-Code wird hauptsächlich als Binärcode verwendet, kann jedoch auch für mehrstufige Ü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:
    $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.

### 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.
Damit wird die Kombinatorik recht übersichtlich:
Der Unterschied zwischen den Formeln 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.

## 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 Teiler der Zeilennummer von der Form 4k + 1, also 1, 5, 9, ..., dann ist die Differenz positiv. Ist der größte ungerade Teiler von der Form 4k + 3, also 3, 7, 11, ..., dann ist die Differenz negativ. Zum Beispiel hat die Zeile 12 die Zahl 2$^2$ = 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 −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. B. Signale eines Temperatursensors oder eines 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:
* 2-Bit- Gray-Code
* 00
* 01
* 11
* 10
* 3-Bit- Gray-Code
* 000
* 001
* 011
* 010
* 110
* 111
* 101
* 100
* 4-Bit- Gray-Code
* 0000
* 0001
* 0011
* 0010
* 0110
* 0111
* 0101
* 0100
* 1100
* 1101
* 1111
* 1110
* 1010
* 1011
* 1001
* 1000
* 5-Bit- Gray-Code
* 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
* 6-Bit- Gray-Code
* 000000
* 000001
* 000011
* 000010
* 000110
* 000111
* 000101
* 000100
* 001100
* 001101
* 001111
* 001110
* 001010
* 001011
* 001001
* 001000
* 011000
* 011001
* 011011
* 011010
* 011110
* 011111
* 011101
* 011100
* 010100
* 010101
* 010111
* 010110
* 010010
* 010011
* 010001
* 010000
* 110000
* 110001
* 110011
* 110010
* 110110
* 110111
* 110101
* 110100
* 111100
* 111101
* 111111
* 111110
* 111010
* 111011
* 111001
* 111000
* 101000
* 101001
* 101011
* 101010
* 101110
* 101111
* 101101
* 101100
* 100100
* 100101
* 100111
* 100110
* 100010
* 100011
* 100001
* 100000

### Problem bei Dualcode-Signalen

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) 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$_2$−t$_1$ später am Ausgang an, während die zweite steigende Flanke um das Intervall t$_4$−t$_3$ 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$_1$ und t$_2$. 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$_3$ und t$_4$.

### Lösung mit Gray-Code

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 t1 und t2 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 t3 und t4 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.
Reihenfolge Dualcode :
| | ¬X$_0$ | X$_0$ | X$_0$ | ¬X$_0$ | |
| ¬X$_2$ | 0 | 1 | 3 | 2 | ¬X$_3$ |
| X$_2$ | 4 | 5 | 7 | 6 | ¬X$_3$ |
| X$_2$ | 12 | 13 | 15 | 14 | X$_3$ |
| ¬X$_2$ | 8 | 9 | 11 | 10 | X$_3$ |
| | ¬X$_1$ | ¬X$_1$ | X$_1$ | X$_1$ | |
Reihenfolge Graycode :
| | ¬X$_0$ | X$_0$ | X$_0$ | ¬X$_0$ | |
| ¬X$_2$ | 0 | 1 | 2 | 3 | ¬X$_3$ |
| X$_2$ | 7 | 6 | 5 | 4 | ¬X$_3$ |
| X$_2$ | 8 | 9 | 10 | 11 | X$_3$ |
| ¬X$_2$ | 15 | 14 | 13 | 12 | X$_3$ |
| | ¬X$_1$ | ¬X$_1$ | X$_1$ | X$_1$ | |
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.

## Programmierung

Folgendes Beispiel zeigt eine Implementierung in der Programmiersprache C++, die die Zeilen des Gray-Codes mit 6 Bits iterativ erzeugt und auf der Konsole ausgibt.

### Zwei- und mehrdimensionale Graycodes

In mehrdimensionen Vektorräumen sind mehrdimensionale Graycodes möglich. In $N$-dimensionalen Graycodes mit jeweils $n\geq 4$ Codeworten pro Dimension hat jedes Codewort $2N$ Nachbarn in $2N$ Richtungen, die sich um maximal 1 Bit unterscheiden. In $N$-dimensionalen Graycodes mit jeweils $n=2$ Codeworten pro Dimension hat jedes Codewort $N$ Nachbarn in $2N$ Richtungen (die entgegengesetzten Nachbarn sind die gleichen), die sich um maximal 1 Bit unterscheiden.
Genutzt werden diese in der Digitalen Kodierung, siehe hier.

## Geometrische und graphentheoretische Darstellung

* Bild 1: 3-Bit-Gray-Code als Ecken eines (3D-)Würfels
* Bild 2: Koordinatensystem hinzugefügt
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) 000000000000000000 001100010010001100 101101110011011110 100001100001010010 110011101101110011 111111111111111111 011110011110101101 010010001100100001
* Bild 3: Die 6 Pfade zu dem Gray-Code in der Tabelle. Es handelt sich um einen Hamiltonkreis. Startpunkt: 000 (grüner Kreis jeweils hinten links oben), Verlauf: grüne→blaue→rote→schwarze Linie, Endpunkt: am Startpunkt Fehler in Bild b) Linie 101→111 und in Bild d) 011→111
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.
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:
    Nr. 101
    Nr. 100011110 Nr. 200101101
    Nr. 1000001011010110111101100 Nr. 2000001011111101100110010 Nr. 3000001101100110111011010 Nr. 4000001101111011010110100 Nr. 5000010011001101111110100 Nr. 6000010011111110100101001 Nr. 7000010110111011001101100 Nr. 8000010110100101111011001 Nr. 9000100101111110010011001 Nr. 10000100101001011111110010 Nr. 11000100110111101001011010 Nr. 12000100110010011111101001
Darüber steigt die Zahl steil an: Für 4 bit sind es 2688, für 5 bit 1813091520 und für 6 bit 71676427445141767741440.

## Balancierte Gray-Codes

Ein balancierter Gray-Code ist ein Gray-Code, bei dem sich die Anzahl der Änderungen für alle $n$ Bits höchstens um 2 unterscheidet. Wenn $TC(i)$ und $TC(j)$ die Anzahl der Änderungen für die Bits mit den Indexen $i$ und $j$ ist, dann gilt für jeden balancierten Gray-Code die Ungleichung $|TC(i)-TC(j)|\leq 2$.
Ein balancierter Gray-Code mit $n$ Bits kann folgendermaßen konstruiert werden:
* Aus einem beliebigen $(n-2)$-Bit Gray-Code mit den Zeilen $s=(s_{1},s_{2},\ldots ,s_{2^{n-2}})$ wird eine Teilfolge $t=(t_{1},t_{2},\ldots ,t_{l})$ ausgewählt, wobei $l$ gerade ist und $t_{1}$, $t_{2}$ und $t_{l-1}$, $t_{l}$ direkt aufeinanderfolgende Zeilen sind.
* Die vier Kopien des $(n-2)$-Würfels. In jedem dieser Würfel betrachtet man den definierten Gray-Code mit den Zeilen $s=s^{(00)}=s^{(01)}=s^{(11)}=s^{(10)}$ und löscht die Übergänge zwischen direkt aufeinanderfolgenden Zeilen auf folgende Weise: Aus $s^{(00)}$ werden die entsprechenden Elemente von den Zeilen mit ungeraden Indexen $t_{1},t_{3},\ldots ,t_{l-1}$ gelöscht. Aus $s^{(01)}$ werden die entsprechenden Elemente von $t_{2},t_{3},\ldots ,t_{l}$ gelöscht. Aus $s^{(11)}$ werden die entsprechenden Elemente von den Zeilen mit geraden Indexen $t_{2},t_{4},\ldots ,t_{l}$ gelöscht. Aus $s^{(10)}$ wird nur das entsprechenden Elemente von $t_{1}$ gelöscht.
* Die vier Teilwürfel werden miteinander verbunden.
Es kann überprüft werden, dass die oben beschriebene Konstruktion tatsächlich einen balancierten $n$-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 $t$ ab.

## Anwendungen

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

### 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$^{2n}$) 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. B. APSK-16 und APSK-32) und bei ungeradzahligen (2$^{2n+1}$) QAM-Modulationen.
* Codes 4-PSK
* Codes 8-PSK
* Codes 16-QAM

## 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$

## 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 exklusiven Oder verknüpft werden. Dazu werden die Bits der Zeile mit jedem Iterationsschritt jeweils um 1 Bit nach rechts verschoben und mit dem Zwischenergebnis mit einem exklusiven Oder verknüpft.
Das folgende Beispiel zeigt die Implementierung einer Funktion, die die Zeile eines (beliebigen n-Bit) binären reflektierten Gray-Codes decodiert:

## 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. Die OEIS-Folge A290772 zählt die Anzahl der möglichen Gray-Codes der Länge $2n$ 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 Binärsystem kennt.
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 Sensoren, 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 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 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.

## Ähnliche Codes

* 1-aus-10-Code
* Aiken-Code
* BCD-Code
* Gillham-Code
* Libaw-Craig-Code
* Stibitz-Code