Testability Design And Implementation Based On Optimized ATPG (Automatic Test Pattern Generation) Algorithm

Automatic test pattern generation(ATPG) technology has been widely used in production test for chip manufacturing defects in. As a test vector generation tools, ATPG fault model according to the input, to generate simple, high coverage test vectors.But the traditional based on structured search ATPG algorithms, if you want to improve fault coverage, the need for a large number of repeated circuit backtracking search tentative, so spend a lot of time redundancy, making testing very expensive. And in this paper based on binary decision diagram of algebraic formulas and Boolean satisfiability SAT Both algorithms can effectively compress the test of time, it is through the gate-level circuit blocks into mathematical logic, propositional logic using algebraic problem solving to achieve rapid traversal purpose, then it takes too long to solve the problem of redundant backtracking searches, but also to improve coverage.In this paper, But for purely based on Boolean satisfiability SAT algorithms, as is the entire variable space of backtracking search for the basic framework, so the search space is large, the time complexity is high, will lead to the algorithm timeout. Because the search space is bigger, we need more time backtracking search, especially for unknown fault time will be longer. While those based only on the binary decision diagram BDD algorithm and may result in the construction of binary memory overflow and other thorny problems decision diagram BDD, in order to improve these shortcomings, we propose a formula different from the traversing heuristic search strategy, incremental the method of early identification undetectable faults, save unnecessary time searching judgment. An Algebraic Method This binary decision diagram BDD and SAT satisfiability of mixed, using Boolean difference equations thinking, to effectively play their respective advantages BDD and SAT in time and space, making the threshold judgment on the nodes do heuristic algorithm strategy each switch, replace operation. While avoiding occurs memory overflow problems and SAT algorithm timeout problems. when design the BDD.This study used a tool BDD algorithm development toolkit CUDD and SAT operation development toolkit Zchaff, used C++ code on the reference circuit to achieve a simulation of the mixed algorithms and application analysis, by comparison of the data with other algorithms, and found that hybrid intelligent algorithm using heuristic search algorithm than the traditional and traditional single algorithm in SAT test run time, back number, fault transmission path memory share performance has significantly improved, but also improve the efficiency of ATPG tool to generate vector.Practice has proved that the smart strategy can identify redundant faults in advance, unpredictable failures, but also to unpredictable failure to effectively search tree pruning, remove the path will lead to failure and node assignment mode, so that the number of test generation process back at least improve the processing efficiency of test generation speed and ATPG.Finally Analysis of the experimental results and algorithms advanced,I summarized the main work on the algorithm design and implementation, combing the innovation and practicality of the algorithm, and the next step to continue research work has been described, the semiconductor outlook the test will encounter challenges and research trends in testing technology and other aspects of the synchronization system complexity between modules.