HOME

TheInfoList



OR:

XOR gate (sometimes EOR, or EXOR and pronounced as Exclusive OR) is a digital
logic gate A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic ga ...
that gives a true (1 or HIGH) output when the number of true inputs is odd. An XOR gate implements an
exclusive or Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
(\nleftrightarrow) from
mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of forma ...
; 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 A power inverter, inverter or invertor is a power electronic device or circuitry that changes direct current (DC) to alternating current (AC). The resulting AC frequency obtained depends on the particular device employed. Inverters do the opp ...
(a NOT gate) which may be activated or deactivated by a switch. XOR can also be viewed as addition
modulo In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation). Given two positive numbers and , modulo (often abbreviated as ) is ...
2. As a result, XOR gates are used to implement binary addition in computers. A half adder consists of an XOR gate and an
AND gate The AND gate is a basic digital logic gate that implements logical conjunction (∧) from mathematical logic AND gate behaves according to the truth table. A HIGH output (1) results only if all the inputs to the AND gate are HIGH (1). If not al ...
. The gate is also used in subtractors and
comparators In electronics, a comparator is a device that compares two voltages or currents and outputs a digital signal indicating which is larger. It has two analog input terminals V_+ and V_- and one binary digital output V_\text. The output is ideally : ...
. The algebraic expressions A \cdot \overline + \overline \cdot B or (A + B) \cdot (\overline A + \overline B) or A \oplus B all represent the XOR gate with inputs ''A'' and ''B''. The behavior of XOR is summarized in the
truth table A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arg ...
shown on the right.


Symbols

There are three schematic symbols for XOR gates: the traditional ANSI and DIN symbols and the
IEC The International Electrotechnical Commission (IEC; in French: ''Commission électrotechnique internationale'') is an international standards organization that prepares and publishes international standards for all electrical, electronic and r ...
symbol. In some cases, the DIN symbol is used with ⊕ instead of ≢. For more information see Logic Gate Symbols. The logic symbols ⊕, J''pq'', and ⊻ can be used to denote an XOR operation in algebraic expressions. C-like languages use the
caret Caret is the name used familiarly for the character , provided on most QWERTY keyboards by typing . The symbol has a variety of uses in programming and mathematics. The name "caret" arose from its visual similarity to the original proofreade ...
symbol ^ to denote bitwise XOR. (Note that the caret does not denote
logical conjunction In logic, mathematics and linguistics, And (\wedge) is the truth-functional operator of logical conjunction; the ''and'' of a set of operands is true if and only if ''all'' of its operands are true. The logical connective that represents thi ...
(AND) in these languages, despite the similarity of symbol.)


Implementation

The XOR gate is most commonly implemented using
MOSFET The metal–oxide–semiconductor field-effect transistor (MOSFET, MOS-FET, or MOS FET) is a type of field-effect transistor (FET), most commonly fabricated by the controlled oxidation of silicon. It has an insulated gate, the voltage of which d ...
s circuits. Some of those implementations include:


CMOS

The Complementary metal–oxide–semiconductor (
CMOS Complementary metal–oxide–semiconductor (CMOS, pronounced "sea-moss", ) is a type of metal–oxide–semiconductor field-effect transistor (MOSFET) fabrication process that uses complementary and symmetrical pairs of p-type and n-type MOSF ...
) implementation of the XOR gate. The nMOS and pMOS transistors are arranged so that the input pairs A \cdot \overline and \overline \cdot B 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 A \cdot B and \overline \cdot \overline activate each one of the two nMOS paths in the bottom to Vss for a logic low. This is a twelve transistor implementation since two additional inverters with two gates each, not shown in the diagram, are needed to generate \overline and \overline.


Transmission gates

The XOR gate can also be implemented by the use of Transmission gates with pass transistor logic. This implementation uses two Transmission gates and two inverters not shown in the diagram to generate \overline and \overline 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 \overline 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. The trade-off with the previous implementation is that since transmission gates are not an ideal switches, there is resistance associated with them, so depending on the signal strength of the input, cascading them may degrade the output levels.


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 \overline and the bottom pass-gate with just two transistors arranged like an inverter but with the source of the pMOS connected to B instead of Vdd and the source of the nMOS connected to \overline instead of GND. 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 \overline used by the transmission gate and the pass transistor logic circuit. As with the previous implementation, the direct connection of the inputs to the outputs through the pass gate transistors or thru the two leftmost transistors, should be taken into account, specially when cascading them.


