MVLSC Home · Issue Contents · Forthcoming Papers
An Improved Lower Bound on the Gate Count for Toffoli-Based Reversible Logic Circuits Realizing Given Reversible Functions
Takashi Hirayama, Ryo Endo and Katsuhisa Yamanaka
This paper presents an improved lower bound, denoted as υ, on the number of gates in Toffoli-based reversible circuits that realize a given reversible logic function, where the circuits are assumed to consist solely of general Toffoli gates and employ no ancilla lines. The previous lower bound, σ-lb, introduced the characteristic vectors of reversible functions to formulate the theory of lower bounds. By carefully analyzing the cofactors of reversible functions, we refine the characteristic vectors and derive a new theoretical basis for improving lower bounds. We demonstrate that the proposed bound, υ, surpasses the previous bound, σ-lb, through mathematical proofs and experimental comparisons. Although the experimental gain is not substantial, υ is consistently greater than or equal to σ-lb. The refinement of lower bounds represents a valuable theoretical advancement. Such lower bounds on the gate count required to realize reversible logic functions are significant for estimating the cost of reversible circuits.
Keywords: Reversible functions, reversible logic circuits, Toffoli gates, lower bound, logic minimization, cofactors of the Shannon expansion