Implicit Representation and Manipulation of Binary Decision Diagrams

Hitoshi YAMAUCHI  Nagisa ISHIURA  Hiromitsu TAKAHASHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.3   pp.354-362
Publication Date: 1996/03/25
Online ISSN: 
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)>>
Buy this Article

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.