Quelltext der Seite Exklusiv-Oder-Gatter

{{Gatter}}
Ein '''Exklusiv-Oder-Gatter''', auch '''XOR-Gatter''' (von {{enS|e'''X'''clusive '''OR'''|de=[[Kontravalenz|exklusives Oder]]}}, „entweder oder“) ist ein [[Logikgatter|Gatter]] (eine elektronische Schaltung) mit zwei<!--mehreren--> Eingängen und einem Ausgang, bei dem der Ausgang [[Logik|logisch]] „1“ ist, wenn an nur einem Eingang „1“ anliegt und an dem anderen<!--den restlichen--> „0“. Die Exklusiv-Oder-Verknüpfung wird auch als Anti- oder [[Kontravalenz]] bezeichnet.

Das<!--Für den einfachen Fall eines Exklusiv-Oder-Gatters mit zwei Eingängen--> bedeutet<!-- das-->, dass das Gatter mit ''verschiedenen'' Eingangspegeln beaufschlagt sein muss, um am Ausgang eine „1“ zu erhalten. ''Entweder'' an dem einen ''oder'' am anderen Eingang muss „1“ anliegen. Im Unterschied zu einer einfachen OR-Verknüpfung gilt die Bedingung als nicht erfüllt, wenn an ''beiden'' Eingängen eine „1“ anliegt. Bei Exklusiv-Oder ist das Ergebnis in diesem Fall eine „0“.

== Symbolik ==
In der Literatur wird das Exklusiv-Oder mit verschiedenen Symbolen gekennzeichnet. Üblich ist es, den Operator als „XOR“ oder „EOR“ auszuschreiben, z.&nbsp;B. mit dem Ausdruck „A ''XOR'' B“. Bei Verwendung des Symbols „+“ für das [[Disjunktion|logische Oder]] wird das Symbol „<math>\oplus</math>“ für das Exklusiv-Oder verwendet. Bei der Verwendung von „∨“ für das logische Oder wird hingegen „⊻“ für das Exklusiv-Oder verwendet. Als [[bitweiser Operator]] findet in [[C (Programmiersprache)|C]] (und von ihr abgeleiteten Programmiersprachen) das Zeichen <code>[[^]]</code> Verwendung.

