MOD NOTE: This post was originally a response to a long-dead thread of the same title and was split off so that any new responses won't generate notifications to long-gone participants.

It is indeed possible if your definition of a multi-input XOR is: result is high if exactly one of the inputs is high. For 3 inputs, in boolean algebra, given inputs a, b, and c, and output y (& = AND, ^ = XOR, | = OR):

y = ((a ^ b) ^ c) ^ (a & b & c)

This can be expanded to support four inputs:

y = (((a ^ b) ^ c) ^ d) ^ (a & b & c & d) ^ ((a & b & c) | (b & c & d) | (a & c & d) | (a & b & d))

and so on. It's provable by running it through a truth table.

A 3 input XOR as a circuit:

 

But why is your definition of a multi-input XOR gate that it is true if exactly one input is HI? You could just as legitimately claim that the definition is that it is LO if either all of the inputs are LO or all of the inputs are HI. You could also claim that it is HI if exactly one input is LO.

Boolean algebra provides no clear extension of a two-input XOR to an N-input XOR since the XOR operation is not fundamental to Boolean algebra to begin with. For the fundamental binary operations {AND, OR} the extensions come naturally as:

AND3 = A & B & C
OR3 = A + B + C

But since XOR is not a defined operator, you can't just cascade it like this and call it the natural extension to N inputs. Similar examples would be the NAND and NOR gates. You can't just cascade them to produce what is universally accepted as the N-input versions of those gates.

To the best of my knowledge, all widely used definitions of the N-input XOR gate is that it is behaves identically to a cascade of N-1 XOR gates, which translates into being an odd-parity detector (the output is HI if an odd number of inputs are HI) regardless of whether the number of inputs is odd or even.

Interestingly, though of no practical consequence that I'm aware of, the degenerate cases of AND, OR, and XOR to a single input is that they each disappear (become buffers).

 

But since XOR is not a defined operator, you can't just cascade it like this and call it the natural extension to N inputs.

I think you can. Without getting into the various permutations like XNOR, XOR is just what it's name says it is no matter how many inputs there are. For 2 inputs, the output is high if any one input exclusively is high. For 4 inputs the same definition holds, any *one* input gives an output.

ak

 

I think you can. Without getting into the various permutations like XNOR, XOR is just what it's name says it is no matter how many inputs there are. For 2 inputs, the output is high if any one input exclusively is high. For 4 inputs the same definition holds, any *one* input gives an output.

ak

But if you cascade it, then you get the odd parity generator which is HI if an odd number of inputs are HI. That's not a matter of semantics or word definitions. If you cascade (N-1) XOR gates, you get an N-input odd parity generator.

Saying that XOR is just what it's name says it is doesn't really cut it. I'm not saying that your interpretation of the extension of the natural meaning from two inputs to more than two inputs is unreasonable -- it's quite reasonable. But it is still a matter of being one reasonable definition in competition with other reasonable definitions. Another very reasonable interpretation of the meaning "exclusive" is that it is HI when the inputs are different.

From a practical standpoint, it is somewhat irrelevant because no matter how strong the argument might be made that a multi-input XOR gate SHOULD be HI if and only if exactly one of its inputs is HI (which is a one-hot detector), that simply isn't what the industry has long since adopted -- they have adopted that a multi-input XOR gate behaves as a cascade of XOR gates, which means that it acts as an odd parity generator.

 

I understand all of your points, and agree that the true definition can be argued either way. OTOH, I don't agree with letting one application define the function; it should be the other way around. And if that means that an XOR gate with 2 inputs works as a parity generator, but not when it has 3 or more inputs, I'm fine with that.

ak

 

Hello there,

There is another interpretation of the XOR gate which does make it sort of fundamental. Although not really fundamental to Boolean logic really, it is i think fundamental to functional logic.

Consider the truth table for a 2 input XOR gate:
00 0
10 1
01 1
11 0

but to make this view more clear, lets invert the output which of course makes it a XNOR gate:
00 1
10 0
01 0
11 1

Now it becomes obvious: the XOR gate or XNOR gate is the equivalent of an EQUALS gate. That is, it determines when the two inputs are equal.

This fact means it is expandable to any number of (pairs of) bits, and as will be shown here expandable to more than two binary input numbers.

If we take two 2 input xnor gates and AND the outputs, we get a two input EQUALITY detector:
Truth table:
00 00 1
00 11 1
11 00 1
11 11 1
All else the output is zero 0.

