For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Implicit Representation and Manipulation of Binary Decision Diagrams
Hitoshi YAMAUCHI Nagisa ISHIURA Hiromitsu TAKAHASHI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/03/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 8th Karuizawa Workshop on Circuits and Systems)
binary decision diagram (BDD), representation of Boolean functions, logic design verification, logic synthesis, implicit representation of graphs,
Full Text: PDF(747KB)>>
This paper presents implicit representation of binary decision diagrams (implicit BDDs) as a new effecient 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 repersentation. 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 maniqulate Boolean functions on this implicit data structure.