Startseite▸Algorithmen & KI▸Gray-Code — Reflektierter Binärcode & Hyperwürfel-Pfad

🔢 Gray-Code — Reflektierter Binärcode & Hyperwürfel-Pfad

Erkunde den Gray-Code (reflektierter Binärcode): die Sequenz, bei der jeder Schritt genau ein Bit umschaltet. Baue ihn per Spiegel-und-Präfix auf, beobachte, wie der Hamilton-Pfad jeden Knoten eines n-Würfels durchläuft, und sieh, warum Drehgeber ihn nutzen, um Übergangsfehler zu vermeiden.

Algorithmen & KI3DLeicht60 FPS

Über den Gray-Code

Der Gray-Code (formal der binär reflektierte Gray-Code, BRGC) ist eine Anordnung von Binärzahlen, bei der sich benachbarte Werte um genau ein Bit unterscheiden. Erfunden von Frank Gray bei Bell Labs im Jahr 1947 und patentiert zur Verwendung in der Pulscodemodulation, eliminiert er die vorübergehenden Mehrbit-Fehler, die im gewöhnlichen Binärcode auftreten, wenn mehrere Bits gleichzeitig umschalten — entscheidend in der digitalen Elektronik, wo sich Signale nicht augenblicklich ändern können. Drehwellen-Encoder, Analog-Digital-Wandler und Karnaugh-Diagramme nutzen alle die Ein-Bit-Änderungseigenschaft, um Glitch-Fehler zu reduzieren und die Logikminimierung zu vereinfachen.

Diese Simulation visualisiert Gray-Codes als Pfad auf einem n-dimensionalen Hyperwürfel: Jede Bitposition entspricht einer Achse, und jeder Gray-Code-Übergang ist eine Kante des Würfels. Du kannst die Sequenz für n von 1 bis 5 durchschreiten und beobachten, wie der Durchlauf jeden Knoten genau einmal besucht — ein Hamilton-Pfad auf dem Hyperwürfel-Graphen — und sehen, wie jeder Übergang genau ein Bit umschaltet.

Häufig gestellte Fragen

Wie wird der Standard-Gray-Code aus einer Binärzahl konstruiert?

Der n-Bit-Gray-Code G(k) für eine Ganzzahl k wird berechnet als G(k) = k XOR (k >> 1): Nimm die Binärdarstellung von k, verschiebe sie um eine Position nach rechts und verknüpfe sie per XOR mit dem Original. Zum Beispiel k=6 (binär 110) → 110 XOR 011 = 101 (dezimal 5), was den 4. Gray-Code in einer 3-Bit-Sequenz ergibt (0,1,3,2,6,7,5,4 in Dezimalzahlen). Die Umkehrung — die Wiederherstellung von k aus G(k) — erfordert ein iteratives Präfix-XOR über die Bits.

Warum ist der Gray-Code für Drehgeber wichtig?

Ein Drehgeber liest die Winkelposition einer Welle aus einem Muster reflektierender oder leitfähiger Segmente aus. Wird Standard-Binärcode verwendet, erfordert ein Übergang wie 7→8 (0111→1000), dass alle vier Bits umschalten; wenn die mechanische Ablesung leicht fehlausgerichtet ist, können Zwischenzustände wie 0110 oder 1010 gelesen werden, was völlig falsche Positionen meldet. Der Gray-Code stellt sicher, dass sich benachbarte Positionen immer um genau ein Segment unterscheiden, sodass immer nur ein Bit in einem mehrdeutigen Zustand sein kann, was Positionsfehler auf ±1 begrenzt.

Was ist die "reflektierte" Konstruktion, die dem Gray-Code seinen vollen Namen gibt?

Der n-Bit-BRGC wird rekursiv aufgebaut: Nimm die (n−1)-Bit-Gray-Code-Liste, stelle jedem Eintrag eine 0 voran, um die ersten 2ⁿ⁻¹ Einträge zu erhalten, und hänge dann die umgekehrte Liste mit vorangestellter 1 an. "Reflektiert" bezieht sich auf diese Spiegelbild-Umkehrung, die sicherstellt, dass sich der letzte Eintrag der 0-Präfix-Hälfte und der erste Eintrag der 1-Präfix-Hälfte um genau ein Bit (das höchstwertige Bit) unterscheiden. Die Rekursion erzeugt dasselbe Ergebnis wie die XOR-Formel G(k) = k XOR (k >> 1).

Wie wird der Gray-Code in Karnaugh-Diagrammen verwendet?