{{Siehe auch|Kontravalenz#Notation_und_Aussprache|titel1=Notation und Aussprache des Kontravalentors}}

{| class="wikitable"
|+ Übersicht
|-
! rowspan="2"| Funktion
! colspan="3"| Schaltsymbol
! rowspan="2"| [[Wahrheitstabelle]]
! rowspan="2"| Relais-Logik
|-
| IEC 60617-12
| US [[ANSI]] 91-1984
| [[DIN]] 40700 (vor 1976)
|-
| <math>Y = A \,\underline{\lor}\, B</math><br /><math>Y = A \oplus B</math><br /><br /><math>Y = A \nleftrightarrow B</math>


<math>Y = A\overline{B} + \overline{A}B</math>
| [[Datei:IEC XOR label.svg|125px|rahmenlos|alt=|klasse=skin-invert|zentriert]]
| [[Datei:Xor-gate-en.svg|125px|rahmenlos|alt=|klasse=skin-invert|zentriert]]
| [[Datei:Logic-gate-xor-de.svg|125px|rahmenlos|alt=|klasse=skin-invert|zentriert]]<br />oder<br />[[Datei:Logic-gate-xor-de-2.svg|125px|rahmenlos|alt=|klasse=skin-invert]]
|
{| class="wikitable centered"
|-
! style="width:33%"|A
! style="width:33%"|B
! Y&nbsp;=&nbsp;A&nbsp;⊻&nbsp;B
|-
| {{Nein-Feld|0}} || {{Nein-Feld|0}} || {{Nein-Feld|'''0'''}}
|-
| {{Nein-Feld|0}} || {{Ja-Feld|1}} || {{Ja-Feld|'''1'''}}
|-
| {{Ja-Feld|1}} || {{Nein-Feld|0}} || {{Ja-Feld|'''1'''}}
|-
| {{Ja-Feld|1}} || {{Ja-Feld|1}} || {{Nein-Feld|'''0'''}}
|}
| [[Datei:Relay xor.svg|200px|rahmenlos|alt=|klasse=skin-invert|zentriert]]
|}

Das Gleichheitszeichen = verdeutlicht beim gegenwärtig in Deutschland gültigen Schaltsymbol, dass nur bei ''einer'' „1“ an den Eingängen (High-Pegel, logisch „1“) der Ausgang „1“ ist.

== Synthese ==
{| class="wikitable toptextcells"
|+ Exklusiv-Oder
|- class="skin-invert"
| [[Datei:XOR Aufbau NAND.svg|zentriert]]
| [[Datei:XOR Aufbau Und-Oder.svg|zentriert]]
| [[Datei:254px 3gate XOR.jpg|zentriert]]
| [[Datei:XOR AOI logic gates.svg|zentriert]]
|-
| Aufbau eines Exklusiv-Oder-Gatters<br />aus vier NAND-Gattern
| Aufbau eines Exklusiv-Oder-Gatters aus Und-,<br />Oder- und Nicht-Gattern (letztere für die<br />Negation je eines der Und-Gatter-Eingänge)
| Aufbau eines Exklusiv-Oder-Gatters<br />aus Und-, Oder- und NAND-Gattern
| Aufbau eines Exklusiv-Oder-Gatters aus<br /> einem NOR- und einem [[AND-OR-Invert]]-Gatter
|}

Die linke Abbildung zeigt den Aufbau eines Exklusiv-Oder-Gatters aus vier [[NAND-Gatter|NAND-Bausteinen]] gemäß der logischen Äquivalenz

:<math>x \,\underline{\lor}\, y \Leftrightarrow \Big( x \,\overline{\land}\, ( x \,\overline{\land}\, y ) \Big) \,\overline{\land}\, \Big( y \,\overline{\land}\, ( x \,\overline{\land}\, y ) \Big)</math>

Die zweite Abbildung von links zeigt den Aufbau eines Exklusiv-Oder-Gatters aus [[Nicht-Gatter|Nicht-]], [[Und-Gatter|Und-]] und [[Oder-Gatter|Oder-Bausteinen]]. Aufgrund der Vielzahl an unterschiedlichen Komponenten besteht allerdings nur in Ausnahmefällen Relevanz für die Umsetzung in Hardware:

:<math>x \,\underline{\lor}\, y \Leftrightarrow \Big( \, ( \neg{x} \land  y ) \lor ( x \land \neg{y} ) \, \Big)</math>

Die dritte Abbildung von links zeigt den Aufbau eines Exklusiv-Oder-Gatters aus einem [[NAND-Gatter|NAND-]], einem [[Und-Gatter|Und-]] und einem [[Oder-Gatter]].

:<math>x \,\underline{\lor}\, y \Leftrightarrow \Big( \, ( x \overline{\land}  y ) \land ( x \lor y ) \, \Big)</math>

Die rechte Abbildung zeigt den Aufbau eines Exklusiv-Oder-Gatters aus einem [[NOR-Gatter|NOR]]- und einem [[AND-OR-Invert]]-Gatter. Umgangssprachlich entspricht diese Formulierung der Aussage, dass weder beide Eingänge beide wahr (d.&nbsp;h. <math> x \land y </math>) noch beide falsch (d.&nbsp;h. <math> x \overline{\lor} y</math>) sein dürfen.

:<math>x \,\underline{\lor}\, y \Leftrightarrow \Big( \, (x \overline{\lor} y) \overline{\lor} (x \land y)  \, \Big)</math>

=== Mehr als zwei Eingänge ===

Die wörtliche Interpretation des Namens „Exklusiv-Oder“ und auch die Symbolik des rechteckigen IEC Schaltzeichens (mit „=1“) werfen die Frage nach dem korrekten Verhalten bei mehr als 2 Eingängen auf. Wenn ein Logikgatter drei oder mehr Eingänge besitzt und am Ausgang nur dann eine „1“ produziert, wenn genau einer der Eingänge den Wert „1“ hat, dann wäre es eine Art „[[1-aus-n-Code|1-aus-n]]“ Detektor (für 2 Eingänge ist dies auch tatsächlich der Fall).

In der Praxis wird dies allerdings selten so implementiert. Es ist überwiegend üblich, das Verhalten weiterer Eingänge so zu betrachten, als ob eine Kaskade von XOR-Operationen mit jeweils 2 Eingängen aufgebaut würde: Die ersten beiden Signale werden in ein erstes XOR-Gatter eingespeist. Der Ausgang dieses Gatters wird zusammen mit dem dritten Eingangssignal in ein zweites XOR-Gatter eingespeist und so weiter für alle weiteren Eingangssignale. Das Ergebnis ist eine Schaltung, welche „1“ ausgibt, wenn eine ungerade Anzahl Eingänge den Wert „1“ haben -- und „0“ bei gerader Anzahl von Eingängen mit „1“. Dieses Verhalten kann zum Beispiel als Paritätsgenerator oder Modulo-2-Addierer genutzt werden.

Beispiel: Der [[Liste von integrierten Schaltkreisen der 74xx-Familie|74LVC1G386]] Schaltkreis wird als Logikgatter mit 3 Eingängen beworben und implementiert einen Paritätsgenerator.<ref>[https://assets.nexperia.com/documents/data-sheet/74LVC1G386.pdf 74LVC1G386] [[data sheet]]</ref> Die dazugehörige Wahrheitstabelle sieht wie folgt aus:

{| class="wikitable"
|-
! style="width:25%"|A
! style="width:25%"|B
! style="width:25%"|C
! Y
|-
| {{Nein-Feld|0}} || {{Nein-Feld|0}} || {{Nein-Feld|0}} || {{Nein-Feld|'''0'''}}
|-
| {{Nein-Feld|0}} || {{Nein-Feld|0}} || {{Ja-Feld|1}} || {{Ja-Feld|'''1'''}}
|-
| {{Nein-Feld|0}} || {{Ja-Feld|1}} || {{Nein-Feld|0}} || {{Ja-Feld|'''1'''}}
|-
| {{Nein-Feld|0}} || {{Ja-Feld|1}} || {{Ja-Feld|1}} || {{Nein-Feld|'''0'''}}
|-
| {{Ja-Feld|1}} || {{Nein-Feld|0}} || {{Nein-Feld|0}} || {{Ja-Feld|'''1'''}}
|-
| {{Ja-Feld|1}} || {{Nein-Feld|0}} || {{Ja-Feld|1}} || {{Nein-Feld|'''0'''}}
|-
| {{Ja-Feld|1}} || {{Ja-Feld|1}} || {{Nein-Feld|0}} || {{Nein-Feld|'''0'''}}
|-
| {{Ja-Feld|1}} || {{Ja-Feld|1}} || {{Ja-Feld|1}} || {{Ja-Feld|'''1'''}}
|}

Auch in gängiger Automatisierungssoftware wie beispielsweise [[STEP 7]] ist dieses Verhalten bei XOR-Bitverknüpfungen von mehr als zwei Eingangssignalen so implementiert.

[[Paul Horowitz]] und Winfield Hill gehen im Lehrbuch ''The Art of Electronics'' die Problematik an, indem sie schreiben, ein Exklusiv-Oder-Gatter habe niemals mehr als zwei Eingänge.<ref>[[Paul Horowitz|Horowitz]] & Hill: ''The Art of Electronics'', Second edition, S. 480 oben links, Zitat: {{" |Sprache=en |Text=it [an exclusive OR gate] never has more than two inputs}}</ref>

== Programmierung ==

Die Exklusiv-Oder-Verknüpfung lässt sich auch durch die [[Addition]] zweier [[Bit]]s [[modulo]] 2 berechnen. Dazu berechnet man die einfache Summe der Eingangssignale, dividiert die Summe durch 2 und betrachtet danach den Rest der Division. Ist die Summe eine gerade Zahl, so ist der Rest gleich null, ist sie ungerade, so ist der Rest gleich eins. Weiterhin kann die einfache Exklusiv-Oder-Verknüpfung zweier Eingangssignale auch als Anzeige der Ungleichheit der Eingangsbits angesehen werden. Dieses gilt auch für eine beliebige gerade Anzahl an Eingangssignalen.

== Anwendung ==
=== Addition von binären Zahlen ===
Ein Exklusiv-Oder-Gatter kann zur Addition von binären Zahlen eingesetzt werden. Hier wird zusätzlich, zum Beispiel mit Hilfe eines Und-Gatters, beim Zustand x=1 und y=1 ein sogenannter [[Übertrag]] gebildet. Dieser Übertrag ist bei der Addition des nächsthöheren Bits als „1“ zu berücksichtigen. Der [[Addierer]] des Von-Neumann-Addierwerks benutzt diese Logik.

=== Kryptografie ===
Das nachweislich sichere [[Verschlüsselungsverfahren]] [[One-Time-Pad]] wird meist unter Zuhilfenahme einer Exklusiv-Oder-Verknüpfung implementiert. Die zu verschlüsselnde Nachricht ([[Klartext (Kryptographie)|Klartext]]) wird dazu zuerst als Bitfolge kodiert. Eine zweite zufällige Bitfolge, die genauso lang wie die Nachricht ist, wird als [[Schlüssel (Kryptologie)|Schlüssel]] verwendet. Der [[Geheimtext]] entsteht, indem das erste Bit der Nachricht mit dem ersten Bit des Schlüssels exklusiv-oder-verknüpft wird, das zweite Bit mit dem zweiten und so weiter. Führt man anschließend die gleiche Exklusiv-Oder-Verknüpfung mit dem Geheimtext und dem Schlüssel aus, so erhält man wieder die ursprüngliche Nachricht.

==== Sicherheit ====
* Fällt einem Angreifer der Klartext und der Geheimtext in die Hand, kann er sehr einfach mittels Exklusiv-Oder-Verknüpfung den Schlüssel herausfinden und diesen bei weiteren Geheimtexten ausprobieren. Die Gewinnung des Schlüssels ist bei anderen Methoden (z.&nbsp;B. [[AES-256|AES]]) kaum möglich. Das spielt beim One-Time-Pad-Verfahren allerdings keine Rolle, da für jede Nachricht voneinander vollständig unabhängige Schlüssel verwendet werden.
* Angriff auf exklusiv-oder-verschlüsselte Daten, falls die Schlüssellänge kürzer ist als der Geheimtext:<ref>Bruce Schneier: ''Angewandte Kryptographie.'' 2006.</ref>
** Mit Exklusiv-Oder-Operationen wird der Geheimtext mit Geheimtext<sub>''n''</sub> verarbeitet, wobei Geheimtext<sub>''n''</sub> dem um ''n'' Bits nach rechts verschobenen Geheimtext entspricht. Wie viele Bits bleiben nach der Exklusiv-Oder-Operation jeweils dieselben? Die Schlüssellänge entspricht der Verschiebung&nbsp;''n'', bei der das Resultat von Geheimtext XOR Geheimtext<sub>''n''</sub> am stärksten dem Geheimtext ähnelt.
** Nun ist die Schlüssellänge ''n'' gefunden. Die Operation Geheimtext XOR Geheimtext<sub>''n''</sub> ergibt dasselbe Resultat wie Klartext XOR Klartext<sub>''n''</sub>. Denn es gilt:<ref name="KRACK">{{Internetquelle |autor=Jürgen Schmidt |url=https://www.heise.de/security/artikel/KRACK-so-funktioniert-der-Angriff-auf-WPA2-3865019.html |titel=KRACK – so funktioniert der Angriff auf WPA2 |werk=heise Security |hrsg=Heise Medien GmbH & Co. KG |datum=2017-10-19 |abruf=2017-10-24}}</ref>
::<math>\text{Geheimtext} \oplus \text{Geheimtext}_n = 
(\text{Klartext} \oplus \text{Schlüssel}) \oplus  (\text{Klartext}_n \oplus \text{Schlüssel}) = (\text{Klartext} \oplus \text{Schlüssel}) \oplus (\text{Schlüssel} \oplus \text{Klartext}_n)</math>
::<math>= \text{Klartext} \oplus (\text{Schlüssel} \oplus \text{Schlüssel}) \oplus \text{Klartext}_n = \text{Klartext} \oplus \text{Klartext}_n</math><br /> Es fällt in der Regel genügend Klartext an, um die Nachricht vollends zu entziffern. Denn es gilt:<ref name="KRACK" />
::<math>\text{Klartext} \oplus \text{Klartext}_n \oplus \text{Klartext}_n = \text{Klartext}</math>

* Weitaus einfacher gestaltet sich die Entschlüsselung, wenn der Schlüssel ''n'' Bits lang ist und im Klartext die gleichen Bits sich ''m''&nbsp;Mal wiederholen, wobei ''m'' ein Vielfaches von&nbsp;''n'' darstellt. Hier als Beispiel eine Wiederholung von Nullen; der Schlüssel ist <code>1010</code>. Da sich im verschlüsselten Text die Sequenz <code>1010</code> wiederholt, kann der Angreifer vermuten, dass der Klartext an dieser Stelle aus Nullen bestand und der Schlüssel <code>1010</code> war (oder der Geheimtext aus Einsen, und der Schlüssel war <code>0101</code>):
Klartext XOR Schlüssel → Geheimtext<br />
11111001'''000000000000''' XOR 10101010101010101010 → 01010011'''101010101010'''

Die Exklusiv-Oder-Verschlüsselung lässt sich aber entscheidend verbessern, indem aus einem kurzen Passwort ein genügend langer Schlüssel erzeugt wird. Ein Beispiel dafür ist die Verschlüsselung mittels [[RC4]], die aber mittlerweile als unsicher gilt. Sicherer, aber etwas langsamer ist die Verschlüsselung mit [[RC4#Spritz|Spritz]].

=== Prüfsummenbildung ===
<div class="float-right hintergrundfarbe2" style="margin-top:0; font-family:monospace,monospace; padding:0 .5em;">
<span style="color:#800000">0101</span> XOR <span style="color:#008000">1011</span> = <span style="color:#000080">1110</span><br />
<span style="color:#000080">1011</span> XOR <span style="color:#008000">1110</span> = <span style="color:#800000">0101</span><br />
<span style="color:#000080">0101</span> XOR <span style="color:#800000">1110</span> = <span style="color:#008000">1011</span>
</div>
Aus zwei Bitfolgen, angenommen <code>0101</code> und <code>1011</code>, wird mittels der Exklusiv-Oder-Verknüpfung die [[Paritätsbit|Parität]] gebildet: <code>1110</code> (erste Zeile im Beispiel rechts). Diese Parität muss zusammen mit den beiden Bitfolgen übertragen bzw. gespeichert werden. Geht nun die erste Bitfolge (<code>0101</code>) verloren, so kann sie wiederhergestellt werden, indem die zweite Bitfolge (<code>1011</code>) mit der Parität exklusiv-oder-verknüpft wird (zweite Zeile). Analog könnte die zweite Bitfolge wiederhergestellt werden (dritte Zeile). Dieser Mechanismus wird unter anderem auch bei [[RAID 5]] verwendet: Je zwei Datenblöcke (aus z.&nbsp;B. 512 Bytes) werden auf je eine Festplatte geschrieben. Auf eine dritte Platte wird die XOR-Verknüpfung der beiden ersten Blöcke geschrieben. Geht jetzt irgendeine der drei Festplatten kaputt, kann die Information vollständig aus den beiden anderen restauriert werden.

=== Frequenzverdopplung ===
[[Datei:Frequenzverdoppler mit XOR.png|mini|Frequenzverdopplung eines Rechtecksignals]]
Eine sehr einfache Frequenzverdopplung von [[Rechteckschwingung]]en im Frequenzbereich bis zu einigen 100&nbsp;MHz kann mit einem Exklusiv-Oder-Gatter erzielt werden, wenn ein Eingang unmittelbar und der andere mit einem geringfügig verzögerten Signal (in der Zeichnung durch ein RC-Glied dargestellt, denkbar sind aber auch Schaltungen beispielsweise mit [[Gatterlaufzeit]]en, wie etwa zwei Inverter) gespeist wird. Das Exklusiv-Oder-Gatter schaltet bei steigender und fallender Flanke; die entstehenden Nadelimpulse sind phasengebunden und etwa so kurz wie die eingesetzte Signalverzögerung. Da dieses Verfahren keine Resonanzfilter verwendet, kann das Eingangssignal fast beliebige [[Tastgrad|Tastverhältnisse]] besitzen bzw. stark [[Frequenzmodulation|frequenzmoduliert]] sein, allerdings ist im Allgemeinen kein Tastgrad von 50 % zu erreichen.

=== Schaltbarer Inverter ===
An einem Eingang liegt ein Signal an, der andere dient als Steuereingang. Liegt der Steuereingang auf logisch „0“, wird das Signal ohne Änderung durchgelassen. Liegt der Steuereingang auf logisch&nbsp;„1“, verhält sich das Gatter wie ein Inverter.

== CMOS-Realisierung ==
[[Datei:Cmos xor.svg|mini|Schaltbild in CMOS-Technik]]
Die zuvor gezeigte Realisierung aus Und- und Oder-Gattern benötigt in [[CMOS]]-Technik 16 Transistoren. Eine direkte Umsetzung (rechts) benötigt nur 12 Transistoren und mit Tricks, unter Einbußen bei der Geschwindigkeit, sechs Transistoren bzw. vier Transistoren. Zum Verständnis: T1+T2 und T3+T4 invertieren die Eingangssignale. Bei High-Potential an beiden Eingängen (A+B) leiten T7+T8 und ziehen den Ausgang Y auf Low-Potential. Sind beide Eingänge auf Low-Potential, leiten T11+T12, da vor beiden ein Inverter liegt, der das Eingangssignal umkehrt.

Eine Realisierung mittels [[AND-OR-Invert]]-Logik benötigt 10 Transistoren. Sie wurde beispielsweise beim [[Intel 80386]] verwendet.<ref>{{Cite web|url=http://www.righto.com/2023/12/386-xor-circuits.html|title=Two interesting XOR circuits inside the Intel 386 processor|language=en|author=Ken Shirrif}}</ref>
[[Datei:XOR with AOI logic in CMOS.svg|mini|CMOS-Implementierung mittels [[AND-OR-Invert]]-Logik]]

Weiterhin gibt es Implementierungen, die sowohl XOR wie NXOR als Ergebnis zur Verfügung stellen.

Ein so optimierter [[Volladdierer|Voll-Addierer]] benötigt nur noch 26 Transistoren (2&nbsp;×&nbsp;4 Transistoren für das Exklusiv-Oder der Summe, 3&nbsp;×&nbsp;4 Transistoren für das 2-fach-NAND und 1&nbsp;×&nbsp;6 Transistoren für das 3-fach-NAND für den Übertrag). Ein 64&nbsp;×&nbsp;64-bit-Multiplizierer lässt sich so als [[Schaltnetz]] mit knapp 140.000 Transistoren implementieren.

== Literatur ==
* {{BibISBN|3-540-42849-6}}
* {{Literatur
   |Autor=Klaus Beuth
   |Titel=Digitaltechnik
   |Auflage=10.
   |Verlag=Vogel
   |Datum=1998
   |ISBN=3-8023-1755-6}}
* {{Literatur
   |Autor=Manfred Seifart, Helmut Beikirch
   |Titel=Digitale Schaltungen
   |Auflage=5.
   |Verlag=Technik
   |Datum=1998
   |ISBN=3-341-01198-6}}

== Einzelnachweise ==
<references />

{{SORTIERUNG:XORGatter}}
[[Kategorie:Digitale Schaltungstechnik]]
[[Kategorie:Schaltalgebra]]

[[sv:Disjunktion (logik)#OR-grind och XOR-grind]]