Hey guys, just wanting a definition for the XOR gate. Does this mean that the output will be high if and only if one input is high or if odd N inputs are high? Like say for example, a four input XOR gate? I have googled this already but am getting conflicting results. For the purpose of an exam which definition do i use?
XOR gate truth table
- Thread starter mentaaal
- Start date
The XOR-gate implements something called exclusive disjunction which is best illustrated with a 2-input gate - put simply the output is true if one and only one of the inputs is true.
If you expand the XOR function to more than 2-inputs then the general XOR rule is that the XOR-gate gives a true output when there are an odd number true inputs.
Dave
If you expand the XOR function to more than 2-inputs then the general XOR rule is that the XOR-gate gives a true output when there are an odd number true inputs.
Dave
The way I keep track of XOR output is that I add the binary values module 2 and whatever I get from the addition is the output.
For example, 1 + 1 in modulo 2 is 0 so the output is 0
Another example: 1+0+1+1+0+1+1 in modulo 2 is 1 so XOR of these seven binary bits is 1.
The XOR is the basis for a half-adder.
hgmjr
For example, 1 + 1 in modulo 2 is 0 so the output is 0
Another example: 1+0+1+1+0+1+1 in modulo 2 is 1 so XOR of these seven binary bits is 1.
The XOR is the basis for a half-adder.
hgmjr
This is the principle of exclusive disjunction and is only fully applicable to a 2-input XOR-gate - this is where the confusion in the OP arises.
A simple example of where the principle of exclusive disjunction breaks down is when all inputs of a 3-input XOR-gate are true - the output of the gate is also true; i.e. \(1\otimes1\)\(\otimes1\)\(\rightarrow1\). Therefore it is not as simple as saying that one and only one input high (true) gives a high (true) output; although it is true, there are exceptions.
The rule that will always work irrespective of the number of inputs is:
1) Look at the inputs to the XOR gate and add up the number of true inputs.
2) If the number of inputs that are true is odd, then the output will be true. Otherwise if the number of inputs that are true is even, then the output will be false.
Dave
Oh, yeah. I think you said that, although the Mathworld link didn't. Wikipedia has a good discussion of the >2 input XOR in natural language.
I guess I was thinking that it must be a fairly common digital logic function. Is that function also called an exclusive disjunction? (I'm a poet!)
I still stand by my statement. This article backs up that viewpoint - http://dept-info.labri.fr/~strandh/Teaching/AMP/Common/Strandh-Tutorial/gates.html.
It would hardly be an exclusive or function if the output were true for more than just one input being true. The exclusive label makes that explicit. Otherwise, it's something like a majority gate.
As I can't find anything but quad 2 input XOR & XNOR gates in the TTL and CMOS logic famlies, this isn't going to go very far.
It would hardly be an exclusive or function if the output were true for more than just one input being true. The exclusive label makes that explicit. Otherwise, it's something like a majority gate.
As I can't find anything but quad 2 input XOR & XNOR gates in the TTL and CMOS logic famlies, this isn't going to go very far.
Not sure why the Mathworld link doesn't work
Anyway, a function that has the property of exclusive disjunction is by definition an XOR function. So when beenthere says "Since it's XOR, the output is high if one, and only one, input is high.", he is not wrong. However, when a function is described as XOR it does not necessarily follow the properties of exclusive disjunction; see my example above for the 3-true-inputs to an XOR gate.
Why?
Because the XOR function, like the OR function, exhibits the associative property of addition. To quote the e-book, "This property tells us we can associate groups of added or multiplied variables together with parentheses without altering the truth of the equations."
So for a 3-input XOR gate we can have the following:
\(1\otimes1\)\(\otimes1\) is the same as saying \((1\otimes1)\)\(\otimes1\)
We know from exclusive disjunction that:
\((1\otimes1)\) = 0
And from exclusive disjunction that:
\(0\otimes1\) = 1
Therefore we can see that a 3-input XOR gate with high (true) on all 3 inputs does indeed give a high (true) on the output. By using the logic above you can extrapolate this to show that when the number of true inputs to an XOR gate is odd, the output of the gate will always be true.
Dave
The link worked, but it only discussed 2-input XORs.Not sure why the Mathworld link doesn't work
Dave
I think you are talking about bitwise XOR. Beenthere is talking about XOR in the sense that hunyukkers like me think about it.
I am pulled off-topic so easily.
Dogmatic - reminds me of Larson's great Farside cartoon.
Attachments
Indeed so, XOR has only full exclusive disjunction when we are talking about 2-inputs, i.e. it follows the full exclusion properties.
Glad the link works now; it only discusses 2-input XOR-gates because it only fully applies to 2-input gates - a 3+ input XOR gate does not necessarily have the full properties of exclusive disjunction. The principles of exclusive disjunction do apply when only one input is high (true), however there are exceptions where more than one true input can produce a true output. As stated above, these are because of the associate properties of the XOR function.
I agree that the concept of XOR for more than 2 inputs is a bit of a misnomer - you have have exclusive-ORs without the need for exclusion! I think we can see why the OP was confused about definition
Dave
bloguetronica
- Joined Apr 27, 2007
- 1,541
Just for the records: There are no XOR gates with more that 2 inputs.
