Embedding of Large Boolean Functions for Reversible Logic
Soeken M, Wille R, Keszocze O, Miller DM, Drechsler R (2015)
Publication Language: English
Publication Status: Published
Publication Type: Journal article, Original article
Publication year: 2015
Journal
Publisher: Association for Computing Machinery
Book Volume: 12
Pages Range: 41:1–41:26
Article Number: 2786982
Journal Issue: 4
DOI: 10.1145/2786982
Abstract
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.
Involved external institutions
Germany (DE)
Canada (CA)How to cite
APA:
Soeken, M., Wille, R., Keszocze, O., Miller, D.M., & Drechsler, R. (2015). Embedding of Large Boolean Functions for Reversible Logic. ACM Journal on Emerging Technologies in Computing Systems, 12(4), 41:1–41:26. https://dx.doi.org/10.1145/2786982
MLA:
Soeken, Mathias, et al. "Embedding of Large Boolean Functions for Reversible Logic." ACM Journal on Emerging Technologies in Computing Systems 12.4 (2015): 41:1–41:26.
BibTeX: Download