This can be expanded to any number of bits by adding two input gates and another input for the AND gate for each. For three bits we have:
00 00 00 1
00 00 11 1
00 11 00 1
00 11 11 1
11 00 00 1
11 00 11 1
11 11 00 1
11 11 11 1
and all other input combos cause an output of 0.

Thus when the single ANDed output is 1 the two inputs (no matter how many bits) are equal, and when the output is 0 they are not equal.

Equality is an important fundamental concept/function.

For a simple construction, we can use XOR gates and a single multi input NOR gate. The NOR gate will then function as a negative input logic AND gate, with positive logic output.

The question then can be asked, "What if we have to detect equality for three binary number inputs rather than just two?".
The answer can then be to use three input XOR gates rather than just two input XOR gates, if we could find them. That way we could detect non equality between three different binary inputs.
For a one bit example:
000 1
001 0
010 0
011 0
100 0
101 0
110 0
111 1

Only when all three inputs are the same do we get a '1' on the output. This concept can also be extended to multiple bit binary inputs.

The verbal description of the XOR gate is also useful:
"Either input high, but not both"

and could be extended to multiple bits by:
"Any input high, but not all".

In a computer language we might have a function available:
y=Compare(0111,1010)

which of course here would equal zero. The multi input XOR gate would give us the equivalent of:
y=Compare(0111,1010,0100)

which compares three binary numbers and only returns TRUE if all three are equal.

If we didnt have three input XOR gates available then we'd have to do the three input comparisons two at a time or do two sets of two comparisons and AND the results. If we had four groups of numbers to test for equality then we'd have to compare the first group with the remaining three groups and then AND the results. That would take a lot of 2 input XOR gates.

 

 

Hello there,

There is another interpretation of the XOR gate which does make it sort of fundamental. Although not really fundamental to Boolean logic really, it is i think fundamental to functional logic.

Not an unreasonable interpretation, but neither are about three others.

We are still left with the fact that the community has long since chosen what a multi-input XOR gate is.

 

I understand all of your points, and agree that the true definition can be argued either way. OTOH, I don't agree with letting one application define the function; it should be the other way around. And if that means that an XOR gate with 2 inputs works as a parity generator, but not when it has 3 or more inputs, I'm fine with that.

ak

I understand the sentiment, but I don't think it's a case of letting one application define the function. A definition HAD to be made. They chose to define it using the same topology that defines, via Boolean algebra, multi-input OR and AND gates (which have a very strong and natural extension from two inputs to three inputs), namely that the output of a multi-input XOR gate is indistinguishable from a cascade of 2-input XOR gates. They accepted whatever logic function results, which happens to be an odd parity generator. Now, if that resulting function had not been useful, my guess is that they MIGHT have found a different definition, or they might have just punted, since there was no driving need/value, and never defined it at all (just as there is no definition for a multi-input implication gate).

 

View attachment 91445

That doesn't serve as a useful definition. For instance, what would that approach mean for a 4-input NAND gate or a 4-input NOR gate?

 

That doesn't serve as a useful definition. For instance, what would that approach mean for a 4-input NAND gate or a 4-input NOR gate?

point taken

just thought I'd throw something in

 

Not an unreasonable interpretation, but neither are about three others.

We are still left with the fact that the community has long since chosen what a multi-input XOR gate is.

Hi,

Not sure what you are trying to say here. Are you saying there was a general consensus of how we should view the XOR gate?

 

Hi,

Not sure what you are trying to say here. Are you saying there was a general consensus of how we should view the XOR gate?

Whenever I have seen a multi-input XOR gate in a standard cell library, it has always been as described, namely the functional equivalent of an odd parity generator.

 

Hi,

Not sure what you are trying to say here. Are you saying there was a general consensus of how we should view the XOR gate?

Can speak for him but the Mod-2-SUM (for parity check relationships) is very useful in chip designs (to simplify logic and save die space) with error-correction codes (EEC) to improve the reliability of memory or data transmissions with things like hamming codes.

 

Hi,

Not sure what you are trying to say here. Are you saying there was a general consensus of how we should view the XOR gate?

This thread started as a necropolis of the very same set of arguments. The mods thought it would be more fruitful for us to all repeat the old arguments as the original thread falls back to the deeper ocean of now locked threads.

In the old thread, @Papabravo put up this link of a commercial part - see truth table.
http://www.nxp.com/documents/data_sheet/74LVC1G386.pdf

For your reading-only pleasure, the locked original is here. We don't want to tread on the rights of the thread owner with two total posts to his credit, @Ashik Ghona


