Embedding of large boolean functions for reversible logic

Mathias Soeken, Robert Wille, Oliver Keszocze, D. Michael Miller, Rolf Drechsler

Research output: Contribution to journalArticlepeer-review

33 Scopus citations


Reversible logic represents the basis for many emerging technologies and has recently been intensively studied. However, most of the Boolean functions of practical interest are irreversible and must be embedded into a reversible function before they can be synthesized. Thus far, an optimal embedding is guaranteed only for small functions, whereas a significant overhead results when large functions are considered. We study this issue in this article.We prove that determining an optimal embedding is coNP-hard already for restricted cases. Then, we propose heuristic and exact methods for determining both the number of additional lines and a corresponding embedding. For the approaches, we considered sum of products and binary decision diagrams as function representations. Experimental evaluations show the applicability of the approaches for large functions. Consequently, the reversible embedding of large functions is enabled as a precursor to subsequent synthesis.

Original languageEnglish
Article number2786982
JournalACM Journal on Emerging Technologies in Computing Systems
Issue number4
StatePublished - Dec 2015
Externally publishedYes


Dive into the research topics of 'Embedding of large boolean functions for reversible logic'. Together they form a unique fingerprint.

Cite this