Optimization of Structurally Synthesized BDDs

R. Ubar, T. Vassiljeva, J. Raik, A. Jutman, M. Tombak, and A. Peder (Estonia)


Binary decision diagrams, node reordering, simulation


Binary Decision Diagrams present an efficient way of modeling digital systems for simulation purposes. In order to take into account the need of representing faults directly in BDDs for fault simulation and test generation a special class of BDDs, refered to as structurally synthesized BDDs is used in the paper. It is shown that the efficiency of simulation using SSBDD highly depends on the distribution of the probabilities of input signal values and on the way the nodes are ordered in SSBDDs. A method and algorithm for optimal ordering of nodes in SSBDDs for the given distribution of the probabilities of input signal values is presented in the paper. Experimental data show an increase in the simulation speed by using SSBDDs with correspondingly reordered nodes.

Important Links:

Go Back