电路宽度制导的布尔推理

作者：李光辉; 邵明; 李晓维

来源：计算机辅助设计与图形学学报, 2004, (11): 1568-1574.

• 电路宽度
• 布尔推理
• 二叉判决图
• 布尔可满足性
• 测试产生 circuit width
• Boolean reasoning
• binary decision diagram
• Boolean satisfiability
• test generation

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

• 单位
  中国科学院计算技术研究所; 浙江林学院; 中国科学院研究生院