Reversible logic became a promising alternative to traditional circuits because of its applications in emerging technologies such as quantum computing, low-power design, DNA computing, or nanotechnologies. As a result, synthesis of the respective circuits is an intensely studied topic. However, most synthesis methods are limited, because they rely on a truth table representation of the function to be synthesized. In this paper, the authors present a synthesis approach that is based on Binary Decision Diagrams (BDDs). The authors propose a technique to derive reversible or quantum circuits from BDDs by substituting all nodes of the BDD with a cascade of Toffoli or quantum gates, respectively. Boolean functions containing more than a hundred of variables can efficiently be synthesized. More precisely, a circuit can be obtained from a given BDD using an algorithm with linear worst case behavior regarding run-time and space requirements. Furthermore, using the proposed approach, theoretical results known from BDDs can be transferred to reversible circuits. Experiments show better results (with respect to the circuit cost) and a significantly better scalability in comparison to previous synthesis approaches.
Top1. Introduction
Reversible logic (Landauer, 1961; Bennett, 1973; Toffoli, 1980) realizes n-input n-output functions that map each possible input vector to a unique output vector (i.e., bijections). Although reversible logic significantly differs from traditional (irreversible) logic (e.g., fan-out and feedback are not allowed), it has become an intensely studied research area in recent years. In particular, this is caused by the fact that reversible logic is the basis for several emerging technologies, while traditional methods suffer from the increasing miniaturization and the exponential growth of the number of transistors in integrated circuits. Researchers expect that in 10-20 years duplication of transistor density every 18 months (according to Moore’s Law) is not possible any longer (Zhirnov, Cavin, Hutchby, & Bourianoff, 2003). Then, alternatives are needed. Reversible logic offers such alternatives as the following applications show:
- •
Reversible Logic for Low-Power Design:Power dissipation and therewith heat generation is a serious problem for today’s computer chips. Landauer and Bennett showed (Landauer, 1961; Bennett, 1973) that (1) using traditional (irreversible) logic gates always leads to energy dissipation regardless of the underlying technology and (2) that circuits with zero power dissipation must be information-lossless. This holds for reversible logic, since data is bijectively transformed without losing any of the original information. Even if today energy dissipation is mainly caused by non-ideal behaviors of transistors and materials, the theoretically possible zero power dissipation makes reversible logic quite interesting for the future. Moreover, in 2002 first reversible circuits have been physically implemented (Desoete & De Vos, 2002) that exploit these observations in the sense that they are powered by their input signals only and did not need additional power supplies.
- •
Reversible Logic as Basis for Quantum Computation:Quantum circuits (Nielsen & Chuang, 2000) offer a new kind of computation. Here, qubits instead of traditional bits are used that allow to represent not only 0 and 1 but also a superposition of both. As a result, qubits can represent multiple states at the same time enabling enormous speed-ups in computations. Even if research in the domain of quantum circuits is still at the beginning, first quantum circuits have already been built. Reversible logic is important in this area, because every quantum operation is inherently reversible. Thus, progress in the domain of reversible logic can directly be applied to quantum logic.
Further applications of reversible logic can be found in the domain of optical computing (Cuykendall & Andersen, 1987), DNA computing (Bennett, 1973), and nanotechnologies (Merkle, 1993).
However, currently the synthesis of reversible or quantum circuits, respectively, is limited. Exact (Hung, Song, Yang, Yang & Perkowski, 2006; Große, Wille, Dueck & Drechsler, 2009) as well as heuristic (Shende, Prasad, Markov & Hayes, 2003; Miller, Maslov & Dueck, 2003; Kerntopf, 2004; Maslov, Dueck & Miller, 2005, 2007; Gupta, Agrawal, & Jha, 2006) methods have been proposed. But both are applicable only for relatively small functions. Exact approaches reach their limits with functions containing more than 6 variables (Große, Wille, Dueck & Drechsler, 2009) while heuristic methods are able to synthesize functions with at most 30 variables (Gupta, Agrawal, & Jha, 2006). Moreover, often a significant amount of run-time is needed to achieve these results.