Access Restriction

Author Soeken, Mathias ♦ Wille, Robert ♦ Keszocze, Oliver ♦ Miller, D Michael ♦ Drechsler, Rolf
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2015
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Boolean functions ♦ Reversible logic ♦ Embedding
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.
ISSN 15504832
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2015-12-09
Publisher Place New York
e-ISSN 15504840
Journal ACM Journal on Emerging Technologies in Computing Systems (JETC)
Volume Number 12
Issue Number 4
Page Count 26
Starting Page 1
Ending Page 26

Open content in new tab

   Open content in new tab
Source: ACM Digital Library