Implicit representation and manipulation of binary decision diagrams
This paper presents implicit representation of binary decision diagrams (implicit BDDs) as a new efficient data structure for Boolean functions. A well-known method of representing graphs by binary decision diagrams (BDDs) is applied to BDDs themselves. Namely, it is a BDD representation of BDDs. Regularity in the structure of BDDs representing certain Boolean functions contributes to significant reduction in size of the resulting implicit BDD representation. Since the implicit BDDs also provide canonical forms for Boolean functions, the equivalence of the two implicit BDD forms is decided in time proportional to the representation size. We also show an algorithm to manipulate Boolean functions on this implicit data structure.
binary decision diagram (bdd) representation of boolean functions logic design verification logic synthesis implicit representation of graphs