We propose a data structure for Boolean functions termed "the free Boolean diagram." A free Boolean diagram allows decision vertices as in the conventional binary decision diagram, but also allows function vertices corresponding to the AND and XOR functions. It has been shown previously that the equivalence of two free Boolean diagrams can be decided probabilistically in polynomial time. Based on the equivalence checking method, we develop a set of algorithms for the probabilistic construction of free Boolean diagrams from multilevel combinational logic circuits, and for their manipulation. These algorithms are modified versions of reduced, ordered binary decision diagram manipulation methods. We provide the implementation details of a free Boolean diagram package. We show that functions difficult to verify using reduced, ordered binary decision diagrams can be verified using the free Boolean diagrams package using substantially less memory.>

We propose a data structure for Boolean functions termed the Free Boolean Diagram (FBD). We extend a previous result to show that the equivalence of two Free Boolean Diagrams can be decided probabilistically in polynomial time. Based on the equivalence checking method, we develop a set of algorithms for the probabilistic construction of Free Boolean Diagrams from multilevel combinational logic circuits, and for their manipulation. These algorithms are modified versions of ordered Binary Decision Diagram manipulation methods. We provide the implementation details of a Free Boolean Diagram package. Results on applying this package to problems in combinational logic verification are presented.

The implications of the observation that the probability of the occurrence of a transition on a wire of a circuit affects both the average power dissipation and the random pattern testability of a circuit are investigated. It is shown that restructuring a logic circuit can significantly affect its average power dissipation. Various methods for the synthesis of combinational logic networks are presented and the effect of different algorithms on the power dissipation of the circuit is demonstrated. The dual problem of improving the random pattern testability of logic circuits is emphasized. It is shown that modifying the signal probabilities can significantly affect the random pattern testability of a circuit.>