  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. In this paper, we study this issue. 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 as well as a corresponding embedding. For the
approaches we considered sums 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.

Emerging Technologies