Shared Structurally Synthesized BDDs for speeding-up parallel pattern simulation in digital circuits

Fault simulation is a critical tool in design, analysis of testability and verification of circuits. BDDs are a well-known model for manipulating Boolean functions. We propose a new type of BDD in the form of Shared Structurally Synthesized BDD (S³BDD) for representing the structure and simulating of faults in digital circuits. The paper offers a formula for calculating the minimal size, a method for synthesis of S³BDDs and a method for parallel pattern simulation with S³BDDs. We demonstrate a considerable increase in the speed-up of simulation of digital circuits using S³BDDs.