Home Detail

Minimization Techniques for Reversible Logic Synthesis

Lecturer: Dr. Gerhard Dueck, University of New Brunswick, Canada



Reversible logic is an emerging research area. Interest in reversible logic is sparked by its applications in quantum computing, low-power CMOS, nanotechnology, and optical computing. Synthesis of reversible circuits differs significantly from synthesis using traditional irreversible gates. Two restrictions are added for reversible networks, namely fan-outs and back-feeds are not allowed. Thus, the only possible structure for a reversible network is a cascade of reversible gates. Toffoli gates are the most frequently used and best investigated. The Toffoli gate inverts a single bit if the Boolean AND of a set of control lines is true.
The synthesis of Toffoli networks can be divided into two steps. First, find a network that realizes the desired function. Second, transform the network such that it uses fewer gates, while realizing the same function. In this talk I will addresses the above synthesis idea. 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 the gates in a template, then a transformation reducing the gate count can be applied. I will describe an efficient method to find all identity circuits (the basis for a template) with a reasonable number of gates. I will conclude the talk by describing some open problems and offer hints on how to tackle them.

Download:

back