Research On The Automatic Test Pattern Generation For The Digital Integrated Circuits

With the scale and complexity growing, digital Circuit testing is becoming more and more difficult. Traditional test pattern generations are no longer meeting the actual development demand of digital circuit. Novel test pattern generation and related algorithms need to be proposed constantly.Test pattern generations are chosen as objects, and fault coverage and time complexity are aimed in this dissertation. The major research contents and results are as follows:1) The Role and Status of test pattern generation is realized by introducing basic implementing process of VLSI. The main flow of IC testing is described too. Meanwhile the development and current study status of test pattern generation for digital circuits is summarized.2) This dissertation introduces basic concepts and algebra of satisfiability in detail. At same time, satisfiability algorithms are expatiated on classification, history, present research, and applications.3) A Non-backtracking Multipath Algorithm For Test Pattern Generation (NBMP) which different from traditional test pattern generation is proposed. A Non-backtracking Multipath AlgorithmsNBMP constructs singular cubes which only contain primary inputs and fault driving cubes which only connect with primary outputs. Then, NBMP produces test patterns using singular cubes and fault driving cubes. NBMP not backtrack during processing. It adopts scope restricting and multi-path searching strategy.The fault coverages of test pattern involving ISCAS85 benchmarks show that NBMP algorithm is superior to the traditional test pattern generation. Moreover, the time complexity is proved approximate linearity by the time complexity analysis and experimental results4) A test pattern generation algorithm for sequential circuits, Hierarchical andIncremental SAT-based Test Pattern Generation (HISAT), is shown in this dissertation. At the first stage, faults are sensitized to output in unit of non-branching path gradually. Optional branches are put into an implicit sensitized branch tree. The prediction strategy for conflicting paths speeds path selection. After that, CNF of Constraints and activation of faults generated in this stage are used for the incremental SAT executed in the second stage.At the second stage, Implication learning is implemented while values of nodes conflict. A new learn rule based on circuit structure is added into implication rules. Algorithm returns to preceding frame for searching satiable solution when the input is not primal input. An observable parameter helps searching along the direction of primal input. By the same way, algorithm goes to following frame for fault sensitization when the output is not primal output. An observable parameter helps sensitizing towards primal output too.The fault coverages involving ISCAS89 benchmarks show that HISAT algorithm is good at the fault coverage.5) Circuits redundancy identification on Boolean functions with paths (RDIBP) is proposed in this dissertation. The RDIBP algorithm which bases on Boolean functions with paths can identify redundancy nodes of digital circuits. Boolean function representations with intermediate nodes expressed as SOP are provided by RDIBP. Moreover, the traditional Boolean function simplifications are improved for finding redundant faults more easily. The circuit nodes are divided into groups according to correlation for increasing algorithm efficiency and preventing memory explosion. So RDIBP is ensured within a reasonable time by adjusting the control parameters.RDIBP experimental results on ISCAS85 ISCAS89 and ITC99 benchmark circuits are compared and analyzed with other algorithms. The experimental results indicate that it can identify redundancy efficiently.6) In this dissertation, a multi-objective heuristic for ICs test suite reduction is also given.The time efficiency of ICs test is reduced greatly because large numbers of redundant test cases exist in test suites. Four test suite reduction algorithms, which are Greedy algorithm, GE, GRE and H heuristic based on the importance of test cases, are compared and analyzed.Furthermore, a new heuristic (Priority-Selected) based on the essential cases and maximal fault coverage is presented for test suite reduction. Priority-Selected algorithm selects essential cases and deletes redundancy by computing test cases weights. Therefore, selection strategies are more reasonable and efficient.Two groups of test suits are used for efficiency of Greedy, GE, GRE, H heuristic and'Priority-Selected'.'Priority-Selected'is proved effective in test suite reduction. 7) Finally, the work of this dissertation is summarized and the prospective research is discussed.