Contact

Johannes Kepler University Linz
Integrated Circuit and System Design
Univ.-Prof. Dr. Robert Wille
Altenberger Straße 69 | SCP3 0405
4040 Linz | Austria
robert.wille@jku.at
Tel: +43 732 2468 4739

Map and directions to JKU

One Pass Design of Reversible Circuits

Reversible computation is a heavily investigated emerging technology due to its promising characteristics in low-power design, its application in quantum computations, and several further application areas. The currently established functional synthesis flow for reversible circuits is composed of two distinct steps. First, an embedding process is conducted which makes non-unique output patterns distinguishable by adding further variables. Then, this function is passed to a synthesis method which eventually yields a reversible circuit. However, the separate consideration of the embedding and synthesis tasks leads to significant drawbacks: In fact, embedding is not necessarily conducted in a fashion which is suited for the following synthesis process. In addition, embedding adds further variables to the function to be synthesized which exponentially increases its corresponding representation in the worst case.

Here, we propose one-pass design of reversible circuits, which combines embedding and synthesis. This allows for conducting synthesis with a high degree of freedom, since the embedding that suits best is inherently chosen during synthesis. We propose two solutions (an exact an a heuristic one) following this scheme that improve the currently established synthesis flow by magnitudes in terms of runtime – allowing to synthesize a reversible circuit with a minimum number of lines for some of the frequently considered benchmark functions for the first time. Furthermore, a significant reduction of the costs of the resulting circuits (up to several orders of magnitude) is achieved with this new design flow.

With this package we aim for demonstrating the potential of the newly introduced one-pass design flow for reversible circuits, rather than for a fully-optimized synthesized method. While our implementation is based on QMDD-based synthesis, we encourage users of this package to incorporated the one-pass design flow for further functional synthesis approaches.

The implementation (including a README with instructions) can be downloaded by clicking on this link (5.2 MB).

Details of the approach are summarized in the paper entitled "One-pass Design of Reversible Circuits: Combining Embedding and Synthesis of Reversible Logic".

In case of questions/problems, please contact us through alwin.zulehner@jku.at and robert.wille@jku.at.

If you use the synthesis approach for your research, we would be thankful if you referred to it by citing the following publication:

@article{zulehner2018one,
   title={One-pass Design of Reversible Circuits: Combining Embedding and Synthesis for Reversible Logic},
   author={Zulehner, Alwin and Wille, Robert},
   journal={IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems},
   year={2018},
   publisher={IEEE}
}

More on our work on quantum computation is summarized in this page.