IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION ( VLSI ) SYSTEMS , VOL . ? ? ? , NO . ? ? ? , ? ? ?
A synthesis algorithm finds a cascade of Toffoli and Fredkin gates with no backtracking and minimal look-ahead, and applies transformations that reduce the size of the circuit through template matching.
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 synthesize 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 size of the circuit. 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 in the network to be synthesized matches more than half of a template, then a transformation that reduces the gate count can be applied. We synthesize all three input, three output reversible functions and compare our results to those previously obtained to test the quality of our synthesis approach. We also use our synthesis tool to obtain circuits for some benchmark functions.