电路宽度制导的布尔推理

Circuit-Width Directed Boolean Reasoning

在基于逻辑电路的布尔推理过程中 ,经常用到二叉判决图 (BDD)与布尔可满足性 (SAT)相结合的算法 由于电路宽度能很好地反映电路的复杂性 ,提出了一种基于电路宽度的启发式策略 ,根据电路宽度来实现SAT算法与BDD算法的交替 充分发挥两者的优势 ,不仅可以防止因构造BDD可能导致的内存爆炸 ,而且还能避免SAT算法可能遇到的超时现象 与以往同类策略相比 ,该启发式策略更节省计算资源 ,提高算法性能 针对组合电路的测试产生实验 。

Binary decision diagram (BDD) and Boolean satisfiability (SAT) are common techniques of logic circuit-based Boolean reasoning scheme Since circuit-width is a good measure of circuit complexity, in this paper, we present a circuit-width based heuristic, which can be used to integrate the BDD technique and SAT technique for Boolean reasoning The scheme switches one engine to another in terms of the circuit-width, thus it takes both advantages of these two engines The circuit-width directed Boolean reasoning algorithm avoids the potential memory explosion caused by constructing the BDDs, and also prevents from the time-outs phenomenon of SAT techniques In comparison with the previous heuristic schemes in literature, the new schemes can save more computational resources, and improve the performance of Boolean reasoning algorithms On the automatic test pattern generation of combinational circuits, the experimental results demonstrate that the proposed heuristic scheme can be applied in Boolean reasoning effectively