FAST GENERATION OF PRIME-IRREDUNDANT COVERS FROM BINARY DECISION DIAGRAMS

Manipulation of Boolean functions is one of the most important techniq ues for implementing of VLSI logic design systems. This paper presents a fast method for generating prime-irredundant covers from Binary Dec ision Diagrams (BDDs), which are efficient representation of Boolean f unctions. Prime-irredundant covers are forms in which each cube is a p rime implicant and no cube can be eliminated. This new method generate s compact cube sets from BDDs directly, in contrast to the conventiona l cube set reduction algorithms, which commonly manipulate redundant c ube sets or truth tables. Our method is based on the idea of a recursi ve operator, proposed by Morreale. Morreale's algorithm is also based on cube set manipulation. We found that the algorithm can be improved and rearranged to fit BDD operations efficiently. The experimental res ults demonstrate that our method is efficient in terms of time and spa ce. In practical time, we can generate cube sets consisting of more th an 1,000,000 literals from multi-level logic circuits which have never previously been flattened into two-level logics. Our method is more t han 10 times faster than ESPRESSO in large-scale examples. It gives qu asi-minimum numbers of cubes and literals. This method should find man y useful applications in logic design systems.