Research On Test Points Selection For Analog Fault Dictionary Techniques

The problem of analog fault testing and diagnosis raised a great deal of interest recently. Among the various analog fault diagnosis categories, fault dictionary approach is one of the most mature and applied techniques. The fault dictionary approach consists of three important phases: fault dictionary construction, test points (including test nodes and test frenquences, etc.) selection and fault diagnosis. Modern densely loaded circuit boards have posed problems for fault diagnosis with in-circuit testers because only limited physical access to the boards is allowed. Minimum set of test points selection method is, therefore, badly needed to reduce the number of test nodes. Test points selection is also an important mission of design for testability. Therefore, this dissertation focuses on the test points selection problem for analog fault dictionary techniques. The main content of this dissertation consists of test points selection based on Integer-Coded fault wise table technique (including local optimal and global optimal solution), test points selection based on Fault-Pair coding technique and tolerance handling methods.1. Research on test points selection approach based on the Integer-Coded fault table technique which is the most widely used in analog fault coding technique. Most of existed test points selection algorithms that based on this technique belong to greedy search method. They all consist of two basic elements: search strategy and test point evaluating criterion. These two elements are researched as follows.1) First, extensive theoretical analyses and comparisons are carried out to evaluate and compare time complexity and accuracy of the existed test point selection strategies and test point evaluating critera. Then, a few existed wrong conclusions are corrected, and a conclusion that search strategy is more important than test point evaluating criterion is drawn.2) Research on a new search strategy. Heuristic depth-first search algorithm A is applicated to test points selection. First, root node is initialized as all faults that to be diagnosed. Then, each candidate test point is used to expand this root node. Thirdly, among the expanded graph nodes, the one with the maximum faulty discrimination power is selected to be expanded for the next iteration. These steps are executed iteratively until all faults are isolated. Thus, the test points selection progress becomes a graph node expanding progress. Test points on the route from the target node to the root node make up of the final solution. Take advantage of the graph search method A , the proposed heuristic graph search method guarantee maximum information increase by adding a test point to optimum set each time. The proposed algorithm more accurately and efficiently finds the minimum set and is proven by statistical experiments.3) A more accuracy heuristic graph search algorithm based rollout algorithm RA is proposed. On a graph level, execute the A algorithm for each graph node, and then N_T optimum test points sets are obtained. Among these test points sets, find the one with the minimum cardinality, and the corresponding root node is added to the searching graph actualy. This algorithm is more accuracy when comparing to other near optimum algorithms and more efficiency than the broad-fist search (global optimum) algorithm.4) Global optimum test points selection algorithm A^*. Based on information theory and M-ary code rule, the methods of calculating heuristic evaluation function, constructing graph node and expanding node are given at first. Then a new heuristic graph search algorithm A^* is given. Statistical experiments carried out in the end show that this new algorithm can not only find the global minimum test points set but also decrease the time and space complexities dramatically.2. A fault coding method (Fault-Pair Boolean table technique) and test points selection method are given. In the Fault-Pair Boolean table, row represents fault pair consist of any possible different faults. Each test point n_j is represented by a binary column vectord . If the i^th fault pair is isolated by n_j, then d_ij=1. Compared to the Integer-Coded fault table technique, the fault encoding technique fully embodies the fault isolation ability of test point. Experiments show that the proposed technique can much more accurately find the optimum solution with less time complexity than the Integer-Coded fault table based exhaustive algorithm.3. The tolerance influence on test points selection and fault diagnosis is handled in this dissertation. Slope fault model is a unified modeling method for both hard fault and soft fault. Two methods are proposed to solve the tolerance problem reside in the slope fault modeling method. On one hand, the intersection of fault signature curve is obtained from real circuit. Therefore, the intersection point contains tolerance information. On the other hand, both analytical method and emulational method are given to calculate the slope signature area. These two methods solve the tolerance problem well. Test points selection problem under the tolerance influence is also disscused.4. The proposed test point selection algorithm is extended to system level sequential fault diagnosis. Test sequencing problem is decomposed into test points selection problem and test sequence arranging problem in this paper. Test points selection problem is solved by using A^*. First, the method of calculating heuristic evaluation function is given by using M-ary code rule. Then, an improved heuristic graph search algorithm A^* that can obtain all possible minimum test point sets is given. Test sequence arranging problem is solved by using AO^*. The heuristic evaluation function of AO^* is given based on the generalization of Huffman coding. The proposed method is fit for the process of DFT (Design for Testability). Experiments and time complexity analysis show that this new algorithm decreases the time complexities dramatically.