Courses

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

```