DocumentCode :
984806
Title :
Synthesis of Fredkin-Toffoli reversible networks
Author :
Maslov, Dmitri ; Dueck, Gerhard W. ; Miller, D. Michael
Author_Institution :
Dept. of Comput. Sci., Univ. of Victoria, BC, Canada
Volume :
13
Issue :
6
fYear :
2005
fDate :
6/1/2005 12:00:00 AM
Firstpage :
765
Lastpage :
769
Abstract :
Reversible logic has applications in quantum computing, low power CMOS, nanotechnology, optical computing, and DNA computing. The most common reversible gates are the Toffoli gate and the Fredkin gate. We present a method that synthesizes a network with these gates in two steps. First, our synthesis algorithm finds a cascade of Toffoli and Fredkin gates with no backtracking and minimal look-ahead. Next we apply transformations that reduce the number of gates in the network. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence of gates in the network to be reduced matches a sequence of gates comprising more than half of a template, then a transformation that reduces the gate count can be applied. We have synthesized all three input, three output reversible functions and here compare our results to the optimal results. We also present the results of applying our synthesis tool to obtain networks for a number of benchmark functions.
Keywords :
logic design; logic gates; network synthesis; DNA computing; Fredkin gate; Fredkin-Toffoli reversible networks; Toffoli gate; benchmark functions; design automation; logic design; low power CMOS; nanotechnology; network optimization; network synthesis; optical computing; quantum computing; reversible gates; reversible logic; synthesis algorithm; synthesis tool; template matching; CMOS logic circuits; CMOS technology; Computer applications; DNA computing; Nanotechnology; Network synthesis; Optical computing; Power dissipation; Quantum computing; Sequences; Design automation; logic design; network optimization; quantum computing;
fLanguage :
English
Journal_Title :
Very Large Scale Integration (VLSI) Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
1063-8210
Type :
jour
DOI :
10.1109/TVLSI.2005.844284
Filename :
1458796
Link To Document :
بازگشت