Structural Heuristics for Test Pattern Generation Based on Satisfiability
Automatic Test Pattern Generation (A TPG) is one of the core problems in testing of digital circuits.ATPG algorithms based on Boolean Satisfiability (SAT) turned out to be very powerful, due to great advances in the performance of satisfiability solvers for propositional logic in the last two decades.SAT-based A TPG clearly outperforms classical approaches especially for hard-to-detect faults.The key to a SAT solver can be scalable is that it is able to take into account the information of high-level structure of formulas.This paper further improves to SA T-based ATPG with structural heuristics.It transforms D-chains to Boolean constraints and generate implication learning in the conjunctive normal form (CNF) clauses.Above all, a TRL-based (Total Reconvergence Line) BDD (binary decision diagram) learning heuristics is presented.This heuristics combine the respective strengths of BDD and SA T and circuit structure based methods to solve local signal correlations.The above learned information is then used to restrict and focus the overall search space of SAT-based test pattern generation.The experimental results show the validity of these heuristic learning technique.
test pattern generation boolean satisfiability (SAT) conjunctive normal form (CNF) binary decision diagram (BDD) heuristic learning
Liu Xin
School of Electrical & Electronic Engineering,Hubei University of Technology,Wuhan 430068,China
国际会议
哈尔滨
英文
288-292
2013-08-16（万方平台首次上网日期，不代表论文的发表时间）