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.