Others view: Four Russians (algorithm) ♦ welcome ♦ Smith & Waterman ♦ Boyer Moore algorithm/ ♦ Welcome ♦ Matrix ♦ complex number ♦

**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.

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 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:

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:

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).

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.

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.

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.

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.

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.

- Forming signals with the XOR gate and delay line.
- Random signal generator made from the shift register and XOR gate.

^{1 }Reference on XOR element^{2 }Synthesis Issues