Finding the Redundant Gates in Reversible Circuits

The paper presents a BDD-based post-synthesis technique to detect the redundant gates in a reversible circuit. Given a reversible circuit C, we are looking for a maximal (or most costly) subset of gates in C that can be removed from C without altering the functionality of the circuit. The runtime of the new algorithm is linear in the size of the involved binary decision diagrams (BDD). In order to lower the runtimes, the presented approach is extended to handle the restricted problem of only looking for up to k gates that can be removed from C for some constant k. This restriction should ensure that the sizes of the involved BDDs remain practicable for adequate constants k.