Descending Order Transformation-based Synthesis of MVL Reversible Circuits
D. Michael Miller, Gerhard W. Dueck · 2021
Transformation-based synthesis is a straightforward technique for determining a circuit for a reversible function. Various methods employing the transformation-based approach have been previously proposed. For an r-valued function, the existing methods consider the function specification in ascending order from the input assignment 0,0,...,0 to the input assignment r - 1, r - 1,..., r - 1. In this paper, we extend the transformation-based synthesis approach by showing how the input assignments can be considered in descending order. A useful technique is to synthesize two circuits, one using ascending order and the other using descending order, and to choose the cheaper circuit as the solution. Experimental results considering both reversible gate count and quantum cost for the 9! 3-valued reversible functions and for a selection of larger functions demonstrate the advantages of considering descending as well as ascending order. The paper includes suggestions for further research incorporating the new descending order approach.