An r-valued m-variable reversible logic function maps each of the r^m input patters to a unique output pattern. The synthesis problem is to realize a reversible function by a cascade of primitive reversible gates. In this paper, we present a simple heuristic algorithm that exploits the bidirectional synthesis possibility inherent in the reversibility of the specification. The primitive reversible gates considered here are one possible extension of the well-known binary Toffoli gates.

We present exhaustive results for the 9! 2-variable 3-valued reversible functions comparing the results of our algorithm to optimal results found by breadth-first search. The approach can be applied to general m-variable, r-valued reversible specifications. Further, we show how the presented technique can be applied to irreversible specifications. The synthesis of a 3-input, 3-valued adder is given as a specific case.