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
fDate :
6/1/2005 12:00:00 AM
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;
Journal_Title :
Very Large Scale Integration (VLSI) Systems, IEEE Transactions on
DOI :
10.1109/TVLSI.2005.844284