http://forum.allaboutcircuits.com/threads/is-it-possible-4-input-xor-gate-why.65323/

 

Hi,

Yes that's interesting. So it could be implemented either way: as a parity generator or as an equality detector (see the IEEE symbol). From what i have read the most common way (but not the only way) is to implement as a parity generator.
From what i can see though, implementing as a parity generator looses some symmetry coming from the other logic form combinations like AND and OR. AND and OR operate on two inputs, but if expanded to three inputs it does basically the same thing for all three inputs in a very symmetrical way. Expanding the XOR with only more XOR gates means we are now operating on pairs of inputs, so we change the grouping. But then again the pairs themselves are have equal priority and there is no constraint on which pairs will be the pair or single input that will be the last straw.
So maybe it can not be nailed down to one or the other, but must be taken to be possibly both depending on the way the designer wanted to implement it.

I was going to say that we already have a parity generator, but then again we already have an equality detector too

I needed lots of equality detectors back in the early 1980's for very fast coincidence detection. That's where i first found the idea that an xor gate can act as an equality detector. I needed lots of them and the packages being sold at the time as genuine equality detectors were much more expensive.

This has been an interesting thread.

 

I think peter taylor almost had it. Isn't this a 4 input XOR gate?

 

Hi,

Yes that's interesting. So it could be implemented either way: as a parity generator or as an equality detector (see the IEEE symbol). From what i have read the most common way (but not the only way) is to implement as a parity generator.
From what i can see though, implementing as a parity generator looses some symmetry coming from the other logic form combinations like AND and OR. AND and OR operate on two inputs, but if expanded to three inputs it does basically the same thing for all three inputs in a very symmetrical way. Expanding the XOR with only more XOR gates means we are now operating on pairs of inputs, so we change the grouping. But then again the pairs themselves are have equal priority and there is no constraint on which pairs will be the pair or single input that will be the last straw.
So maybe it can not be nailed down to one or the other, but must be taken to be possibly both depending on the way the designer wanted to implement it.

A multi-input XOR (acting as a parity detector) is completely symmetric, meaning that the assignment of a particular signal to a particular input has absolutely no effect on the output.

The designer has no say in that; if they are implementing a particular function then any implementation that properly implements that function must behave the same way functionally -- it's the function that is symmetric or not, not the implementation. Now, there may be other asymmetries, such as propagation delay. If implemented as a tree, the prop delays will be fairly symmetric but if implemented as a cascade they will be very asymmetric. But this is true of multi-input AND and OR gates, too. For that matter, even two-input gates are seldom truly symmetric since the capacitance on the series chain elements are not uniform (one of them is much higher) without special design effort.

 

I think peter taylor almost had it. Isn't this a 4 input XOR gate?

View attachment 91509

Depends on the definition that is used for a multi-input XOR gate, which is the crux of the entire thread. Different people feel it should be defined different ways and there are several definitions for which you can come up with sound justifications for that definition being the most natural way to extend the definition from two inputs to more than two inputs.

IF you define it to behave functionally as a cascade of XOR gates, then this (which is a tree of XOR gates) is functionally equivalent.

Cascade of XOR gates:



This stems from the standard Boolean algebra property that AND and OR are left associative. So

(A + B + C + D) = (((A + B) + C) + D)

This is used, as far as I know, as the universal definition of a multi-input OR gate. Similar for an AND gate. But XOR is not a standard Boolean operator and hence has no standard associativity assigned to it. However, a very common (nearly universal) shortcut operator does exist and it is always (as far as I know) treated as being left associative. Hence

\(
(A \oplus B \oplus C \oplus D) \; = \; (((A \oplus B) \oplus C) \oplus D)
\)

Under this convention, then a multi-input XOR gate MUST behave as a cascade of 2-input XOR gates.

Because OR, AND, and XOR are associative operators. This means that

(A + B + C + D) = ((A + B) + (C + D))

The left is a cascade and the right is a tree. Thus for all three operators the tree implementation is functionally identical to the cascade implementation.

Note that if you define a multi-input XOR to be anything other than a parity generator, then you MUST define it's behavior in Boolean algebra to be consistent with that. Good luck.

 

Depends on the definition that is used for a multi-input XOR gate, which is the crux of the entire thread.

I too think that this discussion has been mainly about semantics, so far. Once a function is defined by clear boolean algebra that is not subject to arbitrary interpretation then what's left is how one would like to baptize said function... of course it might be important to speak the same language, but I only consider that relevant when dealing with fundamental (or basic) operations, or at least common building blocks... just my humble opinion... and my 2¢