Gray code

Gray code
Eigenschaften
Hamming-Distanz 1
Stetig ja

Der Gray-Code (nach dem Physiker Frank Gray) ist ein stetiger Code, bei dem sich benachbarte Codewörter nur in einer einzigen dualen Ziffer unterscheiden. Die Hamming-Distanz aller benachbarter Codewörter ist somit 1. Dadurch verringert sich der maximal mögliche Ablesefehler bei der Quantisierung aus einem Analogsignal auf einen Code. Er dient als Kodierungsverfahren zur robusten Übertragung digitaler Größen über analoge Signalwege. Meistens ist er als Binärcode ausgeführt, kann aber auch für mehrstufige Übertragungswege benutzt werden.

Inhaltsverzeichnis

Generierung aus Binärcode

Die folgenden Punkte zeigen, wie man Schritt für Schritt aus einer binär codierten Dezimalzahl (Binärcode) eine Gray-codierte Binärzahl erhält:

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

Das gleiche als Programmcode:

  • Binärcode X1 --> Graycode: X4 = ((X1*2) XOR X1) / 2

Beispiel:

  • Man möchte die Zahl X1 = 1210 = 11002 (Binärcode) in den Graycode konvertieren:
  • Der Links-Shift um 1 Bit liefert X2 = 110002;
  • mit der Modulo-2-Addition(Binäre Addition ohne Übertrag) berechnet man X3 = X1 ⊕ X2 = 11002 ⊕ 110002 = 101002 und
  • nach dem Rechts-Shift erhält man nun die Zahl im Gray-Code: X4 = 10102.

Ein einfacherer Weg wäre folgender:

  • 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 Programmcode:

  • Binärcode X1 --> Graycode: X3 = (X1 XOR (X1/2))

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 hinzu zu nehmen, das mit jedem Taktzyklus toggelt.

Qh [n+1] = !Qh [n]

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] = Q1 [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] & !Qk-3 [n] & ... & !Q1 [n] & !Q0 [n] & Qh [n] )

^ := XOR / Exklusiv Oder / Antivalenz
! := Inverter / Not / Negation
& := Und / And /Konjunktion"


Bedeutung

Ausgangspunkt für diesen Code ist das folgende Problem: Auf mehreren Adern einer elektrischen Datenleitung sollen Daten parallel übertragen werden, die sich stetig (also nicht sprunghaft) ändern, z. B. Signale eines Temperatursensors in einem Ofen. Theoretisch ändern sich die Bits bei einem neuen Messwert auf jeder betroffenen Leitung 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:

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

Dualcodesignal

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

Graycodesignal

Um das zu vermeiden, werden mittels Gray-Code Steuersignalzustände in einer Sequenz abgesendet, bei denen 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 die gleiche Sequenz wie am Eingang an.

Karnaugh-Veitch-Diagramm

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

Reihenfolge bei Dualcode
  ¬X0 X0 X0 ¬X0  
¬X2 0 1 3 2 ¬X3
X2 4 5 7 6 ¬X3
X2 12 13 15 14 X3
¬X2 8 9 11 10 X3
  ¬X1 ¬X1 X1 X1  
Reihenfolge bei Graycode
  ¬X0 X0 X0 ¬X0  
¬X2 0 1 2 3 ¬X3
X2 7 6 5 4 ¬X3
X2 8 9 10 11 X3
¬X2 15 14 13 12 X3
  ¬X1 ¬X1 X1 X1  

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 2n − 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: 111Gray = 7 - (3 - 1) = 5 oder 1111Gray = 15- (7 - (3 - 1)) = 10. Stellen, die 0 sind, werden dabei ausgelassen, Beispiel: 101Gray = 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.

Hyperwürfel

Bild 1: Hyperwürfel
Bild 2: Hyperwürfel mit Koordinatensystem

Bild 1 zeigt den Hyperwürfel für 3 Variablen und Bild 2 den gleichen Würfel mit dazugehörigem Koordinatensystem. Die Knoten (Eckpunkt oder Kreise) am Hyper-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 Hyperwü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.

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


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

