View source for XOR gate

{{Short description|Logic gate}}
{{About|XOR digital logic gate (e.g. SN7486 or CD4030B)|XOR logical operation|Exclusive or|other uses|XOR (disambiguation)}}
{| class="wikitable floatright" style="text-align:center"
|+ {{nowrap|XOR gate [[truth table]]}}
|- bgcolor="#ddeeff"
|colspan=2|'''Input''' || '''Output'''
|- bgcolor="#ddeeff"
| A || B || A XOR B
|-
|{{no2|0}} || {{no2|0}} || {{no2|0}}
|-
|{{no2|0}} || {{yes2|1}} || {{yes2|1}}
|-
|{{yes2|1}} || {{no2|0}} || {{yes2|1}}
|-
|{{yes2|1}} || {{yes2|1}} || {{no2|0}}
|}

'''XOR gate''' (sometimes '''EOR''', or '''EXOR''' and pronounced as '''Exclusive OR''') is a digital [[logic gate]] that gives a true (1 or HIGH) output when the number of true inputs is odd. An XOR gate implements an [[exclusive disjunction|exclusive or]] (<math>\nleftrightarrow</math>) from [[mathematical logic]]; that is, a true output results if one, and only one, of the inputs to the gate is true. If both inputs are false (0/LOW) or both are true, a false output results. XOR represents the inequality function, i.e., the output is true if the inputs are not alike otherwise the output is false. A way to remember XOR is "must have one or the other but not both".