Karnaugh-Diagramme ordnen die Zellen der Wahrheitstabelle entlang jeder Achse in Gray-Code-Reihenfolge an, sodass logisch benachbarte Minterme (die sich in einer Variablen unterscheiden) im Raster auch physisch benachbart sind. Dies ermöglicht die visuelle Identifikation von Rechtecken aus Einsen (oder Nullen), die Primimplikanten entsprechen, und vereinfacht Boolesche Ausdrücke. Ohne Gray-Ordnung wären benachbarte Zellen im Raster nicht logisch benachbart, was den Zweck des Diagramms zunichtemachen würde.

Ist die Gray-Code-Sequenz eindeutig?

Nein. Für n Bits existieren viele verschiedene Ein-Bit-Änderungssequenzen; diese werden Gray-Codes oder Hamilton-Kreise auf dem n-Würfel genannt, und ihre Anzahl wächst überexponentiell mit n. Der binär reflektierte Gray-Code ist die kanonische Wahl aufgrund seiner einfachen rekursiven Konstruktion und der geschlossenen XOR-Formel. Andere Familien umfassen ausgewogene Gray-Codes (bei denen jedes Bit gleich oft umschaltet), monotone Gray-Codes und Snake-in-the-Box-Codes zur Fehlerkorrektur.

Wie hängt der Gray-Code mit den Türmen von Hanoi zusammen?

Die Sequenz der Bitpositionen, die sich in aufeinanderfolgenden Gray-Code-Werten ändern, ist genau die Sequenz der Scheibennummern, die in der optimalen Lösung der Türme von Hanoi bewegt werden: Position 1, 2, 1, 3, 1, 2, 1, 4, … (die Lineal-Sequenz). Dieser Isomorphismus bedeutet, dass jeder Zug im Hanoi-Puzzle dem Umschalten eines Bits im Gray-Code-Zähler entspricht, was eine tiefe kombinatorische Verbindung zwischen den beiden Problemen herstellt.

Was ist ein ausgewogener Gray-Code?

Ein ausgewogener Gray-Code ist einer, bei dem sich jede Bitposition über die 2ⁿ Übergänge hinweg so gleichmäßig wie möglich ändert. Im Standard-BRGC schaltet das höchstwertige Bit nur einmal um, während das niedrigstwertige Bit 2ⁿ⁻¹-mal umschaltet, was eine sehr ungleiche Verteilung erzeugt. Ausgewogene Gray-Codes verteilen die Übergänge gleichmäßig, was für Anwendungen wie Wear-Levelling bei Flash-Speicher und die Reduzierung der Schaltleistung in CMOS-Schaltungen wichtig ist.

Wie wird der Gray-Code zur Fehlerkorrektur verwendet?

Snake-in-the-Box-Codes sind Gray-Code-Pfade auf dem n-Würfel, bei denen keine zwei nicht benachbarten Pfadknoten auch im Würfel benachbart sind (ein "schlängelnder" Hamilton-Pfad). Sie bilden selbstprüfende Ein-Fehler-Codes: Jeder Ein-Bit-Fehler in einem Codewort bewegt sich zu einem Nicht-Codewort-Knoten. Coil-in-the-Box-Codes erreichen einen größeren minimalen Hamming-Abstand. Diese kombinatorischen Codes kommen in fehlertoleranten Rechensystemen und Datenspeichersystemen vor.

Können Gray-Codes für nicht-binäre Zahlensysteme definiert werden?

Ja. Ausgewogene ternäre Gray-Codes, Gray-Codes mit gemischter Basis und Gray-Codes für Permutationen existieren alle. Der Steinhaus-Johnson-Trotter-Algorithmus erzeugt alle Permutationen von N Elementen durch benachbarte Transpositionen, was das Permutationsanalogon eines Ein-Bit-Änderungs-Gray-Codes ist. Diese werden in erschöpfenden Suchalgorithmen verwendet, die Permutationen oder Kombinationen mit minimaler Änderung zwischen aufeinanderfolgenden Zuständen aufzählen.

Wie vereinfacht der Gray-Code das Design digitaler Schaltkreise?

Bei sequentiellen Zustandsmaschinen (FSMs) stellt die Kodierung von Zuständen im Gray-Code sicher, dass Zustandsübergänge nur ein Flip-Flop gleichzeitig ändern müssen. Dies eliminiert vorübergehende Glitch-Zustände, die unbeabsichtigte Logik auslösen könnten, reduziert den Stromverbrauch und verbessert die Zeitreserven. FPGA-Design-Tools bieten oft automatisch Gray-Code-FSM-Kodierung als Option an, wenn der Designer "sichere" oder "One-Hot-Adjacent"-Kodierungsstile auswählt.

