BDD Based Decomposition of Logic Functions with Application to FPGA Synthesis

This paper presents a theory for (disjunctive and nondisjunctive) function decomposition using the BDD representation of Boolean functions. Incompletely specified as well as multi-output Boolean functions are addressed as part of the general theory. A novel algorithm (based on an EVBDD representation) for generating the set of all bound variables that make the function decomposable is also presented. We compared our BDD-based decomposition procedure with existing implementations of the Roth-Karp procedure and obtained significant speed-ups.