Fredkin/Toffoli Templates for Reversible Logic Synthesis

Reversible logic has applications in quantum computing, lowpower CMOS, nanotechnology, optical computing, and DNAcomputing. The most common reversible gates are the Toffoli gate and the Fredkin gate. Our synthesis algorithm first finds a cascade of Toffoli and Fredkin gates with no back-tracking and minimal look-ahead. Next we apply transformations that reduce the size of the circuit. Transformations are accomplished via template matching. The basis for atemplate 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 transformationthat reduces the gate count can be applied. In this paper weshow that Toffoli and Fredkin gates behave in a similar manner. Therefore, some gates in the templates may not needto be specified-they can match a Toffoli or a Fredkin gate.We formalize this by introducing the box gate. All templateswith less than six gates are enumerated and classified. Wesynthesize all three input, three output reversible functionsand compare our results to those obtained previously.