Trading Off Circuit Lines and Gate Costs in the Synthesis of Reversible Logic

Robert Wille, Mathias Soeken, D. Michael Miller, Rolf Drechsler

In: Integration, the VLSI Journal Elsevier 2013.


Motivated by its application in several emerging technologies, the synthesis of reversible circuits has received significant attention in the last decade. The proposed methods can roughly be divided into two different categories: (A) approaches ensuring the minimal number of circuit lines and (B) hierarchical approaches. Both synthesis paradigms have significant differences with respect to the gate costs and the number of lines of the resulting circuits. Hence, designers often have to deal with unsatisfactory results where either the gate costs or the number of circuit lines are disproportionately large. In this paper, the relation between the gate costs of a reversible circuit and the number of circuit lines is considered. We observe that by slightly increasing the number of circuit lines, significant reductions in the gate cost can be obtained. Vice versa, by accepting a small increase in the gate costs, the number of lines can significantly be reduced. Following these observations, two optimization approaches are applied to demonstrate and experimentally evaluate this effect. The optimization approaches generate alternative circuit realizations from which the best one can be picked with regard to the designers' requirements. As a result, a synthesis scheme is proposed that does not focus on a single cost metric, but trades off the contradictory requirements.

German Research Center for Artificial Intelligence
Deutsches Forschungszentrum für Künstliche Intelligenz