Gray-Code

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Der Gray-Code (nach dem Physiker Frank Gray) ist eine symmetrische Art einen Code zu generieren, bei dem sich benachbarte Zahlen nur in einer einzigen dualen Ziffer unterscheiden. 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. Eine wesentliche Eigenschaft ist, dass sich die Gray-Codes für zwei benachbarte Zahlen nur um 1 Ziffer, bei Binärcode also 1 Bit, unterscheiden (Hamming-Distanz). Dadurch verringert sich der maximal mögliche Ablesefehler bei der Quantisierung aus einem Analogsignal auf einen Code.

Inhaltsverzeichnis

1 Generierung
- 1.1 aus Binärcode
- 1.2 direkt als Gray-Zähler
2 Bedeutung
3 Anwendungen
4 Beispiel
5 Geschichte
6 Siehe auch
7 Weblinks

[Bearbeiten] Generierung

[Bearbeiten] 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 von X1 und X2
X4: Rechts-Shift der Dualzahl um 1 Bit; dies ist die gewünschte Zahl im Graycode.

Beispiel:

Man möchte die Zahl X1 = 12₁₀ = 1100₂ (Binärcode) in den Graycode konvertieren:
Der Links-Shift um 1 Bit liefert X2 = 11000₂;
mit der Modulo-2-Addition berechnet man X3 = 1100₂ + 11000₂ = 10100₂ und
nach dem Rechts-Shift erhält man nun die Zahl im Gray-Code: X4 = 1010₂.

[Bearbeiten] direkt 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.

Q_h [n+1] = !Q_h [n]

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] )
(Diese Formel ist nur eine Vermutung! Bitte bestätigen!)

Q_k [n+1] = Q_k [n] ^ ( !Q_k-2 [n] & !Q_k-3 [n] & ... & !Q₁ [n] & !Q₀ [n] & Q_h [n] )
(Auch diese Formel ist nur eine Vermutung! Wer kann bitte bestätigen!)

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

[Bearbeiten] Bedeutung

Ausgangspunkt für diesen Code ist z.B. das Problem, dass bei paralleler Übertragung einer festen Sequenz von Steuersignalzuständen durch elektrische Spannungen auf mehreren Adern einer Datenleitung nicht sichergestellt ist, dass eingangsseitig theoretisch gleichzeitige Änderungen auf mehreren Adern auch tatsächlich exakt gleichzeitig übertragen werden. Dadurch kommt es zu ungewollten Zwischenzuständen:

2-Bit-Gray-Code:

3-Bit-Gray-Code:

4-Bit-Gray-Code:

[Bearbeiten] 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.

[Bearbeiten] Lösung mit Gray-Code

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.

[Bearbeiten] 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
	¬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 bei 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.

[Bearbeiten] Anwendungen

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

Der Gray-Code wird häufig für die Wegmessung verwendet. Bei Verwendung des Gray-Codes spricht man von absoluter Wegmessung. Absolut bedeutet: Die Position des zu messenden Weges ist anhand der Stellung der Nullen und Einser sichtbar und muss nicht hochgezählt werden wie beim inkrementellen Wegmessverfahren. Weiterhin besteht beim inkrementellen Wegmessverfahren die Gefahr, dass bei einem Stromausfall der Zähler seinen Speicherinhalt verliert und somit die momentane Position verloren geht.

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 worst case, 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.

[Bearbeiten] Beispiel

Die Dezimalzahl $410 = 100 2$ entspricht dem Gray-Code $610 = 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 $710 = 111 2$ wird wie folgt dekodiert: $1\cdot 7_{10} - (1\cdot 3_{10} - 1\cdot 1_{10}) = 5_{10}$ .

[Bearbeiten] 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.

[Bearbeiten] Siehe auch

[Bearbeiten] Weblinks

Java-Beispiel für die Umwandlung einer Dezimalzahl in Gray-Code Darstellung

Von „http://de.wikipedia.org../../../g/r/a/Gray-Code_b8ad.html“

Kategorien: Binärcode | Leitungscode