Templates for Toffoli Network Synthesis
Dmitri A Maslov, Gerhard W. Dueck, David Michael Miller · 2003
Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Tooli networks can be divided into two steps. First, nd a network that realizes the desired function. Second, transform the network such that it uses fewer gates, while realizing the same function. This paper addresses the second step. 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 reducing the gate count can be applied. All templates for m 7a re described in this paper.