Have an Android phone?

Try our new game!

XOR gate

XOR gate is a logic gate that performs the operation, verbally defined as "either A or B, but not both" (formally named exclusive OR). Exclusive OR (XOR) gates are less common than OR or AND gates, but they are important in circuits that compare values for equality, compute checksums or do some arithmetics[1].

The equivalent of the XOR element that may be found in everyday life is the device that allows to switch the light on or of from the two places. The light is on only when both switches are in the same position. Hence it can be turned on or off with any of the switches, independently in which position somebody has left another switch. For the "strict" definition, light should mean 0 and darkness should mean 1.

The wiring diagram that allows to control the single light source with two switches. The light is on when either both switches are switched up or both down
The wiring diagram that allows to control the single light source with two switches. The light is on when either both switches are switched up or both down

XOR gate with two inputs

Most (if not all) commercially produced XOR gates have two inputs. XOR elment with two inputs has logical value 1 on the output only if values at both inputs are the same. This means, it produces 0 for input combinations 00 and 11 and 1 for combination 10 and 01. This operation is also called exclusive disjunction and can be written as

.

The two input XOR (exclusive OR) logic gate)

The two input XOR gate performs operation (A and not B) or (B and not A). It can be assembled from AND, OR and NOT elements as shown below:

Assembling the XOR gate from AND, NOT and OR gates.


The circuit above literally repeats the definition. However while easier to understand, this circuit is not good in real world device as it requires three different types of logic gates. Usually is it better to have as little different types as possible, as it is common to package four or six gates into every chip. Hence we would need as many chips as we have different gates, and some gates are likely to stay unused. The circuit below implements XOR element by using four identical NAND gates:

Implementing XOR gate from four identical NAND gates.

The two input XOR gate can work as a controlled bit flipper: depending from the value on one input, it either inverts the value on another input (working as NOT element) or passes it unchanged (working as simple repeater).

XOR element with more than two inputs

If the XOR gate has more than two inputs, it produces logical 1 in the output when the number of 1-input is odd (not when the values in all inputs are the same). For example, if gate has three inputs, it produces 1 for 001, 010, 100, 111 and zero for all others input combinations. This does not contradict the previous definition as for the two input gate, the number of 1-inputs is only odd then when the input values are different. The multi - input XOR gate can be build from the two input XOR gates by simple cascading, as shown in the example.

Cascading 2 input XOR elements to produce 3 input XOR element

The output of the multi-input XOR gate can be viewed as a simple "checksum" that allows to detect error in transferring (inverting) any of the inputs, or the checksum itself. When used this way, the output of the XOR gate is called the parity of the input. These "parity checks" are used in automated error detection and correction.

Cascading two input XOR elements in order to make five input XOR element

Controlled NOT

An important concept in some quantum computers is the two input controlled NOT gate that flips the second input only if the first input is 1 (the first input is passed through the element unchanged). The value of the second output corresponds to the result of a classical XOR gate. Controlled NOT is an important part of reversible logic that allows always allows to reconstruct its input from the output. Such elements have potential to be much more energy efficient but if implemented on the top of the usual elements they are not.

Binary to Gray code converter

Gray code is a special code where only one bit changes between subsequent numbers. Counters that count in Gray code are supposed to produce very "clean", always consistent output. Ordinary counter frequently changes more than one bit when counting next value. If these changes does not happen in absolutely the same time (impossible to reach), the unexpected wrong value may transiently show in the output of the counter. XOR gates can easily convert usual binary code into Gray code using the known formula

that means XOR operation between the each two adjacent bits of the binary value (the highest bit that stays without pair is formally XOR-ed with 0 = left unchanged). The diagram below shows the binary counter whose output is converted into Gray code with XOR gates.

Converting to Gray code with XOR gates

Such converter is very easy to build but it seems more suitable for optical effects. The XOR gates still can produce unexpected spikes as they input comes from the ordinary counter where unexpected transient values may occur (so trash in, trash out)[2]. In order to produce the consistent noise-free output, the counter must count in Gray code directly.

See also

References

  1. 1 Reference on XOR element
  2. 2 Synthesis Issues