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, welche leichter zu merken und anzuwenden ist, besteht aus folgenden Schritten:EE Times: Gray Code Fundamentals – Part 2 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. 2. 3. 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:
Generatormatrix Da der Gray-Code ein linearer Code ist, kann man ihn mit einer Generatormatrix erzeugen. Ein binäres Wort der Länge kann man als Vektor eines -dimensionalen -Vektorraums betrachten. Sei nun ein Zeilenvektor, dann lässt sich die Kodierung des Wortes in das Codewort wie folgt darstellen:
Die Dekodierung erfolgt mit der Multiplikation der Inversen von . Diese hat folgende Form:
Der Vektorraum 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.
Qh [n+1] = !Qh [n] Qh [0 ] = 0 wenn der Gray-Code-Zähler mit Null startet also Q=0, oder Q eine gerade Anzahl an Einsen hat. Bei anderer Initialisierung würde der Zähler rückwärts laufen.
Damit wird die Kombinatorik recht übersichtlich:
Q0 [n+1] = !(Q0 [n] ^ Qh [n] ) Q1 [n+1] = Q1 [n] ^ ( Q0 [n] & Qh [n] ) Q2 [n+1] = Q2 [n] ^ ( Q1 [n] & !Q0 [n] & Qh [n] ) Q3 [n+1] = Q3 [n] ^ ( Q2 [n] & !Q1 [n] & !Q0 [n] & Qh [n] ) … Qk-1[n+1] = Qk-1[n] ^ ( Qk-2[n] & !Qk-3[n] & … & !Q1 [n] & !Q0 [n] & Qh [n]) Qk [n+1] = Qk [n] ^ (!Qk-2[n] & … & !Q1 [n] & !Q0 [n] & Qh [n])
Der Unterschied zwischen den Formeln für das größte Bit Qk und den kleineren Bits Qk-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
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 22 = 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 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) 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 t2−t1 später am Ausgang an, während die zweite steigende Flanke um das Intervall t4−t3 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 t1 und t2. 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 t3 und t4.
Lösung mit Gray-Code 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 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