一种基于SAT的电路错误诊断方法

摘要

本发明公开了一种基于SAT的电路错误诊断方法，首先将待诊断电路的网表结构、给定的观测集共同转化成CNF表达式，通过计算CNF表达式是否有解来判断电路是否存在错误；如果电路存在错误，将电路的网表结构划分成多个错误备选模块，对每个错误备选模块插入一个异或门组成的选择电路，将原电路网表转化成了诊断架构，然后提取该诊断架构的CNF表达式，对其进行SAT求解，根据解的形式判断该错误备选模块中是否有错误。本发明用基来简化SAT求解，并将计算基过程中含有的大量多变元多项式除法运算转化成乘法运算，从而加速基的计算过程。本发明能够高效的诊断和定位电路中的错误、缩短芯片的功能验证与调试时间。