As billions of transistors are being placed on a
few square millimeters of silicon, power dissipation is becoming
a more crucial factor to be tackled for high performance
computing. Reversible circuit synthesis has been considered as a
promising direction for low power design due to its information
lossless behavior. In addition, it forms the basis for quantum
computing. However, synthesis of reversible circuits cannot be
achieved with the classical approaches for irreversible logic due
to the additional imposed constraints, consequently, neither fanout
nor feedback are allowed. Binary Decision Diagrams (BDDs)
have been proposed as a compact data structure to represent
a boolean function. They have been exploited to synthesize
reversible circuits through proper mapping of each BDD's node
into a cascade of reversible Toffoli gates. Nevertheless, reordering
of BDD's nodes before circuit synthesis significantly impacts
the overall cost of the synthesized circuit. In this paper, we
present a comparative study for BDD reordering algorithms
in terms of the cost of the generated reversible circuit. The
studied algorithms include greedy, dynamic programming, and
heuristic based approaches. The cost metric includes the number
of lines, gate count, and quantum cost. Experimental results show
that meta heuristic-based BDD reordering algorithms outperform
other algorithms in terms of the overall synthesized circuit cost
with slightly additional runtime. Thereafter, we conclude with a
proposal for a new framework for reversible logic synthesis.
Index Terms—reversible circuit, binary decision diagram, sifting
algorithm, quantum cost, transistor cost, gate count.

Conference Title

2018 SYMPOSIUM SERIES ON COMPUTATIONAL INTELLIGENCE

Conference Country

India

Conference Date

Nov. 18, 2018 - Nov. 21, 2018

Conference Sponsor

IEEE Computational Intelligence Society

Additional Info

Conference Website