Page 1 Group Theoretical Aspects of Reversible Logic Gates Page 2 Group Theoretical Aspects of Reversible Logic Gates Abstract â€¢ Logic gates with three input bits and three output bits have a privileged position within fundamental computer science. They are a sufficient building block for constructing arbitrary reversible boolean networks and therefore are the key to reversible digital computers. â€¢ Such computers can, in principle, operate without heat production. â€¢ There exist as many as 8! = 40,320 different 3-bit reversible truth tables â€¢ The question: which ones to choose as building blocks. â€¢ Because these gates form a group with respect to the operation `cascading', we can apply group theoretical tools, in order to make such a choice. â€¢ We will study permutations Page 3 Group Theoretical Aspects of Reversible Logic Gates Abstract â€¢ Logic gates with three input bits and three output bits have a privileged position within fundamental computer science. They are a sufficient building block for constructing arbitrary reversible boolean networks and therefore are the key to reversible digital computers. â€¢ Such computers can, in principle, operate without heat production. â€¢ There exist as many as 8! = 40,320 different 3-bit reversible truth tables â€¢ The question: which ones to choose as building blocks. â€¢ Because these gates form a group with respect to the operation `cascading', we can apply group theoretical tools, in order to make such a choice. â€¢ We will study permutations The plan of this paper â€¢ 1. Separate to equivalence classes: permutation (E), negation(I) â€¢ 2. Class PN created by E and I, denoted by group F â€¢ 3. Find generators of group R. â€¢ 4. Investigate the effectiveness of these generators, it means the average number of cascade levels needed to generate an arbitrary circuit from this type of generator. â€¢ Investigate small sets of generators as candidates for a library of cells. R is the group of all reversible gates Page 4 Group Theoretical Aspects of Reversible Logic Gates Abstract â€¢ Logic gates with three input bits and three output bits have a privileged position within fundamental computer science. They are a sufficient building block for constructing arbitrary reversible boolean networks and therefore are the key to reversible digital computers. â€¢ Such computers can, in principle, operate without heat production. â€¢ There exist as many as 8! = 40,320 different 3-bit reversible truth tables â€¢ The question: which ones to choose as building blocks. â€¢ Because these gates form a group with respect to the operation `cascading', we can apply group theoretical tools, in order to make such a choice. â€¢ We will study permutations The plan of this paper â€¢ 1. Separate to equivalence classes: permutation (E), negation(I) â€¢ 2. Class PN created by E and I, denoted by group F â€¢ 3. Find generators of group R. â€¢ 4. Investigate the effectiveness of these generators, it means the average number of cascade levels needed to generate an arbitrary circuit from this type of generator. â€¢ Investigate small sets of generators as candidates for a library of cells. R is the group of all reversible gates 1 Introduction â€¢ Landauer's principle: logic computations that are not reversible, necessarily generate heat: â€“ i.e. kTlog(2), for every bit of information that is lost. where k is Boltzmann's constant and T the temperature. â€¢ For T equal room temperature, this package of heat is small, i.e. 2.9 x 10 -21 joule, but non- negligible. â€¢ In order to produce zero heat, a computer is only allowed to perform reversible computations. â€¢ Such a logically reversible computation can be `undone': the value of the output suffices to recover what the value of the input `has been'. â€¢ The hardware of a reversible computer cannot be constructed from the conventional gates â€¢ On the contrary, it consists exclusively of logically reversible building blocks. â€¢ The number of output bits of a reversible logic gate necessarily equals its number of input bits. â€¢ We will call this number the `logic width' of the gate. Page 5 Group Theoretical Aspects of Reversible Logic Gates Abstract â€¢ Logic gates with three input bits and three output bits have a privileged position within fundamental computer science. They are a sufficient building block for constructing arbitrary reversible boolean networks and therefore are the key to reversible digital computers. â€¢ Such computers can, in principle, operate without heat production. â€¢ There exist as many as 8! = 40,320 different 3-bit reversible truth tables â€¢ The question: which ones to choose as building blocks. â€¢ Because these gates form a group with respect to the operation `cascading', we can apply group theoretical tools, in order to make such a choice. â€¢ We will study permutations The plan of this paper â€¢ 1. Separate to equivalence classes: permutation (E), negation(I) â€¢ 2. Class PN created by E and I, denoted by group F â€¢ 3. Find generators of group R. â€¢ 4. Investigate the effectiveness of these generators, it means the average number of cascade levels needed to generate an arbitrary circuit from this type of generator. â€¢ Investigate small sets of generators as candidates for a library of cells. R is the group of all reversible gates 1 Introduction â€¢ Landauer's principle: logic computations that are not reversible, necessarily generate heat: â€“ i.e. kTlog(2), for every bit of information that is lost. where k is Boltzmann's constant and T the temperature. â€¢ For T equal room temperature, this package of heat is small, i.e. 2.9 x 10 -21 joule, but non- negligible. â€¢ In order to produce zero heat, a computer is only allowed to perform reversible computations. â€¢ Such a logically reversible computation can be `undone': the value of the output suffices to recover what the value of the input `has been'. â€¢ The hardware of a reversible computer cannot be constructed from the conventional gates â€¢ On the contrary, it consists exclusively of logically reversible building blocks. â€¢ The number of output bits of a reversible logic gate necessarily equals its number of input bits. â€¢ We will call this number the `logic width' of the gate. Gates of logic width 3 â€¢ Fredkin and Toffoli: â€“ demonstrated that three inputs and three outputs is necessary and sufficient in order to construct a reversible implementation of an arbitrary boolean function of a finite number of logic variables. â€¢ Thus, from the fundamental point of view, reversible logic gates with a width equal to three have a privileged position.Read More