A Lower Bound on the Gate Count of Toffoli-Based Reversible Logic Circuits

Takashi HIRAYAMA  Hayato SUGAWARA  Katsuhisa YAMANAKA  Yasuaki NISHITANI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E97-D   No.9   pp.2253-2261
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
Keyword: 
reversible logic circuits,  Toffoli gates,  lower bound,  logic minimization,  

Full Text: PDF(584.4KB)
>>Buy this Article


Summary: 
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.