Three-Input Universal Logic Gate

# Three-input universal logic gate

to get instant updates about 'Three-Input Universal Logic Gate' on your MyPage. Meet other similar minded people. Its Free!

X

Description:
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 (Landauer 1961). 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 2<sup>n</sup> 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 2<sup>n</sup>! .

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

Let us define an 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:

is equivalent to this gate:

which merely swaps outputs 0 and...

No feeds found

All