Synthesis of boolean functions in reversible logic

Traditional technologies like CMOS suffer more and more from the increasing iniaturization and the exponential growth of the number of transistors. Thus, alternatives that replace or at least enhance traditional computer chips are needed. Reversible logic, and its applications in domains like quantum computation and low-power design, is such a possible alternative and, thus, has become an intensely studied topic in the recent years. But, synthesis of reversible circuits significantly differs from traditional logic synthesis. In particular, fan-out and feedback are not allowed so that reversible circuits must be cascades of reversible gates. This requires completely new synthesis approaches. This chapter provides an introduction into the topic as well as an overview of selected synthesis methods for reversible logic.More precisely,we reviewreversible functions as well as reversible circuits and, in particular, focus on the embedding of irreversible functions into reversible ones. Then, we describe how such functions (given as a truth table) can be synthesized using exact as well as heuristic approaches. Since only small functions can be synthesized using a truth table as input, we describe a method that exploits Binary Decision Diagrams (BDDs) for reversible logic synthesis of significantly larger functions.