Representations of multiple-output functions using binary decision diagrams for characteristic functions

This paper proposes a method to construct smaller binary decision diagrams for characteristic functions (BDDs for CFs). A BDD for CF represents an n-i nput m-output function, and evaluates all the outputs in O(n+m) time. Mie d erive an upper bound on the number of nodes of the BDD for CF of n-bit adde rs (adrn). We also compare complexities of BDDs for CFs with those of share d binary decision diagrams (SBDDs) and multi-terminal binary decision diagr ams (MTBDDs). Our experimental results show: 1) BDDs for CFs are usually mu ch smaller than MTBDDs; 2) for adrn and for some benchmark circuits, BDDs f or CFs are the smallest among the three types of BDDs; and 3) the proposed method often produces smaller BDDs for CFs than an existing method.