Alternatives

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 (A \cdot \overline) + (\overline \cdot B), we can construct an XOR gate circuit directly using AND, OR and NOT gates. However, this approach requires five gates of three different kinds. As alternative, if different gates are available we can apply
Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
to transform (A \cdot \overline) + (\overline \cdot B) \equiv (A + B) \cdot ( \overline A + \overline B ) as stated above, and apply de Morgan's Law to the last term to get (A + B) \cdot \overline which can be implemented using only three 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 digital electronics, a NAND gate (NOT-AND) is a logic gate which produces an output which is false only if all its inputs are true; thus its output is complement to that of an AND gate. A LOW (0) output results only if all the inputs to the ...
. 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 In digital electronics, a NAND gate (NOT-AND) is a logic gate which produces an output which is false only if all its inputs are true; thus its output is complement to that of an AND gate. A LOW (0) output results only if all the inputs to the ...
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 The NOR gate is a digital logic gate that implements logical NOR - it behaves according to the truth table to the right. A HIGH output (1) results if both the inputs to the gate are LOW (0); if one or both input is HIGH (1), a LOW output (0 ...
). An alternative arrangement is of five NOR gates in a topology that emphasizes the construction of the function from (A + B) \cdot ( \overline A + \overline B ), noting from de Morgan's Law that a
NOR gate The NOR gate is a digital logic gate that implements logical NOR - it behaves according to the truth table to the right. A HIGH output (1) results if both the inputs to the gate are LOW (0); if one or both input is HIGH (1), a LOW output (0 ...
is an inverted-input
AND gate The AND gate is a basic digital logic gate that implements logical conjunction (∧) from mathematical logic AND gate behaves according to the truth table. A HIGH output (1) results only if all the inputs to the AND gate are HIGH (1). If not al ...
. Another alternative arrangement is of five
NAND gates In digital electronics, a NAND gate (NOT-AND) is a logic gate which produces an output which is false only if all its inputs are true; thus its output is complement to that of an AND gate. A LOW (0) output results only if all the inputs to the ...
in a topology that emphasizes the construction of the function from (A \cdot \overline) + (\overline \cdot B), noting from de Morgan's Law that a
NAND gate In digital electronics, a NAND gate (NOT-AND) is a logic gate which produces an output which is false only if all its inputs are true; thus its output is complement to that of an AND gate. A LOW (0) output results only if all the inputs to the ...
is an inverted-input
OR gate The OR gate is a digital logic gate that implements logical disjunction. The OR gate returns true if either or both of its inputs are true; otherwise it returns false. The input and output states are normally represented by different voltage lev ...
. 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

XOR chips are readily available. The most common standard chip codes are: *4070: CMOS quad dual input XOR gates. *4030: CMOS quad dual input XOR gates. *7486:
TTL TTL may refer to: Photography * Through-the-lens metering, a camera feature * Zenit TTL, an SLR film camera named for its TTL metering capability Technology * Time to live, a computer data lifespan-limiting mechanism * Transistor–transistor lo ...
quad dual input XOR gates.


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. 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 In digital circuits and machine learning, a one-hot is a group of bits among which the legal combinations of values are only those with a single high (1) bit and all the others low (0). A similar implementation in which all bits are '1' except ...
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 generator or a modulo-2 adder. For example, the 74LVC1G386 microchip is advertised as a three-input logic gate, and implements a parity generator.74LVC1G386
data sheet


Applications

XOR gates and AND gates are the two most-used structures in VLSI applications.


Uses in addition

The XOR logic gate can be used as a one-bit adder that adds any two bits together to output one bit. For example, if we add 1 plus 1 in binary, we expect a two-bit answer, 10 (i.e. 2 in decimal). Since the trailing ''sum'' bit in this output is achieved with XOR, the preceding ''carry'' bit is calculated with an
AND gate The AND gate is a basic digital logic gate that implements logical conjunction (∧) from mathematical logic AND gate behaves according to the truth table. A HIGH output (1) results only if all the inputs to the AND gate are HIGH (1). If not al ...
. This is the main principle in Half Adders. A slightly larger
Full Adder An adder, or summer, is a digital circuit that performs addition of numbers. In many computers and other kinds of processors adders are used in the arithmetic logic units (ALUs). They are also used in other parts of the processor, where they are ...
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 The OR gate is a digital logic gate that implements logical disjunction. The OR gate returns true if either or both of its inputs are true; otherwise it returns false. The input and output states are normally represented by different voltage lev ...
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

Pseudo-random number (PRN) generators, specifically
linear-feedback shift register In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. The most commonly used linear function of single bits is exclusive-or (XOR). Thus, an LFSR is most often a ...
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.


Correlation and sequence detection

XOR gates produce a 0 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 0 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 Code-division multiple access (CDMA) is a channel access method used by various radio communication technologies. CDMA is an example of multiple access, where several transmitters can send information simultaneously over a single communicatio ...
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 11010 in the data sequence 1110100101 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.


Phase detectors

XOR gates may be used in simplest
phase detector A phase detector or phase comparator is a frequency mixer, analog multiplier or logic circuit that generates a signal which represents the difference in phase between two signal inputs. The phase detector is an essential element of the phase- ...
s.


Analytical representation

f(a,b)=a+b-2ab is an analytical representation of XOR gate: * f(0,0)=0+0-2\cdot 0\cdot 0=0 * f(0,1)=0+1-2\cdot 0\cdot 1=1 * f(1,0)=1+0-2\cdot 1\cdot 0=1 * f(1,1)=1+1-2\cdot 1\cdot 1=0 f(a,b)=, a-b, is an alternative analytical representation.


See also

*
Exclusive or Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
*
AND gate The AND gate is a basic digital logic gate that implements logical conjunction (∧) from mathematical logic AND gate behaves according to the truth table. A HIGH output (1) results only if all the inputs to the AND gate are HIGH (1). If not al ...
*
OR gate The OR gate is a digital logic gate that implements logical disjunction. The OR gate returns true if either or both of its inputs are true; otherwise it returns false. The input and output states are normally represented by different voltage lev ...
* Inverter (NOT gate) *
NAND gate In digital electronics, a NAND gate (NOT-AND) is a logic gate which produces an output which is false only if all its inputs are true; thus its output is complement to that of an AND gate. A LOW (0) output results only if all the inputs to the ...
*
NOR gate The NOR gate is a digital logic gate that implements logical NOR - it behaves according to the truth table to the right. A HIGH output (1) results if both the inputs to the gate are LOW (0); if one or both input is HIGH (1), a LOW output (0 ...
* XNOR gate *
IMPLY gate The IMPLY gate is a digital logic gate that implements a logical conditional pictured with a right-facing arrow (\rightarrow). F=A'+B ( Implication) Logic_gate_symbols. The_List_of_logic_symbols.html" ;"title="Logic_gate#Symbols.html" ;" ...
*
Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
*
Logic gate A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic ga ...


References

{{DEFAULTSORT:Xor Gate Logic gates sv:Disjunktion (logik)#OR-grind och XOR-grind