Sibling-substitution-based BDD minimization using don't cares

In many computer-aided design tools, binary decision diagrams (BDD's) are u sed to represent Boolean functions, To increase the efficiency and capabili ty of these tools, many algorithms have been developed to reduce the size o f the BDD's, This paper presents heuristic algorithms to minimize the size of the BDD's representing incompletely specified functions by intelligently assigning don't cares to binary values. Experimental results show that new algorithms yield significantly smaller BDD's compared with existing algori thms yet still require manageable run-times, These algorithms are particula rly useful for synthesis application where the structure of the hardware/so ftware is derived from the BDD representation of the function to implement because the minimization quality is more critical than the minimization spe ed in these applications.