Group Theoretical Aspects of Reversible Logic Gates Group Theoretical Notes | EduRev

Created by: Charu Jain

: Group Theoretical Aspects of Reversible Logic Gates Group Theoretical Notes | EduRev

 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