Home > Logic Design > XOR – The Interesting Gate

XOR – The Interesting Gate

Note: The interesting features in XOR and XNOR are somehow the same but with small difference, I’ll speak in details here about XOR and will provide another article for XNOR later.

XOR Symbol Red

Among other logic gates, XOR and XNOR are  interesting gates having some unique features.

Multi-input XOR

All 2-input logic gates have the same meaning when they have more than 2 inputs. For example an AND gate is a gate that outputs 1 when all its inputs are 1, an OR gate outputs 1 when any of the inputs is 1, a NAND gate outputs 0 when all its inputs are 1, a NOR gate outputs 1 when all its inputs are 0.

A 2-input XOR gate outputs 1 when there’s exactly a single 1 at the inputs which means it’s exclusively there and that’s from where the name XOR (Exclusive OR) comes. We can alternatively say that it outputs 1 when the 2 inputs are different.

A multi-input XOR gate however doesn’t necessarily have the same meaning as the 2-input XOR above. There’re two different interpretations for a multi-input XOR and let’s check that on a 3-input XOR as an example:

3-input XOR

Interpretation 1

XOR outputs 1 when exactly one of the inputs is 1. This means in other words: either X, Y or Z. Here we are still having the meaning we had in the 2-input XOR … the exclusionary.

This interpretation of XOR is sometimes called one-hot checker or negative coincidence.

In this interpretation F(X, Y, Z) = XY’Z’ + X’YZ’ + X’Y’Z

Interpretation 2

XOR outputs 1 when there are an odd number of 1’s in the input.

In this interpretation F(X, Y, Z) = XY’Z’ + X’YZ’ + X’Y’Z + XYZ

In this interpretation, the XOR can be used as an odd parity checker of the input and consequently an even parity (bit) generator to that input!

You may also notice that the XOR here acts as if it adds the input bits producing the sum bit with out a carry!

How is each interpretation implemented?

Interpretation 1 must be implemented using the equation given for it above [ F(X, Y, Z) = XY’Z’ + X’YZ’ + X’Y’Z ] … that is using 2-level AND-OR circuit design.

Interpretation 2 could also be implemented using its equation [ F(X, Y, Z) = XY’Z’ + X’YZ’ + X’Y’Z + XYZ ] but the interesting thing is that it can be implemented as a tree/chain of XORs.

Here’s how it looks like:

 Interpretation 1

 Interpretation 2

 F(X, Y, Z) = XY’Z’ + X’YZ’ + X’Y’Z

 F(X, Y, Z) = XY’Z’ + X’YZ’ + X’Y’Z + XYZ

 3-input XOR Interpretation 1

3-input XOR Interpretation 2

 3-input XOR Interpretation 1 Truth Table

3-input XOR Interpretation 2 Truth Table

It’s obvious how a chain of XORs is equivalent to the second interpretation of 3-input XOR.

One more important notice that a multi-input XOR in the second interpretation is associative, that is  XXOR SymbolYXOR SymbolZ = (XXOR SymbolY)XOR SymbolZ = XXOR Symbol(YXOR SymbolZ) = (XXOR SymbolZ)XOR SymbolY.

The associativity property in the second interpretation makes it possible to have two different designs  for a 4-bit XOR as shown below:

Interpretation 2 

 F=(((XXOR SymbolY)XOR SymbolZ)XOR SymbolW)

F=(XXOR SymbolY)XOR Symbol(ZXOR SymbolW)

 4-input XOR Design 1

4-input XOR Design 2

 4-input XOR Truth Table

Both design methods are equivalent

It’s also the same case that we have different design methods for more than 4-input XOR due to the associativity property

XOR the  ” Invert or Don’t Invert” tiny circuit

2-input XOR gate outputs XY’+X’Y when supplied with the inputs X and Y … what if one of the inputs is 1 or 0?

  • 1XOR SymbolX = X’
  • 0XOR SymbolX = X

That is if X is xored with 0, it passes as it’s and will be inverted if xored with 1.

What if 1/0 is a control signal S? The value of S then will determine if X passes or else its complement.

This way we get a tiny logic circuit that I call “Invert or Don’t Invert” circuit.

 XOR Invert or Don't Invert Circuit

S

F

0

X

1

X’

XOR Swaps without a temp

A very common trick with XOR is that it can be used to swap the value of two variables without using a third temporary variable. The algorithm follows:

  • X = XXOR Symbol Y
  • Y = XXOR Symbol Y
  • X = XXOR Symbol Y

We can easily prove that:

  • X = XXOR Symbol Y
  • Y = XXOR Symbol Y = (XXOR Symbol Y) XOR Symbol Y = XXOR Symbol (Y XOR Symbol Y) = XXOR Symbol 0 = X  ==> Y = X
  • X = XXOR Symbol Y = (XXOR Symbol Y) XOR Symbol Y = (XXOR Symbol X) XOR Symbol Y =  0XOR Symbol Y = Y ==> X = Y

Summary

  • Multi-Input XOR has two different interpretations unlike all other gates except XNOR.
  • The first interpretation of XOR is that it outputs 1 when exactly one of the inputs is 1.
  • The second interpretation of XOR is that it outputs 1 when there are an odd number of 1’s in the input. As if it adds the input bits to produce the sum bit without carry.
  • Multi-Input XOR (Interpretation 2) can be used as an odd parity checker of the input or an even parity (bit) generator to that input.
  • Interpretation 2 can be implemented as a chain/tree of XORs.
  • XOR can be used as an “Invert or Don’t Invert” circuit.
  • XOR can be used to swap the value of two variables without using a third temporary variable.
– Ahmed Abdullah Hussein
Advertisements
  1. nikhil
    December 24, 2013 at 1:50 PM

    very helpful post.. thanks..

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: