Synthesis of Reversible Circuits Using Decision Diagramm

Rolf Drechsler, Robert Wille

In: International Symposium on Electronic System Design. International Symposium on Electronic System Design (ISED-2012) December 19-22 Kolkata India 2012.


Due to its promising applications in domains like quantum computation or low-power design, synthesis of reversible circuits has become an intensely studied topic. However, many synthesis methods are limited by non-scalable function representations like truth tables. As an alternative, synthesis exploiting graph-based representations have been suggested. The underlying structure is a decision diagram (DD) that may vary regarding reduction methods, decomposition rules, or ordering restrictions. In this work, we review the progress of DD-based synthesis. It is shown that dedicated transformation rules can be applied to generate circuits for functions with a large number of inputs. We discuss the effect of different decomposition types or typical DD improvements like complement edges and re-ordering. Furthermore, we describe how DD-based synthesis can be exploited to transfer theoretical results known from decision diagrams into the domain of reversible circuits. Finally, further directions for future work are outlined.

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence