Trading off circuit lines and gate costs in the synthesis of reversible logic

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 in the resulting circuits. Hence, designers often have to deal with unsatisfactory results were either the gate costs or the number of circuit lines is 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 these effects. 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 competing requirements.