Document Type

Conference Proceeding

Publication Date



Logic synthesis, Computer algorithims, Reversible logic


In this paper a synthesis algorithm for reversible ternary logic cascades is presented. The algorithm can find a solution for any reversible ternary function with n inputs and n outputs utilizing ternary inverter gates and the new (quantum realizable) UCTG gates which are a powerful generalization of ternary Toffoli gates and Generalized Ternary Gates [4]. The algorithm is an extension of the algorithm presented by Dueck, Maslov, and Miller in [3]. A unique feature of this algorithm is that it utilizes no extra wires to generate the outputs. A basic compaction algorithm is defined to improve the results of the basic algorithm. This paper also provides the groundwork for transforming any n*n Toffoli based binary synthesis algorithm into a ternary synthesis algorithm using the new UCTG gates.


This is the author's version of a paper which was subsequently published as "A transformation based algorithm for ternary reversible logic synthesis using universally controlled ternary gates." Proc. IWLS 2004 (2004): 345-352.

Persistent Identifier