For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Lower Bound on the Gate Count of Toffoli-Based Reversible Logic Circuits
Takashi HIRAYAMA Hayato SUGAWARA Katsuhisa YAMANAKA Yasuaki NISHITANI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2014/09/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Multiple-Valued Logic and VLSI Computing)
Category: Reversible/Quantum Computing
reversible logic circuits, Toffoli gates, lower bound, logic minimization,
Full Text: PDF>>
We present a new lower bound on the number of gates in reversible logic circuits that represent a given reversible logic function, in which the circuits are assumed to consist of general Toffoli gates and have no redundant input/output lines. We make a theoretical comparison of lower bounds, and prove that the proposed bound is better than the previous one. Moreover, experimental results for lower bounds on randomly-generated reversible logic functions and reversible benchmarks are given. The results also demonstrate that the proposed lower bound is better than the former one.