Über diese Simulation

Diese Simulation baut den reflektierten binären Gray-Code für eine gewählte Anzahl an Bits auf und animiert ihn als Wanderung über den n-dimensionalen Hyperwürfel. Jede Ganzzahl wird mit g = b XOR (b >> 1) umgewandelt, sodass sich aufeinanderfolgende Codes immer in einem Bit unterscheiden. Die Wanderung ist ein Hamilton-Pfad; eine zweite Ansicht bildet ihn auf eine Drehgeber-Scheibe ab, eine dritte als Tabelle.

🔬 Was es zeigt

Die Hyperwürfel-Ansicht zeichnet die Knoten und Kanten des n-Würfels und verfolgt den Hamilton-Pfad mit einer grünen Spur, wobei der aktuelle Code markiert wird. Die Encoder-Ansicht schattiert konzentrische Ringe wie eine echte Drehgeber-Scheibe. Die Tabellen-Ansicht listet jeden Index mit Binär- und Gray-Werten auf und hebt das umgeschaltete Bit hervor.

🎮 So wird's benutzt

Wechsle die Ansichten mit den Schaltflächen Hyperwürfel, Encoder und Tabelle. Der n-Bit-Regler (2–6) legt fest, wie viele Bits und damit 2ⁿ Codes erscheinen. Geschwindigkeit (0,2–4) legt fest, wie schnell Abspielen voranschreitet; Schritt bewegt sich um jeweils einen Code weiter; Zurücksetzen kehrt zu Code 000 zurück.

💡 Wusstest du schon?

Frank Gray reichte das diesem Code zugrunde liegende Patent 1947 bei Bell Labs ein, während er an Pulscodemodulation arbeitete; es wurde 1953 erteilt, Jahrzehnte bevor es in Drehgebern und Karnaugh-Diagrammen zum Standard wurde.

Häufig gestellte Fragen

Was zeigen die drei Ansichtsmodi (Hyperwürfel, Encoder, Tabelle) eigentlich?

Die Hyperwürfel-Ansicht zeichnet die Knoten und Kanten des Würfels und verfolgt den Hamilton-Pfad, während die Sequenz fortschreitet. Die Encoder-Ansicht rendert dieselben Codes als konzentrische Ringe auf einer Scheibe, wie ein physischer Drehgeber. Die Tabellen-Ansicht listet Binär- und Gray-Codes nebeneinander auf.

Was bedeutet die Statistik "geändertes Bit"?

Sie zeigt an, welche Bitposition sich zwischen dem vorherigen und dem aktuellen Gray-Code geändert hat, gezählt vom höchstwertigen Bit. Vor dem ersten Schritt wird ein Strich angezeigt, danach ein Index wie #0 oder #1 — immer genau ein Bit.

Warum ändert sich das Hyperwürfel-Layout, wenn der n-Bit-Regler bewegt wird?

Jedes Bit fügt eine Achse hinzu: 2 Bit bilden ein Quadrat, 3 Bit einen Würfel, und bis zu 4 Bit werden mit einer festen Richtung pro Bit abgeflacht. Über 4 Bit wechselt das Layout zu einem Kreis, der alle 2ⁿ Codes gleichmäßig verteilt, da eine flache Projektion unlesbar wird.

Was sind die konzentrischen Ringe in der Encoder-Ansicht?

Jeder Ring repräsentiert ein Bit, wobei der äußerste Ring das höchstwertige ist. Ein Segment leuchtet auf, wenn dieses Bit für den Code an diesem Winkel 1 ist, sodass die Scheibe das Muster reproduziert, das ein echter absoluter Drehgeber auf seine Codescheibe druckt.

Wie unterscheiden sich die Steuerelemente Abspielen, Schritt und Zurücksetzen?

Abspielen animiert kontinuierlich mit der durch Geschwindigkeit festgelegten Rate und rückt jeweils eine Kante weiter bis zum letzten Code. Schritt rückt genau einen Code weiter und stoppt. Zurücksetzen setzt die Sequenz auf Index 0 zurück und stoppt jede laufende Animation.

⚙ Unter der Haube

Erkunde den Gray-Code (g = b XOR b>>1), bei dem jeder aufeinanderfolgende Wert ein Bit umschaltet. Durchschreite die 2ⁿ-Sequenz, verfolge den Hamilton-Pfad auf einem n-Würfel und sieh, warum Drehgeber Mehrbit-Fehler vermeiden.

Gray codebinaryhypercubeHamiltonian pathCanvas 2D

3D · Three.js / WebGL-Renderer · 60 FPS Ziel · läuft vollständig clientseitig, ohne Installation