Synthese reversibler Logik

Traditional technologies like CMOS more and more start to suffer from the increasing miniaturization and the exponential growth of the number of transistors. Thus, alternatives that replace or at least enhance traditional computer chips are needed in future. Reversible logic, and its applications in domains like quantum computation, low-power design, optical computing, DNA computing, and nanotechnologies, is such a possible alternative and thus has been 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 paper provides an introduction into the topic as well as an overview of selected synthesis methods for reversible logic. Thereby, we review reversible 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, afterwards we describe a new method that exploits Binary Decision Diagrams (BDDs) for reversible logic synthesis of significantly larger functions.