Gray-Code

Der Gray-Code (auch Reflected Binary Code, nach Frank Gray, der ihn 1947 bei Bell Labs für die Übertragung patentierte) ist ein binäres Codierungssystem, bei dem sich beim Übergang zwischen zwei aufeinanderfolgenden Werten immer nur ein einzelnes Bit ändert. Im gewöhnlichen Binärcode können dagegen beim Zählen mehrere Bits gleichzeitig kippen — der Übergang von 7 auf 8 etwa ändert alle vier Bits (0111 → 1000). Genau dieses gleichzeitige Kippen mehrerer Bits ist die Fehlerquelle, die der Gray-Code beseitigt.

1. Konstruktionsvorschrift

Ein $n$-Bit-Binärwert $B$ lässt sich mit einer einzigen XOR-Operation in den entsprechenden Gray-Code $G$ umrechnen:

$$G = B \oplus (B \gg 1)$$

Das höchstwertige Bit bleibt dabei unverändert, jedes weitere Bit ist das XOR aus dem entsprechenden Binärbit und seinem nächsthöheren Nachbarn. Die Rückrichtung (Gray → Binär) erfolgt durch fortlaufendes XOR von oben nach unten:

$$b_{n-1} = g_{n-1}, \qquad b_i = b_{i+1} \oplus g_i \text{ für } i = n{-}2, \dots, 0$$

2. Konstruktion durch Spiegelung

Die Bezeichnung Reflected Binary Code kommt von einer alternativen, rekursiven Konstruktionsvorschrift, die ganz ohne die XOR-Formel auskommt: Der $n$-Bit-Gray-Code entsteht aus dem $(n{-}1)$-Bit-Gray-Code, indem man dessen Liste einmal in Originalreihenfolge mit vorangestellter 0 und einmal in umgekehrter (gespiegelter) Reihenfolge mit vorangestellter 1 aneinanderhängt:

Da an der Spiegelungs-Nahtstelle immer dasselbe Suffix wiederholt wird (nur das neue führende Bit ändert sich von 0 auf 1), bleibt die Ein-Bit-Übergangseigenschaft auch an dieser Stelle erhalten — inklusive des zyklischen Übergangs vom letzten zurück zum ersten Codewort.

3. Verifikation der Ein-Bit-Eigenschaft

def bin_to_gray(b):
    return b ^ (b >> 1)

def gray_to_bin(g):
    b = 0
    while g:
        b ^= g
        g >>= 1
    return b

def hamming_distance(a, b):
    return bin(a ^ b).count("1")

n = 4
codes = [bin_to_gray(i) for i in range(2**n)]

# Rückdekodierung für alle Werte korrekt?
assert all(gray_to_bin(bin_to_gray(i)) == i for i in range(2**n))

# Alle benachbarten Distanzen exakt 1?
dists = [hamming_distance(codes[i], codes[i+1]) for i in range(len(codes)-1)]
print("Distanzen benachbarter Codeworte:", dists)

# Zyklische Distanz (letztes zu erstem)
print("Zyklische Distanz:", hamming_distance(codes[-1], codes[0]))

print(f"Standard-Binär 7->8: Distanz {hamming_distance(7,8)}")
print(f"Gray 7->8:          Distanz {hamming_distance(codes[7],codes[8])}")

def bin_to_gray(b):
    return b ^ (b >> 1)

def gray_to_bin(g):
    b = 0
    while g:
        b ^= g
        g >>= 1
    return b

def hamming_distance(a, b):
    return bin(a ^ b).count("1")

n = 4
codes = [bin_to_gray(i) for i in range(2**n)]

# Rückdekodierung für alle Werte korrekt?
assert all(gray_to_bin(bin_to_gray(i)) == i for i in range(2**n))

# Alle benachbarten Distanzen exakt 1?
dists = [hamming_distance(codes[i], codes[i+1]) for i in range(len(codes)-1)]
print("Distanzen benachbarter Codeworte:", dists)

# Zyklische Distanz (letztes zu erstem)
print("Zyklische Distanz:", hamming_distance(codes[-1], codes[0]))

print(f"Standard-Binär 7->8: Distanz {hamming_distance(7,8)}")
print(f"Gray 7->8:          Distanz {hamming_distance(codes[7],codes[8])}")

Ausgabe:

Distanzen benachbarter Codeworte: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Zyklische Distanz: 1
Standard-Binär 7->8: Distanz 4
Gray 7->8:          Distanz 1

Distanzen benachbarter Codeworte: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Zyklische Distanz: 1
Standard-Binär 7->8: Distanz 4
Gray 7->8:          Distanz 1

4. Praktischer Einsatz

Drehgeber (Rotary Encoder): Ein mechanischer oder optischer Drehgeber liest mehrere Spuren gleichzeitig aus einer sich drehenden Codescheibe. Mit Standard-Binärcodierung können durch minimale Fertigungs- oder Timing-Toleranzen mehrere Bits nicht exakt gleichzeitig kippen — beim Übergang 7→8 etwa könnte kurzzeitig 0000, 1111 oder jeder andere Zwischenwert ausgelesen werden, je nachdem welche Spur zuerst schaltet. Mit Gray-Code ändert sich an jeder Positionsgrenze garantiert nur ein einziges Bit — ein Lesefehler kann höchstens zum unmittelbaren Nachbarwert führen, nie zu einem beliebig falschen Zwischenwert. Genau dieses Prinzip steckt in den Drehimpulsgebern, mit denen die meisten modernen Transceiver den VFO-Abstimmknopf abtasten (üblicherweise ein 2-Bit-Quadratursignal, eine Miniaturform desselben Gray-Code-Prinzips): Ein leicht versetztes Schalten der beiden Kontaktspuren führt so höchstens zu einem übersprungenen oder doppelt gezählten Schritt, nie zu einem wilden Frequenzsprung.

Analog-Digital-Wandler: Manche ADC-Architekturen (u. a. Flash-ADCs) geben intern Gray-codierte Werte aus, um genau dasselbe Problem zu vermeiden: Bei einem Übergang nahe einer Schwelle mit vielen gleichzeitig kippenden Bits (z. B. Standard-Binär bei 0111→1000) kann ein einzelner, minimal verzögerter Komparator kurzzeitig einen beliebigen, stark abweichenden Zwischenwert erzeugen (decoding glitch). Gray-Code begrenzt den größtmöglichen Fehler eines solchen Glitches auf den unmittelbaren Nachbarwert.

Bitzuordnung in der digitalen Modulation: Bei mehrwertigen Modulationsverfahren wie PSK oder QAM werden mehrere Bits auf ein Symbol (Phasen-/Amplitudenzustand) abgebildet. Ein Übertragungsfehler verwechselt dabei am wahrscheinlichsten benachbarte Symbole (kleinster euklidischer/Phasen-Abstand in der Konstellation). Ordnet man diesen benachbarten Symbolen Gray-codierte statt binär durchnummerierte Bitmuster zu, unterscheidet sich der wahrscheinlichste Fehlerfall (Verwechslung mit dem Nachbarsymbol) nur in einem einzigen Bit — die resultierende Bitfehlerrate ist dadurch für dieselbe Symbolfehlerrate spürbar niedriger als bei sequentieller Bitzuordnung.

Karnaugh-Diagramme: In der digitalen Schaltungsminimierung sind Zeilen- und Spaltenköpfe eines Karnaugh-Diagramms in Gray-Code-Reihenfolge angeordnet, damit benachbarte Felder (die zu vereinfachenden Termen zusammengefasst werden dürfen) sich stets nur in einer Variable unterscheiden.

5. Grenzen

• Keine arithmetische Kompatibilität: Addition und Subtraktion lassen sich auf Gray-codierten Werten nicht direkt durchführen — für Berechnungen muss zunächst zurück in Standard-Binär dekodiert werden (siehe Formel in Abschnitt 1).
• Kein Fehlerkorrektur-Code: Der Gray-Code begrenzt den Schaden eines Lesefehlers auf den Nachbarwert, er erkennt oder korrigiert aber keine Bitfehler im Sinne eines Codes wie Hamming — beide Konzepte ergänzen sich, lösen aber unterschiedliche Probleme.
• Reihenfolge ist an die Konstruktion gebunden: Es gibt keine eindeutige "kanonische" Nummerierung — die konkrete Bitmuster-Zuordnung hängt von der gewählten Konstruktionsvorschrift ab (hier: Standard Reflected Binary Gray Code); andere Gray-Codes mit derselben Ein-Bit-Eigenschaft, aber anderer Reihenfolge, sind möglich.