An XOR gate may serve as a "programmable inverter" in which one input determines whether to invert the other input, or to simply pass it along with no change. Hence it functions as a [[Inverter (logic gate)|inverter]] (a NOT gate) which may be activated or deactivated by a switch.<ref>{{cite book |title=Practical Programmable Circuits: A Guide to PLDs, State Machines, and Microcontrollers |first=James D. |last=Broesch |year=2012 |page=20 |publisher=Elsevier Science |isbn=978-0323139267 |url=https://books.google.com/books?id=I7-v5CBVmfIC&pg=PA20 }}</ref><ref>{{cite book |url=https://github.com/crypto101/crypto101.github.io/raw/master/Crypto101.pdf |first=Laurens |last=Van Houtven |year=2017 |title=Crypto 101 |page=17 }}</ref>

XOR can also be viewed as addition [[Modular arithmetic|modulo]] 2. As a result, XOR gates are used to implement binary addition in computers.  A [[Adder (electronics)#Half adder|half adder]] consists of an XOR gate and an [[AND gate]]. The gate is also used in [[subtractor]]s and [[Digital comparator|comparators]].<ref>{{cite book|last1=Fletcher|first1=William|title=An engineering approach to digital design|date=1980|publisher=Prentice-Hall|isbn=0-13-277699-5|page=[https://archive.org/details/engineeringappro00fle_wur/page/98 98]|url-access=registration|url=https://archive.org/details/engineeringappro00fle_wur/page/98}}</ref>

The [[Boolean algebra|algebraic expressions]] <math>A \cdot \overline{B} + \overline{A} \cdot B</math> or <math>(A + B) \cdot (\overline A + \overline B)</math> or <math>(A + B) \cdot \overline{(A \cdot B)}</math> or <math>A \oplus B</math> all represent the XOR gate with inputs ''A'' and ''B''. The behavior of XOR is summarized in the [[truth table]] shown on the right.

==Symbols==
There are three schematic symbols for XOR gates: the traditional ANSI and DIN symbols and the [[International Electrotechnical Commission|IEC]] symbol. In some cases, the DIN symbol is used with ⊕ instead of ≢. For more information see [[Logic gate#Symbols|Logic Gate Symbols]].

The "=1" on the IEC symbol indicates that the output is activated by only one active input.

{|  style="margin:auto; text-align:center;"
|-
|[[Image:XOR ANSI.svg|class=skin-invert]]
|
|[[Image:XOR IEC.svg|class=skin-invert]]
|
|[[Image:XOR DIN.svg|class=skin-invert]]
|-
|''ANSI XOR Schematic Symbol''&nbsp;&nbsp;&nbsp;
|
|''IEC XOR Schematic Symbol''&nbsp;&nbsp;&nbsp;
|
|''DIN XOR Schematic Symbol''
|}
{{Clear}}

The [[List of logic symbols|logic symbols]] ⊕, [[exclusive or|J''pq'']], and ⊻ can be used to denote an XOR operation in algebraic expressions.

[[List of C-family programming languages|C-like languages]] use the [[Caret#Programming languages|caret]] symbol <code>^</code> to denote bitwise XOR. (Note that the caret does not denote [[logical conjunction]] (AND) in these languages, despite the similarity of symbol.)

==Implementation==
The XOR gate is most commonly implemented using [[MOSFET]]s circuits. Some of those implementations include:

===AND-OR-Invert===
XOR gates can be implemented using AND-OR-Invert ([[AND-OR-Invert|AOI]]) or OR-AND-Invert ([[OR-AND-invert|OAI]]) logic.<ref>{{Cite web |url=https://sus.ziti.uni-heidelberg.de/Lehre/WS1617_DST/DST_Fischer_03_Logik_Gatter.pptx.pdf |title=Aussagenlogik und Gatter |access-date=2024-01-21 |last=Fischer |first=P. |publisher=University of Heidelberg}}</ref>
<gallery widthds="300" heights="225" class="skin-invert-image">
XOR AOI logic gates.svg|An XOR gate using a 2-1 AOI gate.
XOR gate based on 2-2 AOI gate.svg|An XOR gate using a 2-2 OAI gate and negated inputs.
</gallery>

===CMOS===
The  metal–oxide–semiconductor ([[CMOS]]) implementations of the XOR gate corresponding to the AOI logic above
are shown below.

On the left, the [[Field-effect transistor#n-channel FET|nMOS]] and [[Field-effect transistor#p-channel FET|pMOS]] transistors are arranged so that the input pairs <math>A \cdot \overline{B}</math> and <math>\overline{A} \cdot B</math> activate the 2 pMOS transistors of the top left or the 2 pMOS transistors of the top right respectively, connecting Vdd to the output for a logic high. The remaining input pairs <math>A \cdot B</math> and <math>\overline{A} \cdot \overline{B}</math> activate each one of the two nMOS paths in the bottom to Vss for a logic low.<ref>{{cite book |last1=Pedroni |first1=Volnei A. |title=Digital Electronics and Design with VHDL |date=25 January 2008 |publisher=Morgan Kaufmann |isbn=978-0-08-055755-7 |url=https://books.google.com/books?id=-ZAccwyQeXMC&pg=PA82 |access-date=8 November 2022 |language=en}}</ref>

If inverted inputs (for example from a [[Flip-flop (electronics)|flip-flop]]) are available, this gate can be used directly. Otherwise, two additional inverters with two transistors each are needed to generate <math>\overline{A}</math> and <math>\overline{B}</math>, bringing the total number of transistors to twelve.

The AOI implementation without inverted input has been used, for example, in the [[i386|Intel 386]] CPU.<ref>{{Cite web |url=http://www.righto.com/2023/12/386-xor-circuits.html |title=Two interesting XOR circuits inside the Intel 386 processor |access-date=2024-01-14 |last=Shiriff |first=Ken}}</ref>

<gallery widthds="300" heights="225" class="skin-invert-image">
CMOS XOR Gate.svg|Example of CMOS XOR gate
XOR_with_AOI_logic_in_CMOS.svg|CMOS XOR gate using AOI-Logic
</gallery>

===Transmission gates===
The XOR gate can also be implemented through the use of [[transmission gate]]s with [[pass transistor logic]].

[[File:XOR gate implemented with pass gates.svg|thumb|300px|center|Transmission gate implementation of XOR gate|class=skin-invert-image]]

This implementation uses two Transmission gates and two inverters not shown in the diagram to generate <math>\overline{A}</math> and <math>\overline{B}</math> for a total of eight transistors, four less than in the previous design. 
The XOR function is implemented by passing through to the output the inverted value of A when B is high and passing the value of A when B is at a logic low. so when both inputs are low the transmission gate at the bottom is off and the one at the top is on and lets A through which is low so the output is low. When both are high only the one at the bottom is active and lets the inverted value of A through and since A is high the output will again be low. Similarly if B stays high but A is low the output would be <math>\overline{A}</math> which is high as expected and if B is low but A is high the value of A passes through and the output is high completing the truth table for the XOR gate.<ref>{{cite book |last1=Oklobdzija |first1=Vojin G. |title=The Computer Engineering Handbook |date=26 December 2001 |publisher=CRC Press |isbn=978-0-8493-0885-7 |url=https://books.google.com/books?id=38Aj3CjHgc8C&pg=SA2-PA8 |access-date=8 November 2022 |language=en}}</ref>

The trade-off with the previous implementation is that since transmission gates are not ideal switches, there is resistance associated with them, so depending on the signal strength of the input, cascading them may degrade the output levels.<ref name=logicgates />

===Optimized pass-gate-logic wiring===
The previous transmission gate implementation can be further optimized from eight to six transistors by implementing the functionality of the inverter that generates <math>\overline{A}</math> and the bottom pass-gate with just two transistors arranged like an inverter but with the source of the pMOS connected to <math>B</math> instead of [[IC power-supply pin|Vdd]] and the source of the nMOS connected to <math>\overline{B}</math> instead of GND.<ref name=logicgates>{{cite book |title=Designing combinational logic gates in CMOS |page=233 |url=http://bwrcs.eecs.berkeley.edu/Classes/ic541ca/ic541ca_f01/Notes/chapter6.pdf |access-date=9 November 2022}}</ref>

[[File:CmosXORGate.png|thumb|300px|center|Optimized transmission Gate Logic wiring of an XOR gate|class=skin-invert-image]]

The two leftmost transistors mentioned above, perform an optimized conditional inversion of A when B is at a logic high using pass transistor logic to reduce the transistor count and when B is at a logic low, their output is at a high impedance state. The two in the middle are a [[transmission gate]] that drives the output to the value of A when B is at a logic low and the two rightmost transistors form an inverter needed to generate <math>\overline{B}</math> used by the transmission gate and the pass transistor logic circuit.<ref>{{cite book |last1=Annaratone |first1=Silvia |title=Digital CMOS Circuit Design |date=6 December 2012 |publisher=Springer Science & Business Media |isbn=978-1-4613-2285-6 |url=https://books.google.com/books?id=itPcBwAAQBAJ&pg=PA98 |access-date=8 November 2022 |language=en}}</ref>

As with the previous implementation, the direct connection of the inputs to the outputs through the pass gate transistors or through the two leftmost transistors, should be taken into account, especially when cascading them.</ref>
===XOR with AND and NOR===
[[File:ANDNOR XOR Gate implementation.png|thumb|300px|center|XOR Gate with 1 [[AND Gate]] and 2 [[NOR Gate]]s]]
Replacing the second NOR with a normal [[OR Gate]] will create an [[XNOR Gate]]. 
<ref name=logicgates />

==Alternatives==
[[File:254px 3gate XOR.jpg|thumb|right|XOR gate circuit using three mixed gates|class=skin-invert-image]]
If a specific type of gate is not available, a circuit that implements the same function can be constructed from other available gates. A circuit implementing an XOR function can be trivially constructed from an [[XNOR gate]] followed by a [[NOT gate]]. If we consider the expression <math>(A \cdot \overline{B}) + (\overline{A} \cdot B)</math>, we can construct an XOR gate circuit directly using AND, OR and [[Inverter (logic gate)|NOT gates]]. However, this approach requires five gates of three different kinds.

As alternative, if different gates are available we can apply [[Boolean algebra]] to transform <math>(A \cdot \overline{B}) + (\overline{A} \cdot B) \equiv (A + B) \cdot ( \overline A + \overline B )</math> as stated above, and apply [[de Morgan's Law]] to the last term to get <math>(A + B) \cdot \overline {(A \cdot B)} </math> which can be implemented using only four gates as shown on the right. intuitively, XOR is equivalent to OR except for when both A and B are high. So the AND of the OR with then NAND that gives a low only when both A and B are high is equivalent to the XOR.

An XOR gate circuit can be made from four [[NAND gates]]. In fact, both NAND and [[NOR gates]] are so-called "universal gates" and any logical function can be constructed from either [[NAND logic]] or [[NOR logic]] alone. If the four [[NAND gates]] are replaced by [[NOR gates]], this results in an [[XNOR gate]], which can be converted to an XOR gate by inverting the output or one of the inputs (e.g. with a fifth [[NOR gate]]).

{|  style="margin:auto; text-align:center;" class="skin-invert-image"
|-
! width="250" |Desired gate!!width=150|NAND construction!!width=150|NOR construction
|-
|[[Image:XOR ANSI Labelled.svg]]||[[File:XOR from NAND.svg]]||[[File:XOR from NOR 2.svg]]
|}

An alternative arrangement is of five [[NOR gates]] in a topology that emphasizes the construction of the function from <math>(A + B) \cdot ( \overline A + \overline B )</math>, noting from [[de Morgan's Law]] that a [[NOR gate]] is an inverted-input [[AND gate]]. Another alternative arrangement is of five [[NAND gates]] in a topology that emphasizes the construction of the function from <math>(A \cdot \overline{B}) + (\overline{A} \cdot B)</math>, noting from [[de Morgan's Law]] that a [[NAND gate]] is an inverted-input [[OR gate]].

{|  style="margin:auto; text-align:center;" class="skin-invert-image"
|-
! width="250" |Desired gate!!width=150|NAND construction!!width=150|NOR construction
|-
| rowspan="2" |[[Image:XOR ANSI Labelled.svg]]||[[File:XOR from NAND 2.svg]]||[[File:XOR from NOR.svg]]
|}

For the NAND constructions, the upper arrangement requires fewer gates. For the NOR constructions, the lower arrangement offers the advantage of a shorter propagation delay (the time delay between an input changing and the output changing).

==Standard chip packages==
[[File:DOV-1X - Philips HEF4070BP on printed circuit board-9802.jpg|thumb|right|Philips 4070 quad dual input XOR chip on printed circuit board]]
XOR chips are readily available. The most common standard chip codes are:

*4070: CMOS quad dual input XOR gates.<ref name="digitalsystems">{{cite book |last1=Ferdjallah |first1=Mohammed |title=Introduction to Digital Systems: Modeling, Synthesis, and Simulation Using VHDL |date=15 June 2011 |publisher=John Wiley & Sons |isbn=978-1-118-00770-9 |page=38 |url=https://books.google.com/books?id=kJRoR8AAu1AC&pg=PA38 |access-date=9 November 2022 |language=en}}</ref>
*4030: CMOS quad dual input XOR gates.<ref>{{cite book |last1=Ross |first1=Dickon |last2=Lowe |first2=Doug |title=Electronics All-in-One For Dummies - UK |date=24 September 2013 |publisher=John Wiley & Sons |isbn=978-1-118-58971-7 |page=647 |url=https://books.google.com/books?id=SXkBAQAAQBAJ&pg=PT647 |access-date=9 November 2022 |language=en}}</ref>
*7486: [[Transistor–transistor logic|TTL]] quad dual input XOR gates.<ref name="digitalsystems" />

==More than two inputs==
Literal interpretation of the name "exclusive or", or observation of the IEC rectangular symbol, raises the question of correct behaviour with additional inputs.<ref>{{Cite web | url=https://www.edn.com/the-xor-versus-sum-modulo-2 | title=The "XOR" versus "Sum modulo 2" | website=www.edn.com | first=Michael A. | last=Shustov | date=2023-07-04 }}</ref>  If a logic gate were to accept three or more inputs and produce a true output if exactly one of those inputs were true, then it would in effect be a [[one-hot]] detector (and indeed this is the case for only two inputs).  However, it is rarely implemented this way in practice.

It is most common to regard subsequent inputs as being applied through a cascade of binary exclusive-or operations: the first two signals are fed into an XOR gate, then the output of that gate is fed into a second XOR gate together with the third signal, and so on for any remaining signals.  The result is a circuit that outputs a 1 when the number of 1s at its inputs is odd, and a 0 when the number of incoming 1s is even.  This makes it practically useful as a [[parity (telecommunication)|parity generator]] or a modulo-2 [[adder (electronics)|adder]].

For example, the [[List of 7400 series integrated circuits|74LVC1G386]] microchip is advertised as a three-input logic gate, and implements a parity generator.<ref name="74LVC1G386">[http://www.nxp.com/documents/data_sheet/74LVC1G386.pdf 74LVC1G386] {{Webarchive|url=https://web.archive.org/web/20091229193456/http://www.nxp.com/documents/data_sheet/74LVC1G386.pdf |date=2009-12-29 }} [[data sheet]]</ref>

==Applications==
XOR gates and AND gates are the two most-used structures in [[Very Large Scale Integration|VLSI]] applications.<ref>{{cite web |url=https://www.researchgate.net/publication/266678826| title=Comparison of different design techniques of XOR & AND gate using EDA simulation tool|quote=XOR & AND gates are most important basic building blocks of any VLSI applications.}}</ref>

===Addition===
{{stack|[[File:Full-adder_logic_diagram.svg|right|thumb|Example full [[adder (electronics)|adder]]|class=skin-invert-image]]}}
{{stack|[[File:Half Adder.svg|right|frame|Example half [[adder (electronics)|adder]]|class=skin-invert-image]]}}
The XOR logic gate can be used as a one-bit [[adder (electronics)|adder]] that adds any two bits together to output one bit. For example, if we add <code>1</code> plus <code>1</code> in [[Binary numeral system|binary]], we expect a two-bit answer, <code>10</code> (i.e. <code>2</code> in decimal). Since the trailing ''sum'' bit in this output is achieved with XOR, the preceding ''carry'' bit is calculated with an [[AND gate]]. This is the main principle in [[Adder (electronics)#Half adder|Half Adders]]. A slightly larger [[Adder (electronics)#Full adder|Full Adder]] circuit may be chained together in order to add longer binary numbers.

In certain situations, the inputs to an OR gate (for example, in a full-adder) or to an XOR gate can never be both 1's. As this is the only combination for which the OR and XOR gate outputs differ, an [[OR gate]] may be replaced by an XOR gate (or vice versa) without altering the resulting logic. This is convenient if the circuit is being implemented using simple integrated circuit chips which contain only one gate type per chip.

===Pseudo-random number generator===
[[File:LFSR-G16.svg|thumb|right|393 px|Example 16-bit Galois [[Linear-feedback shift register|LFSR]] pseudo-random number generator|class=skin-invert-image]]
[[Pseudorandom number generator|Pseudo-random number (PRN) generators]], specifically [[linear-feedback shift register]]s (LFSR), are defined in terms of the exclusive-or operation. Hence, a suitable setup of XOR gates can model a linear-feedback shift register, in order to generate random numbers.

===Phase detectors===
XOR gates may be used in simplest [[phase detector]]s.<ref>{{cite book |last=Rabaey |first=Jan M. |title=Digital integrated circuits : a design perspective |publisher=Prentice-Hall |year=1996 |isbn=978-0-13-178609-7 |location=Upper Saddle River, N.J. |page=}}</ref>{{Rp|page=425}}

===Buffer or invert a signal===
An XOR gate may be used to easily change between buffering or inverting a signal.  For example, XOR gates can be added to the output of a [[seven-segment display]] [[Seven-segment display#Decoder ICs|decoder circuit]] to allow a user to choose between active-low or active-high output.

===Correlation and sequence detection===
XOR gates produce a <code>0</code> when both inputs match.  When searching for a specific bit pattern or PRN sequence in a very long data sequence, a series of XOR gates can be used to compare a string of bits from the data sequence against the target sequence in parallel.  The number of <code>0</code> outputs can then be counted to determine how well the data sequence matches the target sequence.  Correlators are used in many communications devices such as [[CDMA]] receivers and decoders for error correction and channel codes.  In a CDMA receiver, correlators are used to extract the polarity of a specific PRN sequence out of a combined collection of PRN sequences.

A correlator looking for <code>11010</code> in the data sequence <code>1110100101</code> would compare the incoming data bits against the target sequence at every possible offset while counting the number of matches (zeros):

 1110100101 (data)
 11010      (target)
 00111      (XOR) 2 zero bits
 
 1110100101
  11010
  00000     5 zero bits
 
 1110100101
   11010
   01110    2 zero bits
 
 1110100101
    11010
    10011   2 zero bits
 
 1110100101
     11010
     01000  4 zero bits
 
 1110100101
      11010
      11111 0 zero bits
 
 Matches by offset:
 
   .
   :     :
 : : : : :  
 -----------
 0 1 2 3 4 5

In this example, the best match occurs when the target sequence is offset by 1 bit and all five bits match.  When offset by 5 bits, the sequence exactly matches its inverse.  By looking at the difference between the number of ones and zeros that come out of the bank of XOR gates, it is easy to see where the sequence occurs and whether or not it is inverted.  Longer sequences are easier to detect than short sequences.

== Analytical representation ==
<math>f(a,b)=a+b-2ab</math> is an analytical representation of XOR gate:
* <math>f(0,0)=0+0-2\cdot 0\cdot 0=0</math>
* <math>f(0,1)=0+1-2\cdot 0\cdot 1=1</math>
* <math>f(1,0)=1+0-2\cdot 1\cdot 0=1</math>
* <math>f(1,1)=1+1-2\cdot 1\cdot 1=0</math>

<math>f(a,b)=|a-b|</math> is an alternative analytical representation.

==See also==
{{Commons category|XOR gates}}
{{div col}}
*[[Exclusive or]]
*[[AND gate]]
*[[OR gate]]
*[[Inverter (logic gate)|Inverter (NOT gate)]]
*[[NAND gate]]
*[[NOR gate]]
*[[XNOR gate]]
*[[IMPLY gate]]
*[[Boolean algebra]]
*[[Logic gate]]
{{div col end}}

==References==
{{Reflist}}

{{Logical connectives}}

{{Improve categories|date=May 2021}}

{{DEFAULTSORT:Xor Gate}}
[[Category:Logic gates]]

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