Reversible logic synthesis with output permutation

Synthesis of reversible logic has become a very impor-tant research area. In recent years several algorithms – heuristic as well as exact ones – have been introduced in this area. Typically, they use the specification of a reversible function in terms of a truth table as input. Here, the posi-tion of the outputs are fixed. However, in general it is irrel-evant, how the respective outputs are ordered. Thus, a syn-thesis methodology is proposed that determines for a given reversible function an equivalent circuit realization modulo output permutation. More precisely, the result of the syn-thesis process is a circuit realization whose output functions have been permuted in comparison to the original specifi-cation and the respective permutation vector. We show that this synthesis methodology may lead to significant smaller realizations. We apply Synthesis with Output Permutation (SWOP) to both, an exact and a heuristic synthesis algo-rithm. As our experiments show using the new synthesis paradigm leads to multiple control Toffoli networks that are smaller than the currently best known realizations. 1