Da der hier dargestellt Gray-Code zyklisch ist, wurde in dieser Tabelle der Code in den Spalten c), d) und f) um eine Stelle nach oben verschoben (im Vergleich zur Tabelle weiter oben), so dass jeweils die drei Nullen in der letzten Tabellenzeile stehen. So ist erkennbar, dass es sich bei dem Gray-Code in Spalte a) nur um eine spiegelbildliche Umkehrung der Spalte c) handelt. Genauso ist Spalte b) die Umkehrung von Spalte d), während Spalte e) die Umkehrung von Spalte f) ist. Es gibt drei ungerichtete Hamiltonkreise am dreidimensionalen Hyperwürfel, die hier lediglich in unterschiedlicher Richtung (gerichteter Hamiltonkreis) dargestellt wurden.
Zur besseren Veranschaulichung sind hier nochmals die Codetafeln für die 6 Varianten des 3-Bit-Graycodes dargestellt. Wobei die Variante e den binäre reflektierte Gray-Code darstellt, der meist gemeint ist, wenn vom Gray-Code die Rede ist. Die 6 Versionen kan man auch durch Permutation der 3 Spalten der Codetafel erzeugen. Daraus ergibt sich, dass es bei n Bit n! Versionen gibt. Also für 3 Bit 3!= 6 Versionen des 3-Bit-Graycodes..

3 Bit: a
3 Bit: b
3 Bit: c
3 Bit: d
3 Bit: e
3 Bit: f


Bild 4
... usw. ...

Den 4-Bit-Gray-Code kann man aus dem Hyperwürfel in Bild 4 ablesen. Für 4 Bit gibt es 4! = 24 verschiedene Gray-Codes.

Anwendungen

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

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.

Beispiel

Die Dezimalzahl 410 = 1002 entspricht dem Gray-Code 610 = 1102. 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 710 = 1112 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: 3110 − (1510 − 310) = 19

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. Der Franzose Jean-Maurice-Émile Baudot verwendete Gray-Codes bereits im Jahr 1887 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 Code erst 1946 für seine Zwecke wiederentdeckte. Unter dem Titel Pulse Code Communications wurde am 17. März 1953 unter der US-Patentnummer 2,632,058 ein Patent für eine Gray-Kodierende Elektronenröhre erteilt.

Siehe auch

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Gray-Code — stetig ja Hamming Abstand 1 Der Gray Code ist ein stetiger Code, bei dem sich benachbarte Codewörter nur in einer einzigen dualen Ziffer unterscheiden. Die Hamming Distanz aller benachbarter Codewörter ist somit 1. Dadurch verringert sich der… …   Deutsch Wikipedia

  • Gray-Code —   [ greɪ koːt; nach dem amerikanischen Physiker Frank Gray, ✝ 1969], ein v. a. als Binärcode verwendeter Code zur Codierung der natürlichen Zahlen. Der Gray Code ist so aufgebaut, dass sich beim Übergang von einer Zahl zur benachbarten immer nur… …   Universal-Lexikon

  • Gray code — Gray kodas statusas T sritis automatika atitikmenys: angl. Gray code vok. Gray Code, m rus. код Грея, m pranc. code de Gray, m ryšiai: sinonimas – Grėjaus kodas …   Automatikos terminų žodynas

  • Gray-Code — Gray kodas statusas T sritis automatika atitikmenys: angl. Gray code vok. Gray Code, m rus. код Грея, m pranc. code de Gray, m ryšiai: sinonimas – Grėjaus kodas …   Automatikos terminų žodynas

  • Gray code — /grā kōd/ (computing) noun A type of code for modifying binary numbers (also reflective binary code) ORIGIN: Frank Gray (1887–1969), American physicist * * * n. a numerical code used in computing in which consecutive integers are represented by… …   Useful english dictionary

  • Gray code — The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one digit.The reflected binary code was originally designed to prevent spurious output from… …   Wikipedia

  • Gray code — noun A binary (ie. 1 s and 0 s) coding system in which successive values differ in just one digit position …   Wiktionary

  • Gray (Haute-Saone) — Gray (Haute Saône) Gray Le pont de pierres sur la Saône Administration Pays France Région Franche Comté Département …   Wikipédia en Français

  • Gray (haute-saône) — Gray Le pont de pierres sur la Saône Administration Pays France Région Franche Comté Département …   Wikipédia en Français

  • code de Gray — Gray kodas statusas T sritis automatika atitikmenys: angl. Gray code vok. Gray Code, m rus. код Грея, m pranc. code de Gray, m ryšiai: sinonimas – Grėjaus kodas …   Automatikos terminų žodynas

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”