39

I've just started studying computer engineering, and I'm having some doubts regarding the behavior of the XOR gate.

I've been projecting circuits with Logisim, whose XORs behave differently from what I've learnt. To me, it should behave as a parity gate, giving a high output whenever the inputs receives an odd combination. It doesn't, though, for more than two inputs. How should it behave?

I also read in a book that XOR gates are not produced with more than two inputs. Is that correct? Why?

uniquenamehere
  • 850
  • 1
  • 9
  • 21
gabrieljcs
  • 614
  • 1
  • 5
  • 7
  • 1
    Why not (or almost never) with >2 inputs? Two typical uses of XOR gates are 1) to check for equality, and 2) to control/manipulate the polarity of a signal. Neither makes sense for more than 2 inputs. – Wouter van Ooijen Dec 14 '13 at 22:38
  • 1
    Wouldn't the sum in a full-adder be represented as A ^ B ^ Cin? – gabrieljcs Dec 14 '13 at 23:50
  • You can express it that way, but that does not mean that it is a good way to implement it. – Wouter van Ooijen Dec 15 '13 at 08:49
  • 1
    Just checked my version of Logisim, and the "1 and only 1" appears to be the default behavior but there is the option to change it to an odd-parity function. – Joe Hass Dec 15 '13 at 22:36
  • Indeed, Joe. [This link](http://sourceforge.net/p/circuit/discussion/479544/thread/e874d0a7/) has a discussion regarding that, answered by Logisim's developer, Carl Burch. – gabrieljcs Dec 16 '13 at 16:58
  • XOR checks for parity of the number. It returns low when number is pair and high when number is odd. The inverse with XNOR. – lucas92 May 04 '16 at 15:30

7 Answers7

33

There are different points of view regarding how an exclusive-OR gate with more than two inputs should behave. Most often such an XOR gate behaves like a cascade of 2-input gates and performs an odd-parity function. However, some people interpret the meaning of exclusive-OR more literally and say that the output should be a 1 if and only if exactly one of the inputs is a 1. I do seem to recall that Logisim uses the latter interpretation, and somewhere in my rusty memory I have seen it in an ASIC cell library. One of the the international standard symbols for an XOR gate is a rectangle labelled with =1 which seems to be more consistent with the "1 and only 1" definition.

EDIT: The definition of exclusive-OR as "1 and only 1" is uncommon but it can be found. For example, IEEE-Std91a-1991 gives the symbol for the exclusive-OR on p. 62 with the note: "The output stands at its 1-state if one and only one of the two inputs stands at its 1-state." For more than 2 inputs the standard recommends using the "odd parity" symbol instead. Web sites that discuss this confusing situation include XOR: The Interesting Gate and gate demos at TAMS. A google search will also turn up sites that claim that, strictly speaking, there is no such thing as an XOR gate with more than two inputs.

Joe Hass
  • 8,447
  • 1
  • 29
  • 41
  • 7
    As far as I'm concerned, the second one (1 and only 1) is the only correct way to do this - anything else isn't really *exclusive*. – Polynomial Dec 14 '13 at 23:37
  • 4
    There is no different point of view, both points are technically correct, however "1 if only if exactly one of the inputs is a 1" doesn't expand as you might think. When you cascade 2input XORs, each output feeding in to the pins of a third XOR this shows the above point. Multi-input gates are derived from their 2input primitives. Thus the 4input truth table is ((A⊕B)⊕(C⊕D)) which results in a final 1 output if there are an odd number of true inputs. – Kris Bahnsen Dec 15 '13 at 21:39
  • @KrisBahnsen As the OP pointed out, there are indeed two points of view (try the default XOR in Logisim if you need evidence). Your assertion that multi-input gates are derived from 2-input primitives is given as though it is universal truth but we have already given you a counter-example. – Joe Hass Dec 15 '13 at 22:34
  • @JoeHass, I've never used logisim, I primarily use LogicWorks; in which, a multi-input XOR behaves as I described above, odd number of true inputs is a true output. The wiki page on XOR (en.wikipedia.org/wiki/XOR) agrees that what I said is true as well. I also have never actually seen a multi-input XOR IC, so I cannot turn to datasheets to try and disprove what I said. Logisim seems to be the only thing that implements the multi-input XOR scheme with the logic "1 if and only..." If you can find another source, I will admit I am wrong and that there are multiple definitions of XOR. – Kris Bahnsen Dec 15 '13 at 23:30
  • Good clarification, thank you for putting the time in on researching the standards far more than I had. – Kris Bahnsen Dec 16 '13 at 07:53
  • @Polynomial: One could just as well say "at least one but not all", since anything short of "all" would have some degree of exclusivity. Actually, I can see more uses for "some but not all" than for "exactly one". – supercat Feb 11 '15 at 00:47
12

On a two gate XOR the output is high when the inputs are different. If the inputs are the same the output is low.

Hence this truth table:

enter image description here

You can find a XOR gate that have more than two inputs, but they are not actually a 3 input XOR. They XOR input A and B and the result of them "R" is then XOR with input C. And the result of R XOR C is then XOR with input 4 and so on.

Here is a truth table for the three input XOR shown:

enter image description here

A simple parity algorithm is XORing bits in a received message over for example Ethernet. If the sender and the receiver know that XORing the message bits should be 0 (one bit in the message is provided to be able to add a one so that a message of any length can be 0 when XORed) then the receiver can know if 1 bit has been flipped. This is a bad parity check as it can only find odd number of bit changes, but shows the concept.

uniquenamehere
  • 850
  • 1
  • 9
  • 21
  • 3
    I'm a mathematician, that answer looks horrible to me. I understand that is the output generally intended by a 3-input XOR but 01101000 seems far more logical to me. + Nice answer. – Ben Crossley Jun 05 '19 at 20:30
2

So, I went there and tested! I wrote a small verilog file, simulated and looked at the waveform.

It turns out the correct interpretation for verilog is: There is an odd amount of 1's in the input AKA Interpretation 2 of this article

module top (y1, y2);
output y1, y2;
reg a, b, c;
wire x1, x2;
wire t;

xor(t, a, b);
xor(x2, t, c);

assign y2 = x2;
assign y1 = x1;

xor(x1, a, b, c);

initial
begin
  $dumpfile("test.vcd");
  $dumpvars(y1, y2, a, b, c, x1, x2);

#20
#10  a = 0; b = 0; c = 0;
#10  a = 0; b = 0; c = 1;
#10  a = 0; b = 1; c = 0;
#10  a = 0; b = 1; c = 1;
#10  a = 1; b = 0; c = 0;
#10  a = 1; b = 0; c = 1;
#10  a = 1; b = 1; c = 0;
#10  a = 1; b = 1; c = 1;
#10  a = 0; b = 0; c = 0;
end

endmodule

enter image description here

mentatkgs
  • 121
  • 2
2

XOR is not completly a parity gate. If you define the output of XOR as 1 when one and only one of the inputs is 1 then a three input XOR would give you 0 for all-1 input. This is not used very often and so there are few 3-input XOR-gates.

What most people mean when they say XOR is modulo 2 addition which is a parity checker exactly. Most gates labeled as 3-input XORs are in fact modulo 2 addition gates. For two inputs, modulo 2 addition is the same thing as XOR but the 0 from the XOR described above is instead a 1 in modulo 2 gates. Modulo 2 gates with an arbitrary number of inputs can be produced from simple two-input XOR gates.

Duggie
  • 21
  • 2
1

If you take 4 inputs and feed two to one XOR and two to another then, take the two XOR outputs and feed them to a third XOR, its output does what you believe it should (I think).

Andy aka
  • 434,556
  • 28
  • 351
  • 777
  • 1
    I'm more concerned about the whys, not hows. Thanks for the answer, though. – gabrieljcs Dec 15 '13 at 19:22
  • @root, actually, you asked "How should it behave?" You didn't ask why anywhere. This is a correct answer, it yields ((A⊕B)⊕(C⊕D)) which is the same as a 4input XOR, which is the same as multiple 2input XORs cascaded together. – Kris Bahnsen Dec 15 '13 at 21:29
  • You're right. Sorry for the misunderstanding. – gabrieljcs Dec 16 '13 at 16:46
1

i did a bit of search on seeing your question and found an IC which is a 3input XOR gate. 74LVC1G386 from nxp. the link to the nxp site showing search results for this part number in nxp site is http://www.nxp.com/search?q=74lvc1g386&type=keyword&rows=10

Mahesh Mohandasan
  • 11
  • 3
  • 2
    Thanks for contributing, but your answer will be worthless if NXP changes their search engine. Please summarize what you found here so it will be of lasting value. – Joe Hass Dec 31 '13 at 14:53
  • i just searched to see if there is any manufacture provide XOR with more than 3 inputs and found this one...so thought it'd help i share it...here is a link to their data sheet http://www.nxp.com/documents/data_sheet/74LVC1G386.pdf – Mahesh Mohandasan Dec 31 '13 at 15:04
  • 1
    Please don't post another link! Tell us how the thing works! – Joe Hass Dec 31 '13 at 15:11
  • its a 3 input XOR gate which functions just like we've studied/know. ie., it gives a high o/p for odd number of high inputs(as from the data sheet).thats why shared the link. :) – Mahesh Mohandasan Dec 31 '13 at 15:22
0

As per the logic of simple multi input OR gate, it assumes the the highest value amongst all inputs however it does not take a decision. As regards EXOR ( being mixed up with half adder being just a coincidence, as it does not happen in multi value logic EXOR) it takes a decision as to which one is highest amongst the inputs but if the highest (including 0+0..1+1) are same it fails to select amonst the inputs means it cannot take a decision which one to choose from. No decsion means output is zero.For example if someone is asked to buy maximum number of sweets of one brand in one doller and if there are two brands (radix=2) then he can select the one having highest sweet count but if both brand are available at free of cost he cannot select any (means 0,0) likewise if both the brands offer same number(1,1) of sweets he cannot take a decision means output is zero. Same logic can be extented for 3, 4 or more number of brands (higher radix) of sweets. This equally applicable to multi value logic. (x +x+..+x=0 where x can have any value), In three input EXOR gate 1+1+1=0 (as against the normal interpretation 1+1+1=1 which appears to be wrong, being mixed up with parity). V. T. Ingole, PhD

vijay ingole
  • 220
  • 1
  • 4
  • This explanation is unnecessarily complicated, and doesn't seem to definitively answer the question anyway. –  Sep 16 '15 at 00:04