On the computational power of linearly transformed BDDs

Binary Decision Diagrams (BDDs) are a powerful tool and are frequently used in many applications in VLSI CAD, like synthesis and verification, However , they are very sensitive to the variable ordering and their size often bec omes infeasible. Recently, a new approach for BDD minimization based on lin ear transformations, i.e., a special type of spectral techniques, has been proposed. In this work we study linear transformations from a theoretical point of vi ew. We prove for a family of Boolean functions that the concept of linear t ransformations is really more powerful than "pure" BDDs, i.e., there is a c lass of Boolean functions for which an exponential difference in size exist s. Therefore, linear transformations can prevent an exponential blow-up of the BDD. (C) 2000 Elsevier Science B.V. All rights reserved.