Three-input universal logic gate

Logic gates are used to build computer chips. Reversible logic gates are of interest because they could in principle generate useful results for less heat generated.[1] The nand gate is universal among irreversible logic gates, in the sense that it is possible to simulate any irreversible logic gate with a network of these gates. The Fredkin and Toffoli gates were the first gates to be proved universal among reversible logic gates. However, this universality is not unusual in the space of 3 input and 3 output reversible gates.

A reversible logic gate of n input bits must have n output bits, by the pigeonhole principle. The reversibility requirements means that each of the 2n input combinations must have one and only one output combination - they must be a one-to-one map. Thus the outputs for the inputs are simply some permutation of the inputs, and so the number of n-input reversible gates is 2n! .

For a three-input gate, this number is 8!, around 40 thousand.

Let us define an equivalence relation: two gates are equivalent if the outputs of one can be gotten by rearranging the bits of the outputs of the other. That is, if we simply relabel the wires attached to the output terminals of the gate. Every gate, then, is a member of a 6-member equivalency class bringing the total number of possible gates down to 8000 or so. The three-input identity gate:

Input 0 01010101
Input 1 00110011
Input 2 00001111
Output 0 01010101
Output 1 00110011
Output 2 00001111

is equivalent to this gate:

Input 0 01010101
Input 1 00110011
Input 2 00001111
Output 0 00110011
Output 1 01010101
Output 2 00001111

which merely swaps outputs 0 and 1.

We shall abbreviate the truth table above by treating columns as octal numbers and rows as hexadecimal numbers (a redundancy, but a useful one). The three-input identity table may be written [01234567:AA/CC/0F], and the second table above [02134657=CC/AA/0F]'. The first set of digits gives the output for each possible input, and the second set gives the truth table for each of the three outputs. The remainder of this article will use this notation.

Omitting duplicates gives us around 8000 possible gates.

We are interested in universality. Any one output of a three-input logic gate can have 28 possible truth tables for the 8 distinct input values. A logic gate (or set of logic gates) is universal when suitable cascades of gates can be constructed to give us any of these 256 truth tables.

Surprisingly, it turns out that almost all of the 8 thousand or so 3/3 reversible gates are universal in this sense.

There are 269 exceptions. One of them is the "straight through" gate.

7 of them provide access to 8 possible truth tables. These are:

These ones are those that provide a "not" operator. The 8 truth tables are the 8 ways you can not or not-not each of the 3 inputs.

The remaining exceptions all provide access to 16 truth tables. One example is [75462013=C3:99:0F]. As you can see, this table performs an Exclusive Or (XOR). The 16 truth tables that this gate and presumably all the others provide access to are:

The possible logic gates form a group, with the "set of all gates that XOR some of the inputs" (etc.) being a subgroup.

In summary: almost all 3 input/3 output reversible logic gates are universal in the sense that a network of them can produce any result. Thus the Fredkin and Toffoli gates are not remarkable in being universal.

See also

References

  1. ↑ (Landauer 1961)
This article is issued from Wikipedia - version of the Saturday, February 13, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.