Gray-Code erklärt: Warum Drehgeber ihn verwenden

Kurz gesagt: Im reflektierten binären Gray-Code unterscheiden sich benachbarte Werte in genau einem Bit. Diese Eigenschaft begrenzt die Mehrdeutigkeit an einer korrekt aufgebauten Positionsgrenze und ist für asynchrone FIFO-Zeiger nützlich. Sie beseitigt weder Metastabilität noch Sensorfehler, kombinatorische Glitches oder die Notwendigkeit von CDC-Timing-Einschränkungen.

Ein standardmäßiger 4-Bit-Binärzähler, der von $0111$ nach $1000$ weiterzählt, schaltet alle vier Bits gleichzeitig um. In einem idealisierten Zeitdiagramm ändern sich diese Bits gleichzeitig. In realem Silizium – mit unterschiedlichen Gatterlaufzeiten, endlichen Flankensteilheiten und verrauschten Versorgungsschienen – ändern sie sich jedoch in einer nicht näher festgelegten Reihenfolge. Dadurch flackern auf dem Bus kurz Zwischenwerte wie $1111$ oder $0000$ auf. Für ein CPU-Register ist das harmlos: Der Wert wird erst nach dem Einschwingen an einer Taktflanke abgetastet. Für einen Sensor, der von einem asynchronen Beobachter gelesen wird, sind diese Glitches dagegen echte Messwerte.

Der Gray-Code, auch reflektierter Binärcode genannt, verändert die Randbedingung: Benachbarte Codewörter unterscheiden sich in einem Bit, sodass ein korrekt ausgerichteter Beobachter nicht mehrere beabsichtigte Bitübergänge zugleich auflösen muss. Das eine wechselnde Bit kann weiterhin mehrdeutig, verrauscht oder metastabil sein; Gray-Code verringert also eine Fehlerklasse, macht die Schnittstelle aber nicht unfehlbar.

Warum ist Ein-Bit-Nachbarschaft wichtig?

Betrachten wir einen Drehgeber – die optische oder magnetische Scheibe, die einer Motorsteuerung den Winkel einer Welle mitteilt. Die Scheibe besitzt konzentrische Spuren, von denen jede ein Bit des Positionsworts beiträgt und die von einem Sensor in einem festen Winkel gelesen werden. Beim Drehen der Scheibe sieht der Sensor eine Folge binärer Werte.

Sind die Spuren im natürlichen Binärcode codiert, müssen an der Grenze zwischen Position $3$ ($011$) und Position $4$ ($100$) drei Spuren beim selben Nennwinkel ihren Zustand wechseln. Unterschiede bei Sensorposition, Spurengeometrie und Schwellenwerten bedeuten, dass diese Übergänge nicht unbedingt gleichzeitig beobachtet werden. Die Steuerung kann kurz ein Zwischenwort decodieren, das weit von beiden benachbarten Positionen entfernt liegt.

Codiert man dieselbe Scheibe im Gray-Code, wird jede Winkelgrenze zu einem Ein-Bit-Übergang:

Betrachten Sie die Gray-Spalte. Zwischen je zwei benachbarten Zeilen kippt genau ein Bit. Auch zwischen Zeile 7 und Zeile 0 kippt genau ein Bit; die Folge ist also zyklisch und hat Einheitsabstand. Im vorgesehenen Modell mit jeweils nur einer überschrittenen Grenze beschränkt sich die Schwellenunsicherheit auf den alten oder neuen benachbarten Code. Fehljustierung über mehrere Grenzen hinweg, Verschmutzung, beschädigte Spuren, elektrisches Rauschen oder das Decodieren einer metastabilen Probe können dennoch einen Fehler verursachen.

Die 4-Bit-Gray-Code-Tabelle

Das Muster setzt sich natürlich fort:

Die Bezeichnung „reflektiert“ kommt von der Konstruktionsregel: Um den $(n+1)$-Bit-Code zu bilden, nimmt man den $n$-Bit-Code, spiegelt ihn vertikal, stellt der ursprünglichen Hälfte eine $0$ und der gespiegelten Hälfte eine $1$ voran. Das Spiegeln garantiert, dass die Grenze zwischen den Hälften ein Ein-Bit-Übergang ist – das neue höchstwertige Bit.

Umwandlung von Binär nach Gray

Die Umwandlung von Binär $b$ nach Gray $g$ folgt einer der elegantesten Formeln der Digitallogik:

$g_i = b_i \oplus b_{i+1}$

mit $b_n = 0$ für das MSB. Als einzelner Ausdruck:

$g = b \oplus (b \gg 1)$

In Hardware entsteht jeder Gray-Ausgang durch ein XOR zweier benachbarter Binärbits; es gibt keine Übertragskette, und die ideale Logiktiefe beträgt eine XOR-Stufe. Das garantiert nicht, dass ein kombinatorischer Ausgang glitchfrei bleibt, während sich mehrere Bits eines Binärzählers physisch ändern. Registrieren Sie den umgewandelten Gray-Wert, bevor Sie ihn als CDC-Signal verwenden. Warum XOR hierfür der passende Operator ist, zeigt erneut die Rolle des XOR-Gatters als Differenzdetektor.

Durchgerechnetes Beispiel. Wandeln Sie Binär $1011$ in Gray um.

• $g_3 = b_3 \oplus 0 = 1$
• $g_2 = b_2 \oplus b_3 = 0 \oplus 1 = 1$
• $g_1 = b_1 \oplus b_2 = 1 \oplus 0 = 1$
• $g_0 = b_0 \oplus b_1 = 1 \oplus 1 = 0$

Ergebnis: Gray $1110$; die Tabelle oben bestätigt, dass dies die Codierung der Dezimalzahl 11 ist.

Umwandlung von Gray nach Binär

Die umgekehrte Richtung ist ein Präfix-XOR:

$b_i = g_i \oplus g_{i+1} \oplus g_{i+2} \oplus \dots \oplus g_n$

Gleichwertig kann man vom MSB abwärts gehen: $b_n = g_n$, dann $b_i = b_{i+1} \oplus g_i$. Eine direkte serielle Implementierung hat lineare XOR-Tiefe, doch ein paralleler Präfix-XOR-Baum kann die Tiefe auf Kosten zusätzlicher Verdrahtung und Gatter verringern. Gehen Sie nicht davon aus, dass die einfache Kette die einzige Implementierung ist.

Für das obige Beispiel wird Gray $1110$ decodiert:

• $b_3 = g_3 = 1$
• $b_2 = b_3 \oplus g_2 = 1 \oplus 1 = 0$
• $b_1 = b_2 \oplus g_1 = 0 \oplus 1 = 1$
• $b_0 = b_1 \oplus g_0 = 1 \oplus 0 = 1$

Wiederhergestelltes Binärwort: $1011$, Dezimalzahl 11. Der Hin- und Rückweg stimmt.

Über Drehgeber hinaus: Clock-Domain-Crossing

Drehgeber sind die klassische Motivation, doch die folgenreichste moderne Nutzung von Gray-Code findet sich in FPGAs und SoCs: asynchrone FIFO-Zeiger für Clock-Domain-Crossing (CDC).

Ein FIFO mit zwei Takten benötigt auf jeder Seite eine Schätzung des Zeigers der anderen Seite, um den Voll- oder Leerzustand abzuleiten. Einen gewöhnlichen mehrbitigen Binärzähler direkt über diese Grenze zu übertragen, ist unsicher, weil ein einzelner Inkrementschritt mehrere Bits ändern kann.

Ein robuster Gray-Zeigerentwurf:

1. führt den Arbeitszeiger für lokale Arithmetik binär;
2. wandelt den nächsten Zeiger in Gray um;
3. registriert den Gray-Wert in der Quelldomäne;
4. synchronisiert jedes Gray-Bit in die Zieldomäne; und
5. vergleicht den synchronisierten Zeiger mit den dokumentierten Voll-/Leer-Gleichungen des FIFO.

Gray-Codierung bedeutet, dass pro Inkrement nur ein logisches Zeigerbit wechselt, garantiert aber für sich allein noch kein korrektes CDC. Das wechselnde Bit kann das Übernahmefenster eines Ziel-Flipflops verletzen und metastabil werden. Routing-Skew kann außerdem dazu führen, dass sich am Ziel Gray-Bits aus unterschiedlichen Quellübergängen überlappen, sofern Implementierungsbeschränkungen nicht Verzögerung oder Bus-Skew begrenzen. Sowohl AMD als auch Intel dokumentieren solche Einschränkungen für Gray-codierte FIFO-Zeiger.

Der synchronisierte Zeiger ist außerdem um mehrere Ziel-Taktzyklen verzögert. Die Voll-/Leer-Logik ist auf diesen konservativen Umgang mit der Latenz ausgelegt; sie ist kein jederzeit exakt zählender Wert über Domänengrenzen hinweg. Wenn Korrektheit entscheidend ist, verwenden Sie einen bewährten asynchronen FIFO-Entwurf oder Hersteller-IP.

Ein Gray-Code-Zähler in Hardware

Zwei praktische Ansätze sind:

1. Binärzähler mit registrierter Umwandlung. Berechnen Sie gray_next = binary_next XOR (binary_next >> 1) und übernehmen Sie beide Folgezustandswerte am selben Quelltakt. Der registrierte Gray-Ausgang folgt der Codesequenz; behandeln Sie keinen unregistrierten Konverter, der von einem durchlaufenden oder verzerrten Binärzähler gespeist wird, als glitchfrei.
2. Native Gray-Zustandsmaschine. Leiten Sie eine Folgezustandslogik her, die der gewählten Gray-Folge direkt folgt. Dadurch entfällt ein binäres Zustandsregister, doch Inkrementieren, Dekrementieren und FIFO-Adressarithmetik werden unbequemer.

Um den ersten Ansatz auszuprobieren, öffnen Sie die 4-Bit-Binärzähler-Vorlage, ergänzen das XOR-Netzwerk und registrieren dessen vier Ausgänge. Vergleichen Sie die stabilen Zustände nach jeder Taktflanke. Modelliert der Simulator Gatterlaufzeiten, untersuchen Sie auch den Ausgang des unregistrierten Konverters während der Übergänge; er zeigt, warum das Quellregister wichtig ist.

Nachteil: Die Arithmetik ist umständlich

Die Superkraft von Gray-Code – Ein-Bit-Übergänge – hat ihren Preis: Arithmetik im Gray-Code ist schwierig. Es gibt keine Übertragspropagationsformel, die direkt mit Gray-codierten Werten funktioniert. Um zwei Gray-Zahlen zu addieren, müssen beide nach Binär umgewandelt, addiert und zurückgewandelt werden. Multiplikation und Schieben sind ebenso nicht direkt möglich.

Deshalb wandeln gewöhnliche arithmetische Datenpfade Gray-codierten Zustand im Allgemeinen nach Binär um, statt vollständige Arithmetik direkt in Gray auszuführen. Die Codierung ist an bestimmten Grenzen hilfreich, kein universeller Ersatz für Binär. Karnaugh-Diagramme verwenden Gray-Anordnung aus einem anderen Grund: Benachbarte Zellen müssen sich in genau einer Eingangsvariablen unterscheiden, damit geometrische Gruppen Implikanten entsprechen.

Historischer Hinweis

Die Codierung ist nach dem Bell-Labs-Forscher Frank Gray benannt. Seine Patentanmeldung „Pulse Code Communication“ wurde 1947 eingereicht und 1953 als US 2,632,058 erteilt; sie nennt das Verfahren reflected binary code und betont, dass benachbarte dargestellte Amplituden sich in einer Impulsposition unterscheiden. Verwandte Folgen mit Einheitsabstand gab es schon vor dem Patent, daher ist es präziser, Gray diese einflussreiche Anwendung und Namenslinie zuzuschreiben, statt ihm die Erfindung jeder solchen Folge zuzuschreiben.

Häufige Fallstricke

• Annehmen, dass Arithmetik funktioniert. Gray-codierte Werte bitweise zu addieren, erzeugt Unsinn. Wandeln Sie immer zuerst nach Binär um.
• Die MSB-Nullkonvention ignorieren. Die Binär-zu-Gray-Formel setzt eine virtuelle Null über dem MSB voraus. Wer sie vergisst, invertiert das hohe Bit.
• Gray mit Schieberegister-Schleifen vermischen. Ein Standard-Schieberegister wie die SISO-/SIPO-Entwürfe schiebt Bits seitlich und erhält Einheitsabstandseigenschaften nicht durchgängig. Wandeln Sie an den Grenzen um.
• Gray mit One-Hot verwechseln. One-Hot-Codierung (immer nur ein gesetztes Bit) ist in einem anderen Sinn ebenfalls glitchresistent, aber $O(2^n)$ breit statt $n$. Gray-Code ist die kompakte Wahl.

Wie geht es weiter?

Der veröffentlichte Leitfaden zu SISO, SIPO, PISO und PIPO vergleicht die vier üblichen Datenpfade von Schieberegistern. Verwenden Sie kein gewöhnliches Schieberegister als Ersatz für einen asynchronen FIFO: Zusammengehörige mehrbitige Daten benötigen ein Protokoll, das ihre Kohärenz über die Taktgrenze hinweg bewahrt.

Um Gray-Code in Aktion zu sehen, laden Sie die 4-Bit-Binärzähler-Vorlage, bauen den Konverter, fügen ein Ausgangsregister hinzu und prüfen den Hamming-Abstand zwischen aufeinanderfolgenden registrierten Werten. Entfernen Sie anschließend absichtlich das Register in einem verzögerungsbewussten Modell und untersuchen Sie das Übergangsverhalten.

Primärquellen

• Frank Gray, US-Patent 2,632,058, „Pulse Code Communication“
• AMD-Hinweise zu asynchronen Clock-Domain-Crossings
• AMD-Einschränkungen für Gray-codierte CDC-Busse
• Intel-Timing-Einschränkungen für FIFOs mit zwei Takten