An Approach to Reversible Logic Synthesis Using Input and Output Permutations

Abstract

The problem of reversible logic synthesis has assumed importance with the growing emphasis on low-power design and its relationship to quantum computation. Many synthesis approaches for reversible logic circuits have been reported over the last two decades. For small functions exact solutions that require minimum number of gates can be computed. Otherwise, heuristics have to be applied that are either based on transformations or a direct mapping from a given data structure. Recently, it was shown that significant reduction in the cost of the synthesized circuits can be obtained, if the ordering of the input (or output) lines is changed. The drawback of the approach was that it can only be applied to smaller sized circuits. In this paper, two alternate approaches for obtaining a good ordering of the variables are presented. Given a reversible specification in the form of a truth table or a permutation, both the methods rely on a properly chosen cost function and try to obtain an ordering of the variables that minimizes the cost. The first method uses an evolutionary algorithm (EA) to arrive at a good ordering of the output variables. To avoid long runtimes the EA does not synthesize the circuit after each evolutionary operation. Both the original and the least cost permutations are synthesized using a standard synthesis tool, and the improvement in cost are compared. Experimental results demonstrate the effectiveness of the scheme. The second method uses an encoded multi-valued truth table as the data structure, and tries to minimize cost by considering both input and output variable orderings. Feasible moves are defined and an iterative approach based on simulated annealing (SA) is used to minimize the cost. Here also explicit synthesis is avoided during the process of looking for a good variable ordering.