Graph Transformation Meets Reversible Circuits: Model Transformation and Optimization
Reversible circuits provide the subject of a new promising direction of circuit design. Reversible circuits are cascades of reversible gates specifying bijective functions on Boolean vectors. As one encounters quite a variety of reversible gates in the li
- PDF / 349,752 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 96 Downloads / 177 Views
Abstract. Reversible circuits provide the subject of a new promising direction of circuit design. Reversible circuits are cascades of reversible gates specifying bijective functions on Boolean vectors. As one encounters quite a variety of reversible gates in the literature, there are many classes of reversible circuits. Two main problems are considered: (1) How can circuits of one class be transformed into the ones of another class? (2) How can circuits within one class be optimized with respect to certain measures? While reversible circuits are studied on the functional level and on the level of propositional calculus, there is also a visual representation used frequently for illustrative purposes in an informal way. In this paper, the visual description of reversible circuits is formalized by means of graph transformation. In particular, it is shown that the problems of model transformation and optimization can be investigated within the graph-transformational framework. This continues the authors’ earlier work on the generation, evaluation and synthesis of reversible circuits as graphs.
1
Introduction
Reversible circuits including quantum circuits provide the subject of a new promising direction of circuit design. Reversible circuits are cascades of reversible gates specifying bijective functions on Boolean vectors. As one encounters quite a variety of reversible gates in the literature like Toffoli gates with positive and negative control lines [1], Fredkin gates [2] and others, there are many classes of reversible circuits. These underlying gate classes are also called gate libraries. Two main problems are considered concerning model transformation, optimization and verification. (1) How can circuits of one class be transformed into the ones of another class? For example, Toffoli circuits with positive and negative control lines can be transformed into Toffoli circuits with positive control lines only. And the latter can be transformed into Toffoli circuits with two or less control lines. (2) How can circuits within one class be optimized with respect to certain measures? A typical measure is the number of gates in a circuit. If the gate costs matter, one tries to find equivalent circuits of shorter length. And there are other more sophisticated measures and criteria in which respects c Springer International Publishing Switzerland 2016 R. Echahed and M. Minas (Eds.): ICGT 2016, LNCS 9761, pp. 236–251, 2016. DOI: 10.1007/978-3-319-40530-8 15
Graph Transformation Meets Reversible Circuits
237
optimization is considered. A very interesting side effect of model transformation and optimization is that the underlying procedures preserve functional equivalence. Hence, circuits that can be transformed into each other are proved to be equivalent at the same time. While reversible circuits are studied on the functional level and on the level of propositional calculus, there is also a visual representation used frequently for illustrative purposes in an informal way. In this paper, the visual description of reversible
Data Loading...
