Wikipedia · einfach zusammengefasst · Stand
Exklusiv-Oder-Gatter
Dieses Verhalten kann zum Beispiel als Paritätsgenerator oder Modulo-2-Addierer genutzt werden. Beispiel: Der 74LVC1G386 Schaltkreis wird als Logikgatter …
Inhalt6 Abschnitte
Grundprinzip und Darstellung
Ein Exklusiv-Oder-Gatter (XOR-Gatter) ist eine elektronische Schaltung mit zwei Eingängen und einem Ausgang. Der Ausgang ist genau dann logisch „1“, wenn die Eingänge verschieden sind: Einer muss „1“, der andere „0“ sein. Sind beide Eingänge „0“ oder beide „1“, ist der Ausgang „0“. Die Verknüpfung heißt auch Anti- oder Kontravalenz. Anders als beim einfachen Oder führt also der Fall „1“ und „1“ nicht zu „1“.
Für die Eingänge A und B gilt: 0 ⊻ 0 = 0, 0 ⊻ 1 = 1, 1 ⊻ 0 = 1 und 1 ⊻ 1 = 0. Gebräuchliche Schreibweisen sind „A XOR B“, „A EOR B“, A ⊕ B und A ⊻ B; in C und davon abgeleiteten Programmiersprachen steht der bitweise Operator ^ für XOR. Eine logische Form lautet Y = A,\underline{\lor},B = A\oplus B = A\nleftrightarrow B = A\overline{B}+\overline{A}B.
Aufbau aus anderen Gattern
Ein XOR-Gatter kann aus anderen Grundgattern aufgebaut werden. Die zentrale Zerlegung ist
x,\underline{\lor},y \Leftrightarrow ((\neg x\land y)\lor(x\land\neg y)).
Sie bedeutet: Das Ergebnis ist wahr, wenn x falsch und y wahr ist oder umgekehrt. Eine Umsetzung mit Nicht-, Und- und Oder-Gattern ist wegen der vielen unterschiedlichen Bauteile für Hardware meist nur ausnahmsweise relevant.
Weitere äquivalente Aufbauten verwenden vier NAND-Gatter, oder ein NAND-, ein Und- und ein Oder-Gatter: x,\underline{\lor},y \Leftrightarrow ((x\overline{\land}y)\land(x\lor y)). Auch ein NOR- und ein AND-OR-Invert-Gatter können XOR bilden. Inhaltlich dürfen dabei weder beide Eingänge wahr noch beide falsch sein.
XOR mit mehreren Eingängen und Berechnung
Bei drei oder mehr Eingängen kann „Exklusiv-Oder“ unterschiedlich verstanden werden. Ein „1-aus-n“-Detektor würde nur dann „1“ liefern, wenn genau einer der Eingänge „1“ ist. Praktisch wird jedoch überwiegend eine Kaskade aus XOR-Gattern mit je zwei Eingängen verwendet. Dann ist der Ausgang „1“, wenn eine ungerade Anzahl der Eingänge „1“ hat, und „0“ bei einer geraden Anzahl. Das eignet sich als Paritätsgenerator oder Modulo-2-Addierer.
Der 3-Eingangs-Schaltkreis 74LVC1G386 implementiert beispielsweise einen Paritätsgenerator: Bei 000, 011, 101 und 110 ist Y = 0; bei 001, 010, 100 und 111 ist Y = 1. Auch STEP 7 verwendet dieses Verhalten bei XOR-Bitverknüpfungen mit mehr als zwei Signalen. Paul Horowitz und Winfield Hill vertreten dagegen im Lehrbuch The Art of Electronics die Auffassung, ein XOR-Gatter habe niemals mehr als zwei Eingänge.
Rechnerisch ist XOR die Addition von Bits modulo 2: Man addiert die Eingangswerte und betrachtet den Rest bei Division durch 2. Eine gerade Summe ergibt 0, eine ungerade Summe 1. Bei zwei Bits zeigt XOR daher ihre Ungleichheit an; dies gilt auch für eine beliebige gerade Anzahl von Eingangssignalen.
Addition, Verschlüsselung und Prüfsummen
Bei der Addition binärer Zahlen liefert XOR die Summe eines Bits ohne Übertrag. Bei x = 1 und y = 1 bildet zusätzlich etwa ein Und-Gatter einen Übertrag, der beim nächsthöheren Bit als „1“ berücksichtigt wird. Der Addierer des Von-Neumann-Addierwerks nutzt diese Logik.
Das nachweislich sichere One-Time-Pad wird meist mit XOR umgesetzt. Klartext und ein gleich langer zufälliger Schlüssel werden bitweise exklusiv-oder-verknüpft; so entsteht der Geheimtext. XOR von Geheimtext und demselben Schlüssel stellt den ursprünglichen Klartext wieder her. Kennt ein Angreifer Klartext und Geheimtext, kann er den Schlüssel durch XOR bestimmen. Beim One-Time-Pad ist das unschädlich, weil jede Nachricht einen vollständig unabhängigen Schlüssel verwendet.
Ist bei einer XOR-Verschlüsselung der Schlüssel kürzer als der Geheimtext und wird wiederholt, kann ein Angreifer die Schlüssellänge n über verschobene Geheimtexte untersuchen. Es gilt Geheimtext ⊕ Geheimtext_n = Klartext ⊕ Klartext_n, weil Schlüssel ⊕ Schlüssel = 0. Wiederholungen im Klartext können den Schlüssel besonders leicht verraten. Ein kurzer Schlüssel kann durch ein Verfahren zur Erzeugung eines langen Schlüssels aus einem Passwort ersetzt werden; RC4 gilt mittlerweile als unsicher, Spritz wird als sicherer, aber etwas langsamer genannt.
XOR ermöglicht auch Paritätsdaten zur Wiederherstellung: Aus 0101 und 1011 wird 0101 XOR 1011 = 1110. Ist 0101 verloren, ergibt 1011 XOR 1110 wieder 0101. RAID 5 nutzt dieses Prinzip: Zwei Datenblöcke werden gespeichert, auf einer dritten Platte liegt ihre XOR-Verknüpfung; fällt eine der drei Festplatten aus, lassen sich die Daten aus den beiden anderen restaurieren.
Signale formen und invertieren
Zur Frequenzverdopplung eines Rechtecksignals bis zu einigen 100 MHz kann ein XOR-Gatter ein unverzögertes und ein geringfügig verzögertes Signal erhalten, etwa über ein RC-Glied oder Gatterlaufzeiten. Das Gatter schaltet an steigender und fallender Flanke. Es entstehen phasengebundene Nadelimpulse, deren Länge ungefähr der Signalverzögerung entspricht. Weil keine Resonanzfilter verwendet werden, darf das Eingangssignal fast beliebige Tastverhältnisse haben oder stark frequenzmoduliert sein; ein Tastgrad von 50 % ist jedoch im Allgemeinen nicht erreichbar.
Als schaltbarer Inverter dient ein Eingang dem Signal, der andere als Steuereingang: Bei logisch „0“ wird das Signal unverändert durchgelassen, bei logisch „1“ wird es invertiert.
CMOS-Umsetzung
Eine XOR-Realisierung aus Und- und Oder-Gattern benötigt in CMOS-Technik 16 Transistoren. Eine direkte Umsetzung benötigt 12 Transistoren; mit Tricks sind unter Geschwindigkeitseinbußen sechs beziehungsweise vier Transistoren möglich. In der beschriebenen Schaltung invertieren T1+T2 und T3+T4 die Eingangssignale. Bei High-Potential an beiden Eingängen leiten T7+T8 und ziehen den Ausgang Y auf Low-Potential. Bei Low-Potential an beiden Eingängen leiten T11+T12, da die vorgeschalteten Inverter die Signale umkehren.
Eine Umsetzung mit AND-OR-Invert-Logik braucht 10 Transistoren und wurde beispielsweise beim Intel 80386 verwendet. Es gibt außerdem Implementierungen, die XOR und NXOR zugleich bereitstellen.
