SSBDDs: Advantageous Model and Efficient Algorithms for Digital Circuit Modeling, Simulation & Test

In this paper we sum up the research that was done during the last decade on the topic of Structurally Synthesized Binary Decision Diagrams (SSBDDs). We describe general properties of SSBDDs that make this model very efficient for circuit structure dependent methods and algorithms. In addition, we describe a deterministic test generation algorithm based on SSBDDs and four efficient simulation methods of different classes: logic simulation, multi-valued simulation, timing simulation, and fault simulation. We investigate and show the origins of their common advantages and draw conclusions, which hold for all the described algorithms. The analysis is made on the basis of experimental data acquired when applying these algorithms to ISCAS’85 benchmark circuits. The experiments unveil some new properties of these benchmarks, which we also present in our paper.