Wax. P bi. .flfiy‘x Town? “up“; . 9.; (:1: r I..- .z. , . 1 $5.3. .5 x- . 9.)! d ‘ 5s... . ..J..sx...u..‘ V . ‘ I.;... It ... . . V , . . 3M .1). i252. . 3 _. (curl... .3, .u.‘ . ‘ M529. 2 ‘0‘ '4 ’1) IllliHllUNlHllWlillil‘iliINIHIMIWIHIHHI 3 1293 018017 LIBRARY Michigan State University This is to certify that the dissertation entitled DEVELOPMENT OF EFFICIENT FAULT DIAGNOSABLE DESIGN METHODOLOGIES FOR ANALOG/MIXED-SIGNAL INTEGRATED CIRCUITS presented by Wei-hsing Huang has been accepted towards fulfillment of the requirements for Ph.D. . Electrical Engineering degree 1n @Joéefézfly Major proféssor Date 9/25/1998 MS U i: an Affirmative Action /Equal Opportunity Institution 0-12771 _ __.—-_.- PLACE lN RETURN BOX to remove this checkout from your record. TO AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE ma mu DEVELOPMENT OF EFFICIENT FAULT DIAGNOSABLE DESIGN METHODOLOGIES FOR ANALOG/MIXEDSIGNAL INTEGRATED CIRCUITS By Wei-hsing Huang A DISSERTATION Submitted to Michigan State University in partial fulfillment of requirements for the degree of DOCTOR OF PHILOSOPHY Department of Electrical Engineering 1998 ABSTRCACT DEVELOPMENT OF EFFICIENT FAULT DIAGNOSABLE DESIGN METHODOLOGIES FOR ANALOG/MIXEDSIGNAL INTEGRATED CIRCUITS By Wei—hsing Huang More and more mixed-signal devices are being designed recently for the applications of multimedia, wireless communication, and portable data systems. The analog circuit technology conventionally employed for such applications has been gradually switched to analog/digital mixed-signal circuit technology. Even though much more complicated digital circuits have been widely used in the DSP—based mixed-signal IC, analog circuits will remain for processing or interfacing analog signals. Integrating both digital and analog on a Single chip has improved performance and reduced board size and cost. However, the increasing complexity of mixed-signal circuits drastically reduces the controllability and observability of the circuit on the chip. As a result, testing and fault diagnosis of such complex circuits becomes very difficult and expensive. Therefore, the goal of the thesis study is to develop efficient diagnosable design methodologies for analog] mixed-signal integrated circuits and further integrate the methodologies for the development of an automated diagnostic test system. This study develops a framework of the automated diagnostic test system for analog circuits, including two major analysis tools Diagnosabiliry Analysis and Redesignabiliry Analysis, and Diagnosable Design Methodologies. The diagnosability analysis estimates the maximum diagnosability a circuit can achieve and locates sections of a circuit having poor diagnosability for a given set of test points, while redesignability analysis derives the input/output (I/O) relations of the portions having poor diagnosability and reconstructs them for diagnosability enhancement. The developed diagnosable design methodologies include two major processes: Test Points Selection and Diagnostic Test Programs Generation. The former process identifies the number of test points required to achieve the desired diagnosability and their locations, while the latter process aiItomatically generates test programs in analog version hardware description language, HDL-A. A system, namely ADTS (Automated Diagnostic Test System), is also developed to realize the building blocks of the developed framework. A Graphic User Interface (GUI) environment is developed to allow user to input the circuit description and to conduct the desired analysis or analyses. The system is written in JAVA, an object-oriented language, with a data structure that implements spare matrix techniques for efficient memory usage. To my parents and sister. iv ACKNOWLEDGEMENTS I sincerely thank Professor Chin-Long Wey, my thesis advisor, for his support and valuable suggestions throughout this research. It has been a pleasure to work under his supervision and I have certainly learned a lot from him. I would also like to express my gratitude to the members of my guidance committee, Dr. James A. Resh, Dr. Gregory M. VVIerzba, Dr. Diane T. Rover and Dr. Chester Tsai, for taking time to serve in the commit- tee. This research is sponsored in part by National Science Foundation under grant number MIP-9321255. I have to thank my fellow graduate students, Dr. Cheng-Ping Wang and Jin-Sheng Wang. I got much inspiration from the discussion with them. I will also thank Mohammad Athat Khalil for his help of editing and suggestions for this dissertation. A special thanks goes to my parents and my sister for the support and encourage- ment they have given me during the critical stage of my life. A final note of appreciation must be sent to all the nice people who have ever enriched my campus life while I stayed at Michigan State University. TABLE OF CONTENTS LIST OF TABLES .............................................................................................. LIST OF FIGURES ............................................................................................. Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 INTRODUCTION ......................................................................... 1.1 Objectives and Research Tasks .......................................... 1.2 Thesis Organization .............................................................. BACKGROUND ........................................................................... 2.1 Existing Analog Fault Diagnosis Methodologies .................... 2.2 Self-Testing Approach Fault Diagnosis Algorithm ............... 2.2.1 Component Connection Model ................................. 2.2.2 Self-Testing Approach .............................................. 2.2.3 Parallel Processing .................................................. 2.2.4 Diagnosability Enhancement ..................................... 2.2.5 Automatic Diagnosis Test System ........................... 2.3 Analog Hardware Description Language (HDL-A) ................. 2.4 Discussion ................................................................................. DIAGNOSABILITY ANALYSIS .................................................. 3.1 Upper Bound of Diagnosability ................................. 3.2 Diagnosability Analysis: Component Assignment Algorithm. _ 3.3 Discussion .............................................................................. REDESIGNABILITY ANALYSIS ................................................. 4.1 Redesignability/Unredesignability ............................................ 4.2 Redesignability Analysis: Component Assignment Algorithm 4.3 Discussion .............................................................................. TEST POINTS SELECTION ........................................................ 5.1 TPS Problem Statement ......................................................... 5.2 Algorithm Development .......................................................... 5.3 Improvement ........................................................................ 5.4 Discussion .............................................................................. vi viii Ox-i-‘st— 10 1 1 13 13 18 22 22 23 25 28 29 29 36 46 47 49 53 61 66 73 80 Chapter 6 TEST PROGRAM GENERATION ................................................ 6.1 HDL-A Modeled Control Sources ......................................... 6.2 HDL-A Modeled Pseudo Circuits ........................................... 6.3 Test Program Generation Process ............................................ 6.4 Discussion .............................................................................. Chapter 7 CONCLUSION .............................................................................. 8.1 Summary and Contributions ..................................................... 8.2 Future Work .......................................................................... OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO vii 83 84 87 90 94 95 95 97 99 Table 3-1 Table 3-2 Table 7-1 LIST OF TABLES Maximum Number of Column Vectors. ............................................ T- & M-loop Candidates. ................................................................ Main Functionalities of Developed ADTS. ................................... viii 32 Figure 1-1 Figure 1-2 Figure 1-3 Figure 2-1 Figure 2-2 Figure 2-3 Figure 2-4 Figure 2-5 Figure 2-6 Figure 3-1 Figure 3-2 Figure 3-3 Figure 3-4 Figure 4-1 Figure 42 LIST OF FIGURES Framework of an Automated Diagnostic Test System. Automated Diagnostic Test System. GUI Circuit Description. System Model. ................................................................................. Connection Matrixes: (a) Example CIrcuit; (b) Incidence Matrix; and (c) Fundamental Cut—set Matrix Sf and Fundamental Loop Matrix. Connection Matrix of Example Circuit. Self-Testing Approach: (a) Subdivision; (b) Pseudo Circuit; and (c) Its Connection Matrix. ....................................................................... Automatic Diagnosis System. ........................................................ A HDL-A Modeled Resistor. OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO (a) & (b) Schematic Diagrams of Example Circuit; and (c) Connec- tion Matrix X. OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO A Graph for the Circuit in Fig. 3-l(b) with test points. Example Circuit: (a) Connection Matrix Y; (b) Incidence Matrix; (c) A Graph; and (d) Generated D-Matrix. ................................. Graph Representation: (a) Components and Test Points; (b) T-loop for V45; and (c) M-loop for C2. ....................................................... Redesign Problem. OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO Example Circuit with Four Missing Components. ix 17 17 24 27 33 34 35 45 48 48 Figure 4-3 Figure 4-4 Figure 4-5 Figure 4-6 Figure 5-1 Figure 5-2 Figure 5-3 Figure 5-4 Figure 5-5 Figure 5-6 Figure 6-1 Figure 6-2 Figure 6-3 Figure 6—4 Figure 6-5 Example Circuit: (a) With Missing Components; (b) A Connection Matrix; and (c) A Graph. ............................................................... A Graph for the Circuit in FIg. 4-3(a) with test points and missing components. .................................................................................... Component Assignment Procedure; (a) A T-loop for V45 ; (b) A T- loop for V13; (c) A M-loop for C2; ((1) A M-loop for QBE; and (e) Component Assignment. Missing Component Compaction. Example Circuit: (a) Tree in A Circuit Graph; (b) Fundamental Loops; and (c) Cut-sets. .................................................................. Example for Test Point Selection Process: (a) Circuit Graph; (b) Simplified Version; (0) Path Selection; (d) Selected F-loop(s); (e) Cut-set Selections; and (t) Test Point Locations. .......................... Example for TPS Process; (a) Circuit Graph G’ with Tree; (b) G with Tree and Cut-set and (0) Test Point Locations. OOOOOOOOOOOOOOOOOOOOOO Example: (a) Graph; and (b) Adjacent Matrix. Example Graph: (a) Tree and Co—tree Edges; (b) Prime Implicant Chart; and (c) Cut-sets for g3 and g22. OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO Example Graph: (a) Tree and Co-tnee Edges and (b) Row Coverings. OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO Controlled Source Model: (a) Direct Control; and (b) Indirect Control. ...................................... - ....................................................... Controlled Source Models: (a) Current Source; and (b) Voltage Source. .............................................................................................. I-IDL-A Modeled Pseudo Circuit: (a) B 1_block; (b) A2_block; and (c) DIFF_block. ............................................................................... HDL-A Modeled Test Program Process. OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO HDL-A Descriptions: (a) for Interface; and (b) for Sources. .......... 52 54 59 62 67 67 72 74 76 82 85 86 89 92 93 Chapter 1 INTRODUCTION More and more mixed-signal devices are being designed recently for the applications of multimedia, wireless communication, and portable data systems. The analog circuit technology conventionally employed for such applications has been gradually switched to analog/digital mixed-signal circuit technology. Integrating both digital and analog on a single chip has improved performance and reduced board size and cost. Even though much more complicated digital signal processing circuits have been widely used, analog circuits will remain for processing or interfacing analog signals [1]. For mixed-Signal circuit testing today, the digital and analog components are tested separately. Procedure and equipment for testing stand-alone digital or analog chips have been well-established and implemented. However, manufacturers have found the costs associated with high-volume production of mixed-signal integrated circuits (ICs) are strongly affected by the cost of testing, where the analog circuit testing dominates [2,3]. Thus, developing efficient yet effective testing process for analog/mixed-signal circuits becomes a critical issue [4]. Why are analog/mixed-signal circuits so difficult to test? [In general, a designer constructs the topological structure of a circuit and then selects a set of nominal parameters and the associated parameters tolerances to meet the design specifications. Due to the random fluctuations in fabrication process and variations in the circuit operating conditions, the parameters and their tolerances are selected in such a way that the designed circuit has enough margins to pass the acceptability criteria. Statistical design approaches [5-7] are usually employed to select the nominal parameters and their tolerances for enhancing manufacturability and maximizing chip yields. As a result, the above design process guarantees: a designed circuit meets the design specifications if all parameter values are selected within their tolerances. However, this process does not guarantee: a designed circuit fails to meet the design specifications when a parameter deviation is far beyond its tolerance [4,8]. Therefore, analog circuits must be tested by their specifications instead of their parameters. Since fault behaviors may not be reflected properly even with performance deviation, what the practical fault models for analog circuits are becomes a controversial issue. Without such practical fault models, fault simulations, test generation, and fault coverage evaluation become meaningless. Testing and fault diagnosis are two important aspects in the design and maintenance of electronic circuits. Testing is to detect fault(s) in a circuit, while fault diagnosis is to de- tect and locate the fault(s) [9]. If a circuit has been found to be faulty during design char- acterization before it is in high volume production, it may be useful to diagnose the causes of the failure. Once faults are identified and located, a circuit can then be re-designed to be less sensitive to common failure mechanisms [2]. Fault diagnosis is an inverse problem of the sensitivity analysis problem. More specifically, the sensitivity analysis problem is to find the performance deviations from a set of given parameter deviations, while the fault diagnosis problem is to find the parameter deviations from a set of given performance de- viations. If a parameter deviation is out of its tolerance, the component associated with this parameter is then said to be faulty. Fault diagnosis of analog circuits and systems has been recognized as an extremely difficult problem because of the lack of failure data, continuum nature of analog circuits, component tolerance, and high nonlinearity of diagnosis equation [9-11]. A number of fault diagnosis algorithms have been developed to resolve the problem [9-29]. Among them, an efficient self-testing approach fault diagnosis algorithm and an analog automatic test program generator (AATPG) were developed for both linear and nonlinear analog cir- cuits [16-18]. To develop efficient fault diagnosable design methodologies for mixed-signal ICs, the following important issues must be addressed: (1) given a circuit topology, how to mea- sure the circuit’s diangosability for a given set of test points; and (2) given a circuit topol- ogy, how to select a set of test points that meets the desired diagnosability. It is important for a designer to know what the maximum diagnosability a circuit can achieve and which portion of the circuit having poor diagnosability. The information allows estimation of a Circuit’s diagnosability before the fault diagnosis is attempted. Hence any potential problems can be located early in the design phase, allowing modifica- tions to be introduced to improve the final diagnosability of the circuit. For analog circuit design, a designer usually takes a relatively short period time generating a cicuit topology and spends the remaining design time adjusting design param- eter values to meet the design specification. Usually , there are some portions having poor testability/diagnosability which the designer cannot discover beforehand. Once those por- tions are found, inserting extra test points may be needed for improving the observability and controllability of the circuit. However, inserting test points can cause the circuit per- formance to deviate from the design specification due to the loading effect. Therefore, the designer may need additional design time and efforts to re-adjust the parameter values again. Evidently, an efficient test selection process can greatly reduce the design time and efforts. 1.1 Objectives and Research Tasks The objective of the thesis study is to develop efficient diagnosable design methodologies and automated diagnostic test system for analog circuits. The developed methodologies and system will then be extended for mixed-signal circuits [30]. Fig. 1-1 illustrates the framework of the development in this study. Based on the self-testing approach fault diagnosis algorithm developed in [16-18], the framework is comprised of two major analysis tools: Diagnosability Analysis and Redesignability Analysis, and the developed Diagnosable Design Methodologies. The diagnosability analysis estimates the maximum diagnosability a circuit can achieve and locates sections of a circuit having poor diagnosability for a given set of test points [31], while redesignability analysis derives the input/output (I/O) relations of the portions having poor diagnosability and reconstructs them for diagnosability enhancement [32]. In addition, at this momemnt, the developed diagnosable design methodologies include two major processes: Test Points Selection and Diagnostic Test Programs Generation. The former process identifies the number of test points required to achieve the desired diagnosability and their locations, while the latter process automatically generates test programs for fault diagnosis. For the mixed-Signal circuit applications, hardware description languages (HDLs), such as HDL-A [33,34] for analog circuits and VHDL [35] Fault _ Hardware DiagnOSiS Description Algorithm Language Diagnosable Desi n Methodo ogie Diagnosability Analysis Redesignabili Analysis 9 Automated Dia nostic ystem Fig. 1-1 Framework of an Automated Diagnostic Test System for digital circuits, will be used to develop automatic test program generators. With the successful development of hierarchical testability design system that define realistic fault models and generate test patterns for analog/mixed-signal circuits in [4], an automated diagnostic test system is also developed in this Study. A software program, namely ADTS (Automated Diagnostic Test System) [36], as the system window shown in Fig. 1-2, is developed to realize the functional blocks in Fig. 1-1. A Graphic User Interface (GUI) environment, as Shown in Fig. 1-3, allows user to input the circuit description and to select the analysis tools. The system contains two major processes: Circuit Description and Analysis Engine. The former process constructs the database for the analysis use, while the analysis engine performs the desired analysis/analyses. The system is written in JAVA, an object-oriented language, with a data structure that implements spare matrix techniques for efficient memory usage. 1.2 Thesis Organization The dissertation is organized as follows: Chapter 2 reviews some of existing analog fault diagnosis techniques and the self-testing approach fault diagnosis algorithm. Chapter 3 presents the diagnosability analysis process. Given a circuit topology and a set of test points, the upper-bound diagnosability of the circuit can be estimated. If the upper-bound diagnosability is less than the desired one, then redesign or adding extra test- ing points may be needed. Otherwise, the diagnosability analysis process will take place. Two major tasks are involved in this process: Component Assignment and Diagnosable Configuration Generation. The former generates the candidate diagnosable configurations based on the given circuit topology and test points information, while the latter selects the A.D .T.S . Mmfied Dannie Test Syfian Wei-hsing Huang ichigan State University Fig. 1-2 Automated Diagnostic Test System Fig. 1-3. GUI Circuit Description. one with the maximum diagnosability from the candidates. The process will also identify the portions having poor diagnosability. Chapter 4 describes the redesignability analysis process which checks if the rede- sign is feasible. An efficient algorithm for the redesign analysis will be presented. Chapter 5 presents the test points selection process, while Chapter 6 discusses the test program generation process. The test points selection problem is formulated as a min- imum covering problem. Thus, efficient algorithms are developed to resolve the problem and to speed up the selection process. Chapter 6 describes the development of automatic test program generation prOcess using HDL-A. Finally, Chapter 7 summarizes the thesis, gives a concluding remark and some future research directions. Chapter 2 BACKGROUND With the ever-increasing complexity and compactness of analog/mixed-signal inte- grated circuits, analog testing and diagnosis has become more and more important. Con- ventionally, analog circuits are tested with bed of nails, i.e., every component on the unit under test (UUT) is probed and measured. However, with the progress of the modern packaging technology, as well as the increasing density of the number of components in a UUT, it is impractical to provide proportionally more 1/0 pins. As a result, the number of test points that can be externally accessible will be limited for modern circuit testing. Fault detection and location in electronic systems are performed with measurement done on these limited number of test points. Thus, an effective algorithm which utilizes these test points efficiently plays a key role in fault analysis. Section 2.1 reviews some of existing analog fault diagnosis algorithms. Section 2.2 discusses salient features of the self-testing approach fault diagnosis algorithm developed in [16-18]. Section 2.3 presents the circuit modeling schemes using I-IDL-A. Finally, Sec- tion 2.4 addresses some issues related to the thesis research. 10 2.1 Existing Analog Fault Diagnosis Methodologies Until recently, effort at producing algorithms for automatical diagnosis process has concerned mainly digital circuits for which more or less satisfactory solutions have been reached. Analog circuits, on the other hand, have received much less effort. The difficul- ties and problems are due to the following [37]. 0 Relations among input and output signals in analog circuits are somewhat intricate and not “exact”. For instance, the truth tables of digital circuits will not work for analog circuits where only approximations allow modeling. 0 Analog systems are frequently nonlinear. The noises and the values of parameters of the components exhibit large deviations. Consequently, the tolerance problem has to be considered even for a good circuit and deterministic approaches are most often inefficient. 0 Fault categories as well as their statistical distributions and correlations are not known with precision. Thus, fault classification and modeling based on statistical . result need more elaboration. O Use of analog components is not as systematic as is the case for digital compo- nents. To alleviate the above limitations, two approaches are often employed in analog fault analysis [11,37]: the simulation-before—test (SBT) approach and the simulation-after- test (SAT) approach. The SBT approach requires the simulation of different possible faults and storage of the results as a fault dictionary. The faulty subnetwork responses are com- pared with the dictionary entries and the closest entry to the responses determines the pos- ll sible faults. The method is usually suitable for single catastrophic fault location. For multiple faults situation, the size of the dictionary becomes very large and the method is impractical. In the SAT approach, diagnosis algorithms are deployed so that the faulty net- work responses can be conducted to locate the faulty components. In both cases, there exists a trade-off between the computational effort and the number of accessible nodes. Based on these two categories, a number of analog fault diagnosis techniques have been proposed [37]. They can be roughly categorized as the following three methods: Estimation Methods: These methods address detection, location, and identification. Two general classes of methods belong to this category: deterministic (or quasi- deterministic methods) and probabilistic methods. The former methods consist of determining from measurements as well as the actual values of the parameters of the system under test. In the latter methods, the distribution laws of measured responses are determined from the tolerances on the parameter values and their associated statistical distributions. Topological Methods: The basic data to be handled are the system’s structure and, possibly, analytic relations between input variables and measured responses. Such methods apply to detection and location. These methods rely on some graphical analysis techniques. Taxonomic Methods: The system’s reference responses corresponding to each potential fault condition are Stored into fault dictionary. During actual testing, mea- surement results are compared to the responses recorded and the detected fault is the one for which the set of measurements differs the least. The accuracy of such methods is directly dependent on how comprehensive the fault dictionary is. 12 2.2 Self-Testing Approach Fault Diagnosis Algorithm The self-testing approach fault diagnosis algorithm developed in [16—18] is a SAT approach With a single test vector. This sub-section describes the system model, the self- testing approach, and its implementation. In addition, the parallel processing capability [38] and diagnosability enhancement [39,40] are also discussed. 2.2.1 Component Connection Model The fault diagnosis algorithm developed in [16,17] is based on an interconnection system model known as the component connection model (CCM), as shown in Fig. 2—1. Assume that the UUT is comprised of n components, k external test inputs, and m external test points. The UUT characterizes its components together with a connection equation as follows, a = Lllb + L120 (2'1) y = 1or" + 142“ where a=col(ai) and b=col(bi), i=1,2,..,n, are the column vectors of component input and output variables, respectively, and u and y are respectively the column vectors of external test inputs applied to the system and the system responses measured at the various test points. The connection matrix, L-matrix, is generally sparse and its entries are l, 0, or -1. The entries of vectors a and b are either node voltages or branch currents.iFor analog lin- ear circuits, the component equations is modeled in the frequency domain [16], while those in nonlinear circuits are modeled in the time domain [17]. Note that the components in the CCM model can be either discrete components, individual chips, or subsystems. l3 l \\\\\‘ Components 31 \ 93 9-: R\\\l u: System input y: Output Response Fig. 2-1 System Model D1 _ 3 L1 2 R1RLC1C2C3Lng 00.0.0 —— - 3 R15— NodeO 1-10-1-10 0 czfifi C3:: éRL Nodel _ -1 010 0 0 1 Node2 - 01 01 1 -10 VIN 0 Node3 00-1001-1 (a) Example Circuit (b) Incidence Matrix 1000111 0401000— ' ’ B =110 010 0 Sr=01011-1-1 {1110010 001004" 1110001 (c) Fundamental Cut-set Matrix Sf and Fundamental Loop Matrix Bf Fig. 2-2 Connection Matrixes l4 1 Thus, the system model can be applied for analog, digital, and mixed-signal integrated cir- cuits and systems. To construct the connection matrix, given a circuit schematic diagram, as shown in Fig. 2-2(a), an incidence matrix A, as Shown in Fig. 2-2(b), describes the interconnections between each component, where a directional notation is used where branch current flow out of node labeled as “-1” toward node labeled as “1”. By performing Gaussian elimina- tion process on matrix A, the fundamental cut-set matrix Sf can be obtained. Sf describes the relations between the current flow through each components and the nodes it is con- nected. It satisfies the Kirchoff’s current law (KCL) and has the form of Sf = [1r l D], as Shown in Fig. 2-2(c), where D is a r x (b-r) matrix and L is a r x r identity matrix. Simi- larly, the fundamental loop matrix which describes Kirchoff’s voltage law (KVL) can be obtained by simply transposing D matrix as Bf = [-Dt I 1“], where Dt is the transpose matrix of D and IM is a (n-r) x (n-r) identity matrix. C C Let I: [1"] and V=[:'] , where It and Ic are the currents in the tree and co-tree edges, respectively, and Vt and Vc are the voltages in the tree and co-tree edges, respectively. According to KCL and KVL, we obtain 0=S,I=I,+DIC;ando=13fv=-Dtv,+vc (2-2) lé:l=l:r‘oll¥:l If we choose the component input vector a= [5‘] and the component output vector Therefore, C 15 b: [:1 , then we have the matrix L1 1: [ or ID] . If all test points are chosen from either It or - D o C Vc, then the matrix L21 can be constructed from the L” matrix. Fig. 2-3 illustrates the connection matrix L for the example circuit in Fig. 2-2(a). For linear circuits, the component equation is modeled in the frequency domain as follows, b = Z a (24) where Z=diag(Zi), i=1,2,..,n, is a frequency domain composite component transfer matrix. Each Zi=Zi(s,r) describes the i-th component of the UUT, where r=col(ri) is the column vector of unknown component parameters and s is the complex frequency variable [16]. Typically, the unknown component parameters take the form of resistance, capacitance, inductances, and amplifier gain, etc. For nonlinear circuits, the component characteristics are expressed as follows, *1 = Fi(xi,ai); bi = Gi(xi,ai); xi(0)=0; i=1,2,..,n (2-5) where xi’s are the component state variables. The component equations in (2-5) are modeled in the time domain [17]. For notational purpose, we stack the individual component equations together to form the following composite component equations; x = F(x,a); b = G(x,a); x(0)=0; (2-6) 16 lFl1 VC1 IDl VCZ IL1 V03 VRL |D1 IL1 VRL _ # ' 1 HHOHOOO — OOOOI—‘Oo i—‘i—‘Ol—‘Ol—‘O OOOOHOH HHOOOOO OOHOHOH OOHOHOH HHOHOOO J l—‘OO I OOH l—‘OO OOH Hoo OHH OHH "ii-"5 o VR1 lC1 VDl ICZ VLl I03 IRL VIN Fig. 2-3 Connection Matrix of Example Circuit in Fig. 2-2(a) \\\\\\\V \\ N I Hoqooo 00°C 7 9.2 = hm _./am+lbm+l % = . /321:|_2 ///////// (a) “as“ '3 32 m1 000 $31- = "3.3.3.... 38 i 3 3 Viii'" -'1'"d'-'1' 1C] 0 1 0 1C3 0 0 O _._s L ‘ ...~.-.-..- ...-......- I 0000 OQOH opoo HOHO ................. ODD-“30°C owdooo I HHQOOH I oofipoo I I I E] Components in Testee Group Components in Tester Group _VD1_ —ID1 1 1C2 a1_ VC2 VLl " IL1 ul —IRI_ 1 £2 £2 VC1 y3 LVC3_ *— — (C) VRI‘ b2: ICl IC3_ Fig. 2-4. Self-Testing Approach: (a) Subdivision; (b) Pseudo Circuit; and (c) Its Connection Matrix. n 2.2.2 Self-Testing Approach Conceptually, at each step of the diagnosis process, the components are subdivided into two groups, namely Tester Group and Testee Group. Assuming that the components in the Testee Group, i.e., components #(m+1) to #n, as Shown in Fig. 2-4(a), are all good, (The assumption will be justified from the test results) and thus their component characteristics are known. From these known component characteristics and both known It and y, we estimate the function behaviors of the components in the Tester Group, i.e., components #1 to #m. For a given component subdivision, the circuit in Fig. 2-4(b), referred to as "pseudo circuit", is reconstructed from the original one in Fig. 2-4(a). Since we use the components in the Tester Group to test those in the Testee Group, hence it is "self-testing" approach. A number of component subdivisions may be needed and a decision algorithm is required to identify the faulty component(s). Mathematically, at each step, the connection equations in (2-1) are partitioned as follows, where Tester Group and Testee Group are represented by superscripts "1" and "2", respectively. a1: L1111b1+L1112b2+ L121 u (2-7a) a2 = L1121b1+ L1122 b2 + L122 u (2-7b) y = L211 b‘ + 1412 b2+ L22 u <2-7c) the component equations for linear case are also partitioned as follows, b1=Z1a1 (2-8a) b2=22a2 (2-8b) 18 and those for nonlinear case are x' = F1(x1,a‘);b‘= G'(x‘,a‘); x1(0)=0 (2-9a) x 2 = F2(x2,a2); b2 = G2(x2,a2); x2(0)=0 (2-9b) Therefore, a pseudo circuit can be derived and expressed as follows [16,17] a1 = I rval:=1.0e3; PROCEDURAL FOR ac, dc, transient => irl:=[pos,neg].v/rval; pos.i%=irl; neg.i%=-irl; vrl:=[pos,neg].v; END RELATION; END ARCHITECTURE res; Fig.2-6. A HDL-A Modeled Resistor 27 2.4 Discussion AS discussed in Section 2.2.1, the connection matrix L1 and the parameters in both a and b are derived from the transformation of the incident matrix of a given Circuit. Since the transformation is not unique, a number of diffemt connection matrices may be gener- ated. In other words, for a circuit topology and a set of test points, a number of L21 matri- ces may be generated. Interestingly, some transformations may be t-dignosable, but others may be not [31]. For simplicity, a transformation which makes the circuit to be t-diagnos- able is referred to as diangosable configuration. This implies that, for the same circuit tol- oplogy and test points, due to non-unique transformations, some configurations are diagnosable. Therefore, the question is how to generate a diagnosable configuration from the given circuit topology and test points. In addition, given a set Of test points, it is impor- tant to know what the maximum diagnosability a circuit can achieve ? which configuration achieves the maximum diagnosability .7 and which configurations have poor diagnosabil- ity? These issues will be addressed and investigated in the next chapter. 28 Chapter 3 DIAGNOSABILITY ANALYSIS This chapter presents the diagnosability analysis of a circuit from its topology and test points. Section 3.1 discusses the upper bound of the diagnosability given a set of test points. Section 3.2 presents a component assignment algorithm that makes I41 matrix with the highest global column-rank. Example is provided to demonstrate the procedures of developed analysis process. Finally, summary and discussion for the diagnosability analysis are given in Section 3.3. 3.1 Upper Bound of Diagnosability Consider a circuit that has 11 components and m test points. A test point can be either current measurement, referred to as IM-test point, or voltage measurement, referred to as VM-test point. Let m1 and mv be the number of IM- and VM-test points, respectively, where m1+mv=m. For the Lu matrix, since it is extracted from L11 matrix given in (2-3), 0 [if] . Where E1 is an mI'l3)"nl matrix, E2 is an “Why-Dz 52 it will have the form of L21: [ matrix, and n1+n2=n. In general, 111 2 m and n2 2 m. Let r1 and r2 be the global column- ranks of E1 and F12, respectively. Apparently, m1 2 r1 and mv .2 r2. The following lemma and theorems result. 29 Lemma 3-1. The global column-rank of L21 is r = min{r1,r2}. M: It is obvious that any columns in [g] are linearly independent of those in [El] . The 2 0 global column-rank of [2] is the same as that of E2, and both [E 1] and E1 have the same 0 2 rank. This concludes r = min{r1,r2}. W. The upper bound of the diagnosability of a circuit is min{m1,mv}. PM: Since E1 is an mI-by-nl matrix, its global column-rank r1 S m. Similarly, r2 S my. Therefore, by Lemma 3-1, the global column-rank of Ln is 1=min{r1,r2} S r, SmI and r S r2 S mv. This concludes r S min{m1,mv}. Theorem 3-1 shows that diagnosability is limited by min{m1,mv}, instead of the number of test points, m, in [39]. In fact, a tighter upper bound can be Obtained from E1 and E2131]. Tammi-2. The global column-rank of E1 is II S mI-l , if n1 > C(mllmI/ZI)+K, where K=l for m1=2, 3; and K=O for m1 2 4 Note that C(x,z) is the combinations of taking z out from x, and [l is the ceiling function, i.e., [ml/2] is the maximum integer Z mI/2. For mI=4, each column vector in E1 is one of the following 16 patterns, Pattem—9 0 I 2 3 4 5 6 7 8 9 10 II 12 I3 14 15 Index 0 0 0 O l O 0 1 O l l 0 l l 1 1 O 0 0 1 0 0 1 0 1 0 l l 0 l 1 1 O 0 1 0 0 l O O 1 1 0 l l 0 1 l 0 1 0 0 O 1 l l 0 0 0 l l 1 0 l 30 groups, referred to as p-Group, O S p S 5. For simplicity, O-Group and S-Group are called trivial-p-Groups, and the remaining ones are non-trivial-p-Groups. It can be easily shown that the global column-rank of the matrix formed by any non-trivial p-Group is r1=m1=4. However, if a matrix is formed by any non-trivial p-Group with a column vector from the other p-Groups, it will not have a full global column-rank, i.e., r1 < m1. Therefore, we con- clude that the global column-rank of a matrix formed by two or more p—Groups is r, < m1. An interesting question is: if a matrix is formed by the distinct column vectors selected from the 16 patterns, what is the maximum number of column vectors the matrix has a fill! rank, i. e., r1=m1=4 ? Note that the number of column vectors in a p-Group is C(mI,p), and the maximum C(m1,p) occurs at p=|-mI/2-I. Therefore, the solution to the above question is C(mIImI/zli = (4,2) = 6. In other words, El does not have a full rank, r1 < 4, irnl > 6. This has been verified by simulation, where all possible E1 with more than 6 distinct column vectors selected from the 16 patterns are simulated and the resultant ranks are less than 4. For mI=2, each column vector will be one of the following four patterns, Pattern index —> 0 1 2 3 0 0 1 1 0 1 0 1 Since the global column-rank of the matrix formed by Patterns #l—#3 is 2, the maximum number of column-rank is C(mll mI/2-i)+1=C(2,1)+1=3. Similarly, for m1=3, the maximum number is also C(mIJ-mI/ZIHI, i.e., C(3,2)+1=4. Similar to Lemma 3-2, the following lemma also concludes. W. The global column-rank of F4 is r2 S mv-l, if n2 > C(mvlmv/2I)+K,where K=l for mv=2, 3; and K=O for mv 2 4 31 The maximum number Of column vectors for various m1 are tabulated in Table 3-1. Table 3-1. Maximum Number of Column Vectors m; (or mv) 2 3 4 5 6 7 # of col. vectors 3 4 6 10 20 35 W. (a) The upper bound of the diagnosability of a circuit is (mv- 1 ) if mv 2 m1 and n2 > C(mvl mV/21)+I<; where K=I for mv=2, 3; and K=O for my 2 4; and (b) The upper bound of the diagnosability of a circuit is (ml-1) if m1 2 my and 111 > C(mll m1/2-|)+1<, where K=l for m1=2, 3; and K=0 for m1 2 4. Consider the example circuit in Fig. 3-1 with the selected four test points. Fig. 3-2 illustrates a graph that describes the example circuit in Fig. 3-1(c) and test points. The edges in the graph represent the components in the circuit. The VMTP components for both VM- test points, V13 and V45, are not the real components in the circuit, and the edges repre- senting these components are referred to as virtual edges. In this figure, the graph has 11 real edges and two virtual edges, where n1=5, n2=6, and m1=mv=2. By Theorem 3-2, the upper bound of diagnosability is 1, i.e., the set of test points is only good for at most l-diag- nosability. In fact, the circuit with the connection matrix in Fig. 3-1 is l-diagnosable, while that with the connection matrix in Fig. 3-3(f) is O-diagnosable. 32 m ] mm uvv [ .0000000000130000—Iwu m _ + _11 Cm _ bwwmwwmmmmmm. _14000000000"11..00_ (C) . 00000000400.001..0 . 14010000010" 11.100 . 10001000000.1000 . 10001000000" 1000 . 04014000000.01..00 . OOOOOIJJOOOHOOJO Lzr L11 . 00000400400.0001.. . 10000000000"1000 . 00000100101.0001 . 00.400044401100130 VCEQ VCE l3 VC2 IRL VR3 1C1 1R1 V45 [v y Fig. 3-1: (a)&(b) Schematic diagrams of example circuit; (c) Connection matrix X; 33 IM-Test Points [:1 VM-Test Points Fig. 3-2. A graph for the circuit in Fig. 3-1(b) with test points. 34 1 CC m V V [ 00000004000 _000000I.1.I.II + S 11C2 QQ wmwwmmmmmee_ 0002 OOIJ 114101000000 _ 10001000000 14110000000 14000000000 10000000000 00004000000 00000100044 00000000400 00000000404 00000001101. 0000004 4 c u -1 1400 1000 1400 1400 1000 0000 0040 0040 0044 0011 VBEQ VCEQ m m m1 m1 RC K2 RE WE VB (a) 0 3 E R3 RE Cl 0 Tree Edges QC 1 4— 4 -1 4 0 0 0-1 0 011000 000n:1 001:04 OOnIIO OOOIAU 001:40 10n:40 01:400 1n:u00 1.1.000 120000 — : Co-tree Edges (e) Fig. 3-3. Example circuit: (a) Connection Matrix Y; (b) incidence matrix; (c) a graph and (d) generated D—matrix. 5 3.2 Diagnosability Analysis: Component Assignment Algorithm The connection matrix Of a circuit is derived from the incidence matrix A of the cir- cuit together with the component assignment. Our objective is to develop an efficient com- ponent assignment algorithm that provides a connection matrix with the maximum diagnosability [31]. These assignments are based on the circuit topology, which is applica- ble to not only the diagnosability analysis, but also the redesignability analysis presented in next chapter. Consider a circuit consisting of 11 components and m test points which includes m1 IMTPs and my VMT P. According to (2-2), nodal analysis and loop analysis are performed for tree and co-tree elements, respectively. Therefore, the fnst assignment rule is obtained as follows, REILL- (a) All IMTP components are assigned to the tree; and (b) All VMTP components, except the virtual ones, are assigned to the co-tree. Each component of an electrical network can be constructed so that it is included in at least one loop. Thirs, two types of loops are then defined in this implementation: T-loop and M-loop. A T-loop is a loop associated with a VMTP component, while an M-loop is a loop associated with a non-TP component, i.e., neither an IMTP nor VMTP component. A T-loop, associated with a VMTP component, may contain IMTP components(s) and non- TP components, but not the VMTP components. On the other hand, an M-loop includes the non-TP component it is associated with and at least one IMTP component. An M-loop may include IMTP components and the other non-TP components, but not the VMTP compo- 36 nents. This concludes that a VMTP component is included only in the T—loop it is associated with, but never in any other T-loops, nor M-loops. By Rule 1(b), a VMTP component is assigned to the co-tree. Therefore, the remain- ing components in a T-loop associated with this VMTP component are assigned to the tree. On the other hand, the non-TP component associated with an M-loop is assigned to the co- tree, and the remaining components in the M-loop are assigned to the tree. The following rule results. Rule; (a) In a T-loop, its associated VMTP component is assigned to the co-tree, and the remaining ones are assigned to the tree. (b) In a M-loop, its associated non-IMTP component is assigned to the co- tree, and the remaining ones are assigned to the tree. A graph has (Nd-1) tree edges, where Nd is the number of nodes in the graph. Excluding the INITP components which, by Rule 1(a), are assigned to the tree, the graph has only (N d—l-ml) tree edges available. Suppose that a T-loop includes Nt non-TP compo- nents, by Rule 2(a), the NI non-TP components are assigned to the tree. This implies that the number of non-TP components in a candidate T-loop cannot exceed (Nd-l-mI). Simi- larly, the number of non-TP components in a candidate M-loop, excluding the non-TP com- ponents which the M-loop is associated with, also cannot exceed (N d-l-ml). Rule}. The number of non-TP components in a candidate T- or M-loop cannot exceed (Nd- 1 -m1). 37 The L21 matrix can be represented in terms of test points and components as fol- lows, Ly Matrrx - -P-'I;1PT2:PT,12- - - PC]...PCnl iii; 53 31:: 3; W TPIml i_Q___Q__.,.___Q__E %///% (34) Tpv, I ’6"".’..’"6l 'I'Pv2 // 0 0: l : TPvmV . i-Q.....-_.".'__.O. where TPVl, TPVZ, ..., and TPva are the VM-test points, TPIl, TPIZ, ..., and TPImI are the IM-test points, PT], PTZ, .., and PTnz are the tree-components, and PC], PC2, .., and PC,“ are the co-tree components. Let wae a T-loop set which is defined as TLS = {(T 1,T2, ...,va) l Ti is a candidate T-loop associated with TPVi} (3-2) A candidate T-loop Ti constitutes the i-th row of the matrix 13;. A candidate T-loop set is the TLS whose corresponding E2 matrix has a non-zero global column-rank. In addition, by Rule 3, the total number of non-TP components included in a candidate T-loop set must not exceed (Nd-l-ml). Rubi. A candidate T-loop set must satisfy (a) The total number of non-TP components is (N d-mI-l), and (b) The global column-rank of E2 is r2 2 1. By definition, an IMTP component contributes to a column vector of E2. If an IMTP component is not included in a T—loop set, a zero column results in F4 and violates Rule 4(b). Since all the (Nd-mI-1)non-TP components and m1 IMTP components, i.e., PTl, PTZ, 38 .., and PT “2, included in a candidate T—loop set are assigned to the tree, the remaining com- ponents in the circuit, i.e., PCI, PC2, and PT“, are assigned to the co-tree. Therefore, an M-loop set, MLS, is defined as M15 = {(M1,M2, ...,Mnl) I Mj is a candidate M-loop associated with PCj} (3-3) A candidate M-loop Mj constitutes the j-th column of the matrix E1 corresponding to PCj. A candidate M-loop set associated with a candidate TLS is the MLS whose corresponding E1 matrix has a non-zero global column-rank. Similar to Rule 4, the following rule results 31119;. A candidate M-loop set must satisfy (a) The total number of non-TP components in (TLS,MLS) is (Nd-mI-l), and (b) The global column-rank of E1 is r1 2 1. Based on Rules 4 and 5, we derive pairs of (TLSMLS) with nonzero ranks r, and r2. By Lemma 3-1, the global column-rank r=min{r1,r2}, the pair (T LSMLS) with the maxi- mum rank r is then chosen for constructing the connection matrix which achieves the max- imum diagnosability. The component assignment procedure is summarized in Algorithm 3- 1. The following example illustrates the stepwise procedure of this algorithm and the detailed implementation. Consider the circuit of Fig. 34 (b), where n=1 1, m=4, m1=mv=2, Nd=6, Nd-mI-l=3, n1=5, and n2=6. The VM—test points are V45 and V13, the IM-test points are [C] and IRl, and the non-TP components include QBE, QCE, RL, RC, C2, R2, R3, RE, and CE. In Step 1, both IMTP components C1 and R1 are assigned to the tree. In Step 2, both T- and M- 39 loops are generated using following symmetric matrix, referred to as the adjacency matrix, which describes the relationship between any two nodes, where "1" means connection and "0" means no connection. Node —» 0 1 2 3 4 5 Index 0 0 1 1 0 1 1 \‘ 1 1 0 1 0 1 o 2 1 1 0 1 0 0 3 0 0 1 0 1 1 4 1 1 0 1 0 0 5 1 0 0 1 0 o For V45, we generate a number of loops starting from node 4 to node 5. A path is invalid if a node is re-visited. This implementation chooses the next node to visit in an ascending order of the assigned node number, for simplicity. Thus, we start with node 4 which connects to nodes 0, 1, and 3. We first select node 0 which connects to nodes 1, 2, 4, and 5, where node 4 has been visited, and only nodes 1, 2, and 5 are valid. Consequently, we select the next valid nodes in the sequence of nodes 2, 3, and 5. Therefore, a path 4-0- 1-2-3-5 connects node 4 to node 5, and the path with the VMTP component for V45 form a T-loop for V45. From Fig. 3-2, the path includes the following components: both edges for RE and CE in "4—0", R2 and C1 in "04", R1 in "1-2", RC in 2-3, and C2 in "3-5". Sim- ilarly, all T-loops for V45 can be generated as follows, 4-0-1-2-3—5 {RE,CE},{R2,C1},R1,RC,C2 4-1-2-0-5 QBE,R1,R3,RL 4-0-2-3-5 {RE,CE},RB, CC2 4-1-2-3-5 QBE,R1,RC,C2 4-0-5 {RE,CE},RL 4-3-2-0-5 QCE,RC,R3,RL 4-1-0-2-3-5 QBE,{C1,R2},R3,RC,C2 4-3 -2-1-0-5 QCE,RC,R1,{C1,R2},RL 4-1-0-5 QBE,{C1,R2},RL 4-3-5 QCE,C2 By Rule 2, the non-TP components must be less than or equal to 3. Thus, all candidate T- Algorithm 34. Component Assignment for Diagnosab .! iv . 1 .1. Lu Step 1 l'_ o i . t 2 t ..- uim .2; i i.- ‘5... A...‘ , .r i ' Assign the VMTP and IMTP components by Rule 1. Generate all candidate T-loops and M-loops by Rule 2, and assign the components by Rule 3. (Generate matrices E1 and By) 3.1 Select a candidate T-loop Ti for each TPVi to construct a T—loop set TLS as in (3-2). IF end-of-selection, GOTO Step 4 3.2 IF the TLS does not satisfy Rule 4, GOTO Step 3.1 3.3 Select a candidate M-loop M3 for each PCj to construct a M-loop set MLS as in (3-3). IF end-of-selection, GOTO Step 3.1 3.4 IF the MLS does not satisfy Rule 5, GOTO Step 3.3 3.5 The component assignment is recorded as well as r1 and r2. (Maximum Diagnosability) 4.1 Find the maximum t, where t=min{r1,r2}, for each candidate com- ponent assignments. (The component assignment generates a connection matrix which achieves t-diagnosability.) 41 loops for V45 are listed below. l. RE,C1,R1,RC,C2 5 QBE,C1,RL 9 QCE, RC, R1, Cl, 2. CE,Cl,Rl,RC,C2 6 QBE,R2,RL 10 QCE, C2 3 RE,RL 7 QBE, R1, R3, RL 4 CE,RL 8 QBE. R1, RC, C2 A candidate T-loop set is selected from TLS, in (34), and must satisfy Rule 4. In order to reduce the complexity of searching process, the T-loops, as shown in Table 3-2, are sorted in an ascending order for the numbers of non-TP components. Similarly, the sorted T-loops for V13 and the sorted candidate M-loops for all non-TP components are also listed in Table 3-2. In Step 3.1, the first T-loop, (RE,RL), in V45, and the first one, (R1,RC), in V13, are selected. Since the IMTP-component C1 is not included in either T-loop, a zero column occurs in E2 and violates Rule 4(b). Thus, the pair cannot be a candidate T-loop set. The procedure is repeated. The first candidate T-loop set is obtained by selecting the fourth T- loop, (QBE,C1,RL), of V45, and the first T-loop, (R1,RC), of V13. It generates the follow- ing E2 matrix QBE C1 RL R1 RC V45 1 1 1 0 0 V13 0 O 0 1 1 which satisfies Rule 4 with r2=1. Similarly, we also obtain two other candidate T-loop sets: the eighth T-loop, (QCE,RC,R1,C1,RL), of V45, and the first T-loop, (R1,RC), of V13; and the tenth T-loop, (CE,C1,Rl,RC,C2), of V45, and the first T-loop, (R1,RC), of V13. Both also satisfy Rule 4 with r2=1. 42 Table 3-2- W- 1. RE,RL 5 QBE,R2,RL 9 RE,C1,R1,RC,C2 V45 2. CE,RL 6 QBE,R1,R3,RL 10 CE,C1,R1,RC,C2 3 QCE,C2 7 QBE,R1,RC,C2 4 QBE,C1,RL 8 QCE,RC,R1,C1,RL 1. R1,RC 6 R2,RE.QCE 11 R1.R3.RE.QCE 2. QBE,QCE 7 C1,CE,QCE 12 R1,R3,CE,QCE VB 3 C1,R3,RC 8 R2,CE,QCE 13 R1,R3,RL,C2 4 R2,R3,RC 9 C1,RL,C2 5 C1,RE.QCE 10 R2,RL,C2 1. C1,RE 4 R1,R3,CE 7 C1,R3,RC,QCE QBE 2. C1,CE 5 R1,RC,QCE 3 R1,R3,RE 6 C1,RL,C2,QCE QCE 1. RC,R1,QBE 4. RC,R1,R2,CE 7. RC,R3,C1,QBE 2. RC,R1,C1,CE 5. RC,R1,R2,RE 3. RC,Rl,Cl,RE 6. C2,RL,C1,QBE m, 1. C1,R1,RC,C2 2. R2,R1,Rc,c2 3. C1,QBE,QCE,C2 1. R1,QBE,QCE 5. R3,C1,RE,QCE 9. C1,R3,QBE,QCE RC 2. R1,C1,RE,QCE 6. R1,C2,RE,QCE 10. R1,R2,RE,QCE 3. R1,C1,CE,QCE 7. R1,R2,CE,QCE 4. R1,C1,RL,C2 8. R1,R2,RL,C2 C2 1. RC,R1,C1,RL 2. RC,R1,R2,RL 3. QCE,QBE,C1,RL 1. C1 3. CE,QCE,RC,R1 5. RL,C2,RC,R1 R2 2. R3,Rl 4. RE,QCE,RC,R1 1. C1,Rl 3. CE,QBE,R1 5. C1,QBE,QCE,RC R3 2. R2,R1 4. RE,QBE,R1 RE 1. C1,QBE 3. C1,R1,RC,QCE 4. R2,R1,RC,QCE CB 2. R3,R1,QBE 43 Consider the first candidate T-loop set, where the IMTP components, R1 and Cl, and the non-TP components, QBE, RL, and RC, are assigned to the tree. Since the total number of tree components is 5, the remaining components, C2, RE, CE, R2, R3, and QCE, must be assigned to the co-tree. In Step 3.3, the M-loop sets associated with the candidate T-loop set are formed by the M-loops for the non-TP components C2, R2, R3, QCE, RE, and CE. Note that the non-TP components in an M-loop are assigned to the tree. Since the candidate T-loop set has already contained all 5 tree—components, a candidate M-loop must be the one that includes only the tree components. More specifically, consider the M-loops of C2 in Table 3-2, where it has 3 possible M-loops. The second M-loop, (RC,R1,RZ,RL), cannot be chosen because it contains a co-tree component R2. Similarly, the 3rd M-loop is also rejected because it contains a co-tree component QCE. For the first M-loop, (RC, C1,R1,RL), it contains only the tree components and is then chosen. Similarly, the first M- loops of all other co-tree components, RE, CE, R2, R3, and QCE, are selected, and the cor- responding matrix E1 is, C2 RE CE R2 R3 QCE ICl l 1 1 1 l 0 [RI 1 0 O O l l which satisfies Rule 5 with r1=1. Thus, the component assignment, C1, R1, QBE, RL, and RC in the tree, and C2, RE, CE, R2, R3, and QCE in the co-tree, generates the partition in Fig. 3-4 and Connection matrix Y in Fig. 3-1(c) which has l-diagnosability. IM-Test Points [:1 VM-Test Points Fig. 3-4. Graph Representation: (a) Components and Test Points; (b) T-ioop for V45; and (c) M-loop for C2. 45 For the second candidate T—loop set, it contains the tree-components, QCE, RC, C l , R1, and RL, and the corresponding El matrix has r2=l. Similarly, an associated candidate M-loop set is constructed by selecting the first M-loops of C2, R3, and R2, the third M- loops of RE and CE, and the fifth M-loop of QBE, and the corresponding E1 matrix has r1=l. Finally, for the third candidate T-loop set containing the tree-components, CE, C1, R1, RC, and C2, the corresponding E2 matrix has r2=1. However, since each M-loop in RE contains at least one co-tree component, a zero column vector occurs in E2 at the column corresponding to RE, and thus no candidate M-loop sets exist. Therefore, only two different component assignments are concluded. In Step 4.1, both achieve the same 1-diagnosability. 3.3 Discussion Given a circuit topology and test points, Algorithm 34 selects a connection matrix whcih achieves the maximum diagnosability that the circuit can achieve. The algorithm has been implemented to the system ADTS as a “Diagnosability Analysis” process. The algorithm also identifies the components having poor diagnosability from the connection matrix. To enhance the circuit diagnosability, the portions having poor diagnosability may be redesigned using the redesignability analysis discussed in the next chapter. 46 Chapter 4 REDESIGNABILITY ANALYSIS The redesign problem can be formulated as follows: assume that the schematic cir- cuit diagram is given, but some parts of the circuit are unknown or missing, the circuit is re-designable if the input/output (I/O) relation of each missing part can be traced, and the derived I/O relations can then be implemented. Note that we do not intend to discover the exact circuit schematic and components that were present in the circuit originally imple- mented [32,53]. Rather, the functions originally intended to be present will be identical. Thus, many possible implementations exist to recover their I/O relations. Based on our system model, CCM, with the known test input signals a and system responses y and the characteristics of the components in the Tester Group, as in (243), the I/O relations of the components in the Testee Group can be derived and evaluated. That is, the I/O relation Z2 can be derived as long as 52 and a2 exist. The redesign problem can be stated in a similar way, as illustrated in Fig. 44 , where the I/O relation of each Missing Part is derived using the characteristics of the Known Parts together with the applied input sig- nals and the measured responses. Thus, both fault diagnosis problem and redesign problem Share some similarities. Based on the system model and fault diagnosis algorithm, the Miss- ing Parts of the redesign problem in Fig. 4-1 are equivalent to the components in the Testee Group as in Fig. 24, while the Known Parts are equivalent to those in the Tester Group. 47 [:1 Known Parts — Missing Parts Fig. 4-1 Redesign problem. I Missing component Fig. 4-2 Example circuit with four missing components. 48 14*.1111 Therefore, the process of deriving the I/O relations for the components in the Testee Group can be applied to derive the I/O relations for the Missing Parts in the redesign problem. Our proposed redesign process is comprised of two steps: (1) redesignability check: and (2) redesign solution. Based on a set of rules derived from circuit topology, the former step checks whether a given circuit is redesignable with respect to a set of Missing Parts, given some test points. In this step, neither circuit simulations nor test vector applications are needed. Once the circuit is found to be redesignable, the I/O relations of the Missing Parts are derived to recover the Missing Parts. This aim is to develop an algorithm that ef- ficiently determines whether the circuit is redesignable. In the next section, rules for redesignability check are discussed. Section 4.2 pre- sents the development of the proposed redesign process. Finally, discussion is given in Sec- tion 4.3. 4.1 Unredesignabilitleedesignability Given a target circuit with the selected test points, one can derive the connection matrices Lu and L12, in (2-1), from the circuit topology, and L21 and L22 from the test points. Suppose that the circuit consists of 11 components and m test points, the Ln matrix is an m-by-n matrix. Suppose also that there exist q missing components in that circuit, a matrix, referred to as MP-matrix, is formed by those columns in 1,21 which are corresponding to these q missing components. Therefore, the following lemma results. Lgmmafii. A target circuit is redesignable if the corresponding MP-matrix has a full global column-rank. 49 ELQQL; A full global column-rank MP-matrix is left invertible. Thus, the I/O relation of each missing component can be derived as Shown in (240a). This concludes that the circuit is redesignable. Examulfl. Consider the example circuit and test points in Fig. 3-1(b). Suppose that Cl, RC, CE, and R3 are four missing components, as the shaded blocks indicated in Fig. 4-2. The following MP-matrix is extracted from the columns 1,4,8 and 11 of the [.21 matrix in Fig. 3-3(a)9 0 0 l I 0 0 O -1 -1 0 O O 0 -1 O 0 and it has a full global column-rank. By Lemma 4-1, the circuit is redesignable. By definition, a circuit is t-diagnosable if, given the results of all allowable tests, one can uniquely identify all faulty components provided that the number of faulty components does not exceed t [54,55]. The following theorem results. W. A t-diagnosable circuit is definitely redesignable if the number of missing components in the target circuit is less than t. M If the circuit contains less than t missing components, then the corresponding MP- matrix is contained in a 1.le matrix which has a full global column-rank because the circuit is t-diagnosable. Thus, the MP-matrix also has a full global column-rank. By Lemma 4-1, the circuit is redesignable. 50 The circuit in Fig. 4-2 has been Shown as l-diagnosable [39] if partitioned properly. By Theorem 44, the circuit with any single missing component is definitely redesignable. The t-diagnosability in Theorem 44 ensures the circuit redesignability if the circuit has at most t missing components. However, a t-diagnosable circuit may still be redesignable even when it has more than t missing components. W. Consider the same circuit with the same connection matrix in Example 1, except changing the missing components as RC, QBE, C2 and RL, as Shown in Fig. 4-3(a). The MP-matrix, 0 O 0 1 0 0 0 -1 0 -1 4 0 -1 0 0 0 does not have a full global column-rank. However, with an alternative connection matrix shown in Fig. 4-3(b), the MP-matrix corresponding to the missing components, RC, C2, RL,andQBEis 0 0 1 1 0 0 -1 0 4 4 0 0 -1 O 0 0 and it has a full global column-rank. Thus, the circuit is redesignable. Example 2 shows that the corresponding MP-matrices for different connection 1 matrices may be different. The MP-matrix for one connection matrix may not be full global column-rank, but it may be full global column-rank for other connection matrices. There- 51 Frail." m V .1 [V _00000004000 0000— _00000011111 0010— + _ _ 1C2 m .mmwmmmmmmm 3 ”U _l. 0 R 5 , 0 1 14110000000 1400 VC1 1000000 1400— 4 1000000 1000 l O 0 11.100000000011400 1.000000000011000 00001000410040 m 0000000400 0040 (b) 2 3 E RE c1 0 (C) Fig4-3. Example circuit: (a) with missing components; 1 0000001101. 00.11. 0 O 0 00000000404 0044 0 0 00000444 0010 4 4 _ E mmm 53— 11C 11 l _mmmmmwmmvwwmmwy ; and (c) a graph. 52 (b) a connection matrix fore, a circuit is redesignable if there exists at least one connection matrix in which the cor- responding MP-matrix has a full global column-rank. Otherwise, the circuit is unredesignable. W. A circuit is unredesignable if there exist no full global column-rank MP matrices for all possible connection matrices. If a circuit has more than 111 missing components, where m is the number of test points, then we will never be able to find a full global column-rank MP-matrix. Thus, the following theorem results. W. A circuit is unredesignable if the number of missing components exceeds m. It is impractical to check the rank of the corresponding MP-matrices of all possible connection matrices of a target circuit. An efficient algorithm is developed to find a connection matrix whose corresponding MP-matrix has a full global column-rank from circuit topology, which will be presented in the next section. 4.2 Redesignability Analysis: Component Assignment Algorithm Consider a target circuit‘that has 11 components, In test points, and q missing com- ponents. Let m1 and my be the numbers of IM- and VM-test points, respectively, where m1+mv=m. Fig. 4-4 illustrates a graph that describes the example circuit in Fig. 4-3(a), where both test points and missing components are indicated. Similar to the partitioned 1121 53 Missing Components [:1 Test Points Fig. 4-4 A graph for the circuit in Fig. 4-3(a) with test points and missing components. 54 matrix in (3- l ), the MP-matrix can be partitioned as follows, MP-Matrix MC, MCZ Mqu MCQVH MC TPI. 0 O 0 V/fl/ TPIELI 0 0 0 é///% Cl / m, 7 ///// ° ° TFV2 X 0 0 +1me W 0 0 where TPVl, TPV2, ..., and TPva are the VM-test points, TPIl, TPIZ, ..., and TPImI are the IM-test points, and MC1,..,Mqu, MCq\,+1,..,l\'ICq are the missing components. Con- structing linearly independent columns in a MP-matrix is equivalent to constructing lin- early independent columns in both matrices MX and MY. \VIthout loss of generality, we assume that the matrix MX includes qv’s missing components, and MY includes the remaining ones. Let a T-loop set, T”, be defined as (3-2), we define a candidate T-loop set as the TLS which constitutes a MX matrix with a global column-rank of qvi The necessary condition for MX to have a global column-rank of qv is my 2 qv. Also, the necessary con- dition for MY tohave a global column-rank of (q-qv) is m-mv Z q-qv. Thus, the number of missing components in a candidate T-loop set is ranged between mv and q-m+mv Rubi-J, A candidate T-loop set with qv’s missing components must satisfy (a) my 2 qv Z q-m+mv; (b) All candidate T-loops constitute MX with a global column-rank of qv. (c) Rule 4(a). 55 I Given a candidate TLS which includes the missing components MCi, i=1,2,..,qv, let a M-loop set, M L3, be defined as (3-2) and a candidate M-loop quj constitutes the j-th column of the matrix MY. Therefore, we define a candidate M-loop set associated with a candidate TLS as the MLS which constitutes 3 MY matrix with a global column-rank of (q- qv). Similar to Rule 44, the following rule results Rgle 4-2 A candidate M-loop set with (q—qv)’s missing components must satisfy (a) All candidate M-loops constitute MY with a global column-rank of (q-qv). (b) Rule 5(a). Consequently, a MP-matrix formed by a pair of a candidate TLS and its associated candidate MLS, (T LS’MLS)’ has a full global column-rank q. The component assignment procedure is summarized in Algorithm 4-1. The follow- ing example illustrates the stepwise procedure of Algorithm 4-1 and the detailed implemen- tation. Examplel. Consider the circuit of Fig. 4-3(a) which has 11 components. The VM-test points are V45 and V13, and the corresponding VMTP components are virtual components. The IM-test points are 1C1 and IR], and the IMTP components are C1 and R1. The missing components are RC, C2, RL, and QBE. In Step 1, q=m=4, and, by Step 2, both components C1 and R1 are assigned to the tree. In Step 3, both T- andM-loops are generated using sym- metric adjacent matrix described in section 3. 56 For V45, all T—loops can be generated as follows, 4-0-1-2-3-5 {RE,CE},{R2,C1],R1,RC,C2 4-1-2-0-5 QBE,R1,R3,RL 4-0- 2 — 3 - 5 {RE,CE},R3,RC C2 4-1- 2- 3 - 5 QBE,R1,RC,C2 4-0-5 {RE,CE},RL 4-3-2-0-5 QCE,RC,R3,RL 4-1-0- 2 - 3 - 5 QBE,{C1,R2},R3,RC,C2 4- 3 - 2 -1- 0- 5 QCE,RC,R1,{C1.R2},RL 4-1-0-5 QBE,[C1,R2},RL 4-3-5 QCE,C2 In Fig. 4-4, the number of non-IMTP components is Nd-mv=6-2=4, where the IMTP com- ponents are C1 and R1. By Rule 2, all candidate T-loops for V45 are listed below. 1. RE,C1,R1,RC,C2 5 QBE,C1,RL 9 QCE, RC, R1, Cl, RL 2. CE,C1,R1,RC,C2 6 QBE,R2,RL 10 QCE, C2 3 RE,RL 7 QBE, R1, R3, RL 4 CE,RL 8 OBE, R1. RC. C2 According to Step 4.1, a candidate T-loop set is selected from TLS in (44) which satisfies Rule 4-1, where the total non-IMTP components in the candidate T-loop set cannot exceed (Nd-mvl). Therefore, we sort the above table so that the number of non-IMTP components is in an ascending order. In this arrangement, we may have a better chance to derive a candidate T-loop set which meets Rule 44(b). 1. RE,RL 4 QBE,C1,RL 7 QBE, R1, RC, C2 V45 2. CE,RL 5 QBE,R2,RL 8 RE,C1,R1,RC,C2 3 QCE, C2 6 QBE, R1, R3, RL 9 CE,C1,R1,RC,C2 Similarly, the sorted T-loops for V13 and M-loops for QBE, RL, RC, and C2 are listed as follows. 57 1. R1,RC 4 C1,RE.QCE 7 R1,R3,RE.QCE V13 2. QBE,QCE 5 C1,CE.QCE 8 R 1 ,R3,CE,QCE 3 C1,R3,Rc 6 C1,RL,C2 9 R1 ,R3,R:,C2 l. C1,RE 4 R1,R3,CE 7 C1,R3,RC.QCE QBE 2. C 1 ,CE 5 R1,RC,QCE 3 R1,R3,RE 6 C1,RL,C2,QCE RL 1 C1,R1,RC,C2 2. R2,R1,RC,C2 3. C1,QBE.QCE.C2 1. R1,QBE,QCE 4. R1,C1,RL,C2 7. R1,R2,CE,QCE RC 2. R1,C1,RE,QCE 5. R3,C l ,RE,QCE 8. R1,R2,RL,C2 3. R1,C1,CE,QCE 6. R1,C2,RE,QCE C2 1. RC,R1,C1,RL 2. RC,R1,R2,RL 3. QCE,QBE,C1,RL In Step 4.1, we choose the first T-loop, {RE,RL}, for V45, as shown in Fig. 4-5(a), and the first T-loop, {R1,RC}, for V13, as shown in Fig. 4-5(b), to form a candidate T-loop set which satisfies Rule 44. The matrix MX has a global colurrm-rank of 2, where the matrix is R V45 0 V13 1 C RL 1 0 The uncovered missing components are C2 and QBE. In Step 4.3, the first M-loops for both C2 and QBE, as shown in Fig. 4-5(c) and Fig. 4-5(d), are chosen to form a candidate M- loop set which satisfies Rule 4-2. The matrix MY is C2 QBE IR1 1 0 [Cl 1 1 This concludes that the components {R1,C1,RE,RL,RC} are assigned to the tree and the remaining ones to the co-tree, as shown in Fig. 4-5(e). In fact, the component assignment for the graph in Fig. 4-5(e) is derived by taking the 8-th T-loop for V45, the first T-loop for V13, the first M-loop for QBE, and the first M- loop of RL. Thus, RE, Cl, R1, RC, and C2 are assigned to the tree and the remaining ones are to the co-tree. Algorithm 44 has been implemented to the test system, ADTS, as a 58 Missing Components 1:3 Test Points (6) Figu. 4-5. Component Assignment Procedure: (a) A T-loop for V45; (b) A T-loop for V13; (0) A M-loop for CZ; (d) A M-Ioop for QBE; and (9) Component Assignment. 59 ~ "1 3:3 5:35;.“ mamfifig' "3'_§1&5£mm~ run-rerun F ' Algorithm 44. Component Assignment for Redesignability Analysis Step 0. Let n, m, and q be the number of components, test points, and missing components. 1. IFq > m, GOTO Step 5 2. Assign the VMTP and IMTP components by Rule 1. 3. Generate all candidate T-loops and M-loops by Rule 2, and assign the components by Rule 3. 4. (Generate matrices MX and MY) 4.1 Select a candidate T—loop Ti for each TPVi to construct a candi- date T-loop set TLS. IF end-of-selection, GOTO Step 4-5 4.2 IF the TLS does not satisfy Rule 44, GOT 0 Step 4.1 4.3 Select a candidate M-loop M3 for each MCj to construct a candi- date M-loop set MLS. IF end-of-selection, GOT 0 Step 4.1 4.4 IF the MLS does not satisfy Rule 4-2, GOTO Step 4.3 4.5 The component assignment is done, and the circuit is redesign- able. ' EXIT 5. The circuit is unredesignable. {51' if" “Redesignability Analysis ” process. It should be mentioned that, with exhaustive search of the possible component assignments, we have identified 5 different assignments for the example circuit in Fig. 4—4. 4.3 Discussion This chapter presents the redesignability analysis process for analog circuits. One of the most difficult aspects of redesign is the recognition of the functionality of existing implementation. The developed redesign process is comprised of two steps: (a) redesigna- bility check; and (b) redesign solution. Based on circuit topology, a set of rules is developed to assign the edges in a graph to either tree or co-tree so that the associated MP-matrix with generated L-matrix is left invertible. Consequently, the I/O relations of the missing compo- nents can be reconstructed from the corresponding pseudo circuits. If a valid component assignment exists by Algorithm 4-1, the target circuit is redesignable. Otherwise, it is unre- designable with respect to the missing components. Note that the circuit may be possibly modified to become redesignable by decreasing the number of missing components. (we assume that the number of test points is fixed during the redesign process.) This can be achieved by combining some missing components as a bigger component, as shown in Fig. 4-6, referred to as missing circuit augmentation [56]. A combined missing component may include a number of missing components and/or known components. As the number of missing components is decreased, the number of test points may also decrease if IMTP- or VMTP component(s) are included by combined missing components. Once circuit is found redesignable, the I/O relations of missing components can be derived by (2-10): the redesignable configuration is used to construct the L-matrix in (2-7) 61 Fig. 4-6. Missing Component Compaction examples. 62 R3 first. Since the corresponding MP-matrix is left-invertible, by the K-matrix for the pseudo circuit in (2-11), we can find aiz and biz of the i-th missing component to construct its I/O relation, where both aiz and biz are functions of the system input vector u, the system response vector y and characteristic functions of the known parts. In fact, the I/O relation of the i-th component can also be derived using Sspice, a symbolic version of Spice [57.58]. With appropriate selection of input Signal vectors u and the generated system response vec- tor y, the missing components can be constructed from the I/O relations. As mentioned, the component assignment for a given graph (or circuit) is not unique. Which component assignment may provide the lowest cost for redesign is very important for further exploration. In addition, the complexity of the symbolically repre- sented I/O relations [58] is an important issue. Selecting appropriate input vector u is also essential for generating redesign solution(s) [56]. 63 Chapter 5 TEST POINTS SELECTION This chapter presents an efficient test points selection (T PS) process for easily test- able analog circuit design. The selections of both VMTPs and IMTPS are discussed. The selection of VMTPs can be formulated as to find a minimum set of fundamental loops that cover all nodes in the circuit graph, while the selection of IMTPS is to find a minimum number of cut-sets that cover all co-tree edges in the graph. Section 5.1 describes the prob- lem statement of the test points selection. Section 5.2 presents the development of TPS algorithm which finds the minimum number of test points and identifies their locations from circuit topology. Section 5.3 introduces a heuristic algorithm to Speed up the selec- tion process for larger circuits. Finally, summary and concluding remarks are given in Section 5.4. 5.1 TPS Problem Statement According to Rule 1 ~ Rule 3 in Chapter 3, the edges included in the fundamental loops associated with the selected VMTPS are assigned to tree edges, and the remaining co- tree edges must be included in the cut-sets associated with the selected IMTPS [31]. In other words, given a tree, the test points must be selected in such a way that the fundamental loops associated with the given VMTPS cover all tree edges, and the cut-sets associated with the selected IMTPS cover all co-tree edges. Therefore, the TPS problem for VMTPS, referred to as TPS_V problem, can be stated as follows, "to find a minimum number of fimdamental loops that cover all tree edges" Similarly, the TPS problem for IMTPS, referred to as TPS_I problem, is Stated below, TPS_I Problem: "to find a minimum number of cut-sets that cover all co-tree edges" Unfortunately, the number of possible trees in a graph is Nde'2 for circuit graph with the number of nodes Nd Z 3 [59]. Thus, exhaustively searching for all possible trees for test points selection problem is impractical particularly for large Nd. For each VMTP, there exists a unique fundamental loop associated with it. The fun- damental loop includes at least two nodes, i.e, the terminal nodes of the VMTP component. Since a fundamental loop visits the nodes it includes only once, the loop across these two terminal nodes is a valid path. Therefore, the TPS_V problem can be re-stated as follows, TPS_V Problem: "to find a minimum number of valid paths that construct a tree and cover all nodes in a graph" It should be mentioned that (1) any node in a valid path cannot be visited twice or more. However, one node can be visited by two different valid paths as long as no close loops are formed; (2) the valid paths define a tree in the given circuit graph. (3) the selected VMTPs construct the E2 matrix in Table 3-2 and must satisfy r2 2 1. Therefore, the TPS_I problem then selects a minimum number of cut-sets that covers all co-tree edges. The tree edges associated with the selected cut-sets are selected as the IMTPS which construct the 65 E1 matrix satisfying r1 2 1. For an example circuit and given tree/co-tree partition shown in Fig. 54(a), Fig. 54(b) illustrates the two fundamental loops associated with V45 and V13. while Fig. 54(c) shows the cut-sets associated with IC 1 and IR]. Since all circuit elements can be covered by either fundamental loops associated with VMTPS or cut-sets associated with IMTPS, this configuration is at least l-diagnosable. 5.2 Algorithm Development A Hamilton path is a valid path in a graph such that it contains all the nodes [60]. If there exists a Hamilton path in a graph, by the TPS_V problem, the circuit needs only one VMTP, which is across two terminals of the Hamilton path, to diagnose. A simple suffi- cient, but not necessary, condition for checking the existence of a Hamilton path in a graph can be found in [59]. In general, not all circuits contain the Hamilton paths.Thus, efficient algorithm are developed to resolve the TPS_V problem. To reduce the complexity of searching valid paths in a graph, the original graph G is simplified as G’, a simple graph, by merging the parallel edges and/or series edges as fol- lows, 8919.5;1. (a) if two or more edges are connected in parallel, they are merged as one in G’; and (b) if two or more edges are connected in series, they are merged as one in G’. Consider the graph G in Fig. 5-2(a), the parallel edges R2 and C1 in G are merged as the edge g1 in G’, as shown in Fig. 5-2(b). Similarly, the parallel edges RE and CE are merged as g6, while the series edges C2 and RL are merged as g7, where node "5" is elim- 66 Fundamental loop for V13 Fundamental loop for V45 Fig. 5-1. Example Circuit: (a) Tree in A circuit Graph; (b) Fundamental Loops; and (c) Cut-sets. Fig. 5-2. Example for Test Point Selection Process: (a) Circuit Graph; (b) Simplified Version; (0) Path Selection; (d) Selected F-loop(s); (e) Cut-set Selection; and (f) Test Point Locations. 67 inated. As a result, the number of edges and nodes in G are 11 and 6, and they are reduced to 8 and 5 in G’, respectively. The next step is to search for the possible valid paths from the adjancecy matrix of the graph, where the adjacency matrix of G’ is as follows: NOde —> 0 1 2 3 4 Index 0 0 1 1 l 1 \‘ 1 1 0 1 0 1 2 1 1 0 1 0 3 1 0 1 0 1 4 1 1 0 l 0 Consider the construction of all valid paths between node 1 to node 2. all valid paths between nodes 1 and 2 can be generated as follows, where the paths with "*" indicate the Hamilton paths: 1-02 1402 103-2 * 1-4.0-3-2 * 1-0-4—3-2 * 1430-2 12 143-2 Once the valid paths are constructed, a minimum set of valid paths that cover all nodes is selected, where the valid paths construct a tree in G’. The parallel and series edges in G are assigned based on the assignment in G’ and the following rule. 31119.22. (a) For parallel edges in G, if the corresponding edge in G’ is assigned to tree, we assign any one of the parallel edges to tree and the remaining ones to co-tree; if the corresponding edge in G’ is assigned to co-tree, we assign all parallel edges to co-tree. (b) For series edges in G, let the terminal nodes of the series edges be or and B, respectively, if the corresponding edge in G’ is assigned to tree, we 68 assign all series edges to tree, if the corresponding edge in G’ is assigned to co-tree, we assign the edge with Otto co-tree, and the remaining ones to tree, where Otis the terminal node of the valid path. Consider a simple G’ with a Hamilton path 1—4—0-3—2, as illustrated in Fig. 5-2(c), where the tree edges are g3, g6, g7, and g4, and the co-tree edges include g1, g2, g5, and g3. By Rule 5—2, the parallel edges C1 and R2 are assigned to co-tree, as shown in Fig. 5-2(d). Similarly, for tree edge g6, the parallel edges RE and CE are assigned to tree and co-tree edges, respectively. Finally, for the tree edge g7, the series edges RL and C2 are assigned to tree. This concludes that the circuit needs only one VMTP at the voltage across nodes 1 and 2, i.e., V12. In general, if there exist a minimum set of mv’s valid paths that include all nodes in G, then the circuit requires mv’s VMTPS. For the TPS_I problem, it is to find a minimum number of cut-sets that cover all co- tree edges. The problem can be formulated as a minimum covering problem. More specif- ically, consider a matrix D=(Dij)exk, where e=Nd4 and k=n-e. The selected VMTPs define the tree edges {PT1, PT 2,..,PT,,} and the remaining edges in the graph are co-tree edges, say, {PC1, PC2, .., PCk}. The j-th column of D is associated with PCi and describes the funda- mental loop associated with PCi. Similarly, the j-th row means the cut-set associated with PTj. Therefore, if the co-tree edge P13 is included in the fundamental loop associated with PCi, then Dji="x". Otherwise, Dji=" " (blank). For example, consider the tree in Fig. 5—2(d), where the tree edges are RC, C2, RL, RE, and QBE, and the co-tree edges include R1, R2, 69 R3, Cl , CE, QCE. Thus, the corresponding matrix D can be constructed as follows R1 R2 R3 Cl CE QCE RC x x C2 x x x RL x x x RE x x x x x QBE x x x For example, there exists a fundamental 100p associated with co-tree edge R1 including the tree edges RC, C2, RL, RE, and QBE. Thus, the x’s in the first column indicate the tree edges that are included in the fundamental loop associated with R1. Therefore, the TPS_I problem is to find the minimum number of rows that cover all co-tree edges R1, R2, R3, C1, CE, and QCE. In other words, the TPS_I problem is to find the minimum number of rows that cover all co-tree edges, i.e., all PCi’s. The minimum covering problem can be resolved using the prime implicants chart used in the Quine-McClusky method [60] for two-level logic minimization. In that chart, we first find the essential prime implicants, equivalent to essential cut-sets here. These are immediately apparent whenever there is a single "x" in any column. This means that there is a coatree edge which is covered by one and only one cut-set. For example, the column with respect to CE has a single "x", where the cut-set associated with the tree edge RE is the one and only one which covers CE. The essential cut-sets must participate in the final cover. A reduced prime implicant chart can be obtained by deleting the column and row associated with the essential cut-set. Since the essential cut-sets usually cover additional co-tree edges. Any columns that have an "x" in a row associated with an essential cut-set are also deleted. In case that there exist cyclic prime implicant tables, the Patrick’s method can be applied to find a set of minimum covers [60]. 70 An essential cut-set associated with RE was found in the above chart and it covers the co-tree edges R1, R2, C1, and QCE. Only one column R3 is remained and can be cov- ered by any one of the cut-sets associated with RC, C2, or RL. Fig. 5-2(e) shows the two cut-sets associated with RE and RC which cover all co-tree edges. Fig. 5-2(f) illustrates that the circuit can be diagnosable with a VMTP, V12, and two IMTPS, IRE and IRC. Based on this edge assignment, we obtain the following matrices E1 and E2: QBERE RL C2 RC R1 R3 QCECE R2 C1 IRC 0 0 0 0 0 l 1 0 0 O 0 IRE 0 0 0 0 0 0 0 1 1 1 1 VRl l 1 1 l l 0 0 0 0 0 0 It can be easily verified that both r1 and r2 are equal to 1. Algorithm 54 summarizes the above test point selection process. Consider the simple graph G’ with a Hamilton path 1-4-3-2-0, as shown in Fig. 5-3 (a). Since the edge g7 in G’ is assigned to co-tree and node 0 is a terminal node of the valid path, by Rule 5-2, RL is assigned to tree and C2 to co-tree, as shown in Fig. 5-3(b). As a result, the edge V15 is chosen as the only VMTP, and the tree edges include QBE, QCE, RC, R3, and RL, while R1, R2, RE, C1, C2, and CE are in co—tree. The corresponding D matrix can be generated as follows. R1R2REC1C2CE QBE x x x QCExxxx x 'RC xxxxxx R3 xxxxx RL x Obviously, the cut-set associated with RC covers all co-tree edges and can be illustrated in Fig. 5-3(c). Thus, the circuit is diagnosable with two test points: the VMTP V15 and the 71 Fig. 5-3. Example for TPS Process: (a) Circuit Graph G’ with Tree; (D) G with Tree and Cut-set; and (0) Test Point Locations. 72 IMTP IRC. Based on the edge assignment, we obtain the following matrices E1 and E2 1C2 CE QBE QCERC R3 RL IRC 0 0 0 0 0 1 1 1 1 1 R1 R2 RE 1 l VRl 0 0 C l l l l O O O 0 where both E1 and E2 have global column-rank of 1. 5.3 Improvement As presented in the previous section, a simple adjacency matrix was used to find the possible valid paths. Among the possible valid paths, a minimum set is chosen to cover all nodes in the graph and to determine the VMTPs. However, finding all possible valid paths from the adjacency matrix of a graph for a reasonably large circuit may have very high searching complexity. Therefore, this chapter presents a simple heuristic algorithm, as sum- marized in Algorithm 5-2, for finding a near minimum set of valid paths that covers all nodes in the graph. For simplicity of this discussion, a challenge graph given in Fig. 5-4(a) is used to illustrate the stepwise procedure, and its adjacency matrix is given in Fig. 5-4(b), where the degree of a node is the number of its adjacent nodes. The node degree can be computed by summing up the number of 1’s in the associated row. The developed algorithm finds a valid path at a time. For the first valid path, the node degrees are first computed and the node with the highest degree is selected as the ini- tial node. If more than one nodes with the highest degree exist, the node with the lower index has the higher priority to be selected. For simplicity, the node with highest priority is the one to be selected, NTBS node, for short. For example, the highest node degree in the adjacency matrix is 5, where nodes 8, 10, and 12 have the same highest node degree. Thus, 73 810 10 mm 5 1. 2 gobg g 2 1. l 1 7M 14 l .52 g ... a 5 can 685 ““1 1 gm ...... .1. m 8B 95 00 918 888 3 2 g 313 814 g6 g7 81 (a) Node 2345678910111213141516 1 Node Index m. 3333333535353333 000000000000 000000010001 1 0 0000000001010 0000000101000 110 001 001 001 0000011000100110 0000100001010000 0001000010101100 0010000101000000 0100001010001010 1000000100010000 1000100000010000 0001010000100000 0010100001000000 0101000010000000 1010000100000000 0100011000000000 123456789WUHBMHM (b) Fig. 5-4. Example: (a) Graph; and (b) Adjacency Matrix. 74 the NTBS node is the node 8. Let the initial node of the first valid path be denoted as node or, i.e., the valid path start with the node Ot. The next step is to find the NTBS node, B, of or. For example, node 8 has 5 adjacent nodes 2, 7, 9, l3, and 15 that have the same degree of 3. Thus, the NTBS node of a is node 2, i.e., 8:2. It should be noted that the degree of a node must be updated if its adjacent nodes have been visited. Once B is selected, the next step is to find its NTBS node. The same process is repeated until no more NTBS node exists. Let y be the node which does not have NTBS node, i.e., y is the terminal node of the valid path. The process generates the following valid path, as shown in Fig. 5-5(a), 8—>2—91—>6—>5—)4—)3—>9—>10—>1 1-—>12—>7 where 7:7. Once the terminal node is found, the valid path may be extended from the initial node a if its NTBS node exists. Let n be the NTBS node of or in the extended valid path. For example, at this moment, node 8 still have two adjacent nodes 13 and 15 which are not yet visited. Thus, node 13 is chosen as its NTBS node, i.e., 11:13. The next step is to find the NTBS node of 1], and the same process is repeated until no more NTBS node exists. Let p be the terminal node of the extended valid path. The extended path for the example is 8—>13-—>16—-)14 where p=14. In summary, the first valid path is constructed from or to y if no extension exists, and thus the VMTP is selected at V(Ot,y). On the other hand, if extended path exists, then the valid path starts from p to y and the VMTP is selected at V(p,y). In the above example, the path is from node 14 to 7, i.e., the VMTP is either V(7,14) or V(l4,7). Once the first valid path is constructed, the remaining valid paths are generated from the unvisited nodes. Note that 100ps are not allowed in a tree. In order to avoid forming 75 Cut-set for g3 Cut-set for g22 1 (a) VMTPS: V(7,14), V(8,15) (c) IMTP: g3 and g22 2 7 10 11 12 14 15 19 20 23 24 26 l x x x x x x x + 3 x x x x x x x x x x x 4 x x x x x x x x x x 5 x x x x x x x x x 6 x x x x x x x x 8 x x x x x x 9 x x x x x x x x x x 13 x x 16 x x x x x x x x x 17 x x x x x x 18 x x x x x 21 x x "P 22 x x x x 25 x x 27 x x x (b) Fig. 5-5. Example Graph: (a) Tree and Co-tree Edges; (b) Prime implicant Chart; and (c) Cut-sets for 93 and 922. 76 _. wearfi Ti— - “xfirgqr. . e. - “e; . _} Algorithm 5-1: Algorithm for Test Points Selections Step 1. Generate simple graph G’ using Rule 54. 2. (Select VMTPS) 2.1 Generate all valid paths 2.2 Select a candidate set of valid paths that cover all nodes in G’. 2.3 Assign edges in G using Rule 5-2. 3. (Select IMTPS) 3.1 Generate the prime implicant table or reduced table 3.2 Find essential cut-sets 3.3 Ifexist, GOTO Step 3.1; 3.4 Apply Patrick’s method if necessary. 3.5 m=m1+mv; IF m is not minimum, GOT 0 Step 2.2. 3.6 DONE. 77 loops, any nodes in a valid path cannot be revisited. However, a node may be visited by two different valid paths as long as no loops are formed. Therefore, the nodes included in the first valid path may be re-visited by the other valid paths. In this algorithm, a flag, FLAG(i), is used to define the status of the i-th node. More specifically, FLAG(i)=0 if the i-th node has not yet been visited, FLAG(i)=1 if the i-th node is visited by the current path, and FLAG(i)=2 if the i-th node is visited by the previous paths. The flags are initialized as 0’s before the first valid path is constructed. Once the first path is generated, FLAG(i) is set to a 2 if FLAG(i)=1 . When the second path is constructed, the candidate nodes for the NTBS node are those adjacent nodes with FLAG(i)=0 or 2. However, the ones with FLAG(i)=0 has higher priority to be chosen than those with FLAG(i)=2 so that more unvisited nodes can be covered. Once the i-th node is chosen as the NTBS node, the flag, FLAG(i)=0 or 2, will be set to a 1. The node with FLAG(i)=1 is always disqualified as the candidate NTBS node. Thus, no loops will be formed in this selection process. For the above example, after constructing the first valid path, there exists only one node which is unvisited, i.e., node 15. By Algorithm 5-2, its NTBS node is node 8 and no more unvisited nodes. The second valid path is from node 15 to node 8 and thus the second VMTP is V(8,15) or V(15,8). Since no unvisited node exists, the process terminated and a tree is constructed and shown in Fig. 5-5(a). Therefore, the tree and co-tree edges are listed as the indices shown in Fig. 5-5(b). Based on the row covering scheme in Algorithm 5-1, both rows 3 and 22 cover all co-tree edges. Therefore, the IMTPS are selected at g3 and g22. Fig. 5-5(c) illustrates the cut-sets for g3 and g22. This concludes that the circuit needs only four test points to make it easily testable. 78 [III */ Step Algorithm 5-2: Improved Algorithm for Test Points Selections Node(i): i-th node in the graph, i=1,2,..,n; Adj(x): the adjacent nodes of the node x; FLAG(i): the status of the i-th node; 0- unvisited; I- visited in current path; 2— visited in previous paths. V_path(v)[]: an array of nodes in the v-th valid path. NTBSO is a function for finding NTSB node. NTSB(0,vJ) - from all nodes with FLAG=O for v-th path; NTSB(1,v,j) - from the adjacent nodes of V_Path(v)[j] with FLAG=0; It returns the NTSB nodes, or a 0 if no NTSB exist. 1. v = 1; FLAG=0; p=#{i l FLAG(i)=0} 2. /* Construct the v-th valid path, first find the initial node */ 2.1 j=1; V_path(v)[l]=NTBS(0,v,j); FLAG(i)=1; p=p4; 2.2 k=NTBS(1,v,j); 2.3 If (k¢0) {i=j+l; v_path(v)[il=k; FLAG(k)=1; p=p-1; if (p20) GOT 0 Step 2.2;} 2.4 r—-j; 1* terminal node */ 3. /* Extended path *I 3.1 k=NTBS(1,v,1); 3.2 If (k¢0 & p20) {i=j+1; V_pam(v>01=k; FLAG rval:=1.0e3; PROCEDURAL FOR ac, dc, transient => irl:=[pos,neg].v/rval; pos.i%=irl; neg.i%=-irl; vrl:=[pos,neg].v; END RELATION; END ARCHITECTURE res; (a) ENTITY vcvs IS COUPLING(vx:analog); PIN (pos,neg:electrical); END ENTITY vcvs; ARCHITECTURE vx OF vcvs IS BEGIN RELATION PROCEDURAL FOR ac, dc, transient => [pos,neg].v%:=vx; END RELATION; END ARCHITECTURE vx; (b) Fig. 6—1. Controlled Source Models: (a3 Direct Control; and (b) Indirect Contro. 85 -- CCCS I-IDL-A MODEL ENTITY cccs IS COUPLING(vx,ix:analog); PIN (pos,neg:electrical); END ENTITY cccs; ARCHITECTURE icon OF cccs IS BEGIN RELATION PROCEDURAL FOR ac, dc, transient => pos.i%=ix; neg.i%=-ix; vx:=[pos,neg].v; END RELATION; END ARCHITECTURE icon; (a) -- VCVS I-IDL-A MODEL ENTITY vcvs IS COUPLING(vx,ix:analog); PIN (pos,neg:electrical); END ENTITY vcvs; ARCHITECTURE vcon OF vcvs IS BEGIN RELATION PROCEDURAL FOR ac, dc, transient => [pos,neg].v%:=vx; ix:=pos.i; END RELATION; END ARCHITECTURE vcon; (b) Fig. 6-2. Controlled Source Models: (a) Current Source; and (b) Voltage Source. 86 the pseudo circuits. By using controlled source, vendor provided component library can be applied directly without any modifications. 6.2 HDL-A Modeled Pseudo Circuits The connection matrix K in Eqn. (240) of a pseudo circuit is used to describe a test program for the component subdivision. A test program is generated by the following three steps: Step 1. Compute al and b1 from (240) and (2-83), or (2-9a); Step 2. Calculate both a} and 3,2 from (2-lOb) and from (2-8b) or (2—9b). Step 3. Compute 6,2 from (24%) and find the difference (Biz-15,2). Consider the connection matrix of the pseudo circuit in Fig. 3-1, with al=(a1 l,al2,al3,al4,a15,a16,a17)=(IR1 ,VC2,IQ1,VCE,VR3,VR2,VRE) and bl=(bl 1,bl2,b13,b14,b15,b16‘,b17)=(VR1,IC2,VQ1,ICE,IR3,IR2,IRE). Therefore, we have al l==y 1; a12=b4-b5+b6-b7+y2; a1 3=b6—y 1+y2; a14=b2~y3-y4; a15=~bl -b2+b3-u2+y3+y4; a16=b2-b3-y3-y4; a17=b2-y3-y4. The corresponding HDL-A description is given in Fig. 6-3(a), and its ENTITY is referred to as BI-block. Note that COUPLING allows the B l-block to use their values of III, yl, y2, y3 and y4, the input and test signals, obtained from the source description. The parameter in the COUPLING declaration, is either voltage source controlled by the voltage across, or current source controlled by the current flow through associated components. 87 -- HDLA MODELED PSEUDO CIRCUIT Bl-BLOCK -- FOR TESTEE GROUP COMPONENTS: C1, RC, Q2, RL ENTITY B1_BLOCK IS COUPLING (a11,a12,al3,a14,a15,a16, al7,yl,y2,y3,y4,u1,u2:analog); PIN (gnd:electrical); END ENTITY B1_BLOCK; ARCHITECTURE Pl OF Bl_BLOCK IS BEGIN RELATION PROCEDURE FOR DC, AC, TRANSIENT=> -- GET a1 FROM b1, u, y AND THEN COUPLING OUT a11:=+y1; --Rl a12:=+b4-b5+b6+b7+y2; --C2 a13:=+b6-yl+y2; --Q1 al4:=+b2-y3-y4; «CE a15:=-b1-b2+b3-u2+y3+y4; --R3 al6:=+b2-b3-y3-y4; --R2 al7:=+b2-y3-y4; --RE END RELATION; END ARCHITECTURE P1; (2!) -- HDLA MODELED PSEUDO CIRCUIT A2-BLOCK -- FOR TESTEE GROUP COMPONENTS: Cl, RC, Q2, RL ENTITY A2_BLOCK IS COUPLING (b11,b12,b13,b14,b15,b16,b17,a21, a22,a23,a24,y1,y2,y3,y4,ul,u2:analog); PIN (gnd:electrical); END ENTITY A2_BLOCK; ARCHITECTURE P2 OF A2_BLOCK IS BEGIN RELATION PROCEDURE FOR DC, AC, TRANSIENT=> - GET a2 FROM bl, u, y AND THEN COUPLING OUT a21:=+y2; --C1 a22:=-b5+yl ; «RC a23:=+b2+u2-y4; «Q2 a24:=+b2-u2-y3; --RL END RELATION; END ARCHITECTURE P2; 0)) 88 « HDLA MODELED PSEUDO CIRCUIT DIFF-BLOCK « FOR TESTEE GROUP COMPONENTS: C1, RC, Q2, RL ENTITY DIFF_BLOCK IS COUPLING (b11,b12,bl3,bl4,b15,b16,bl7,bb21 ,bb22,bb23,bb24,y1,y2,y3 ,y4,u l ,u2:analog); PIN (gnd:electrical); END ENTITY DIFF_BLOCK; ARCHITECTURE P3 OF DIFF_BLOCK IS BEGIN RELATION PROCEDURE FOR DC, AC, TRANSIENT=> « OUTPUT DIFFERENCE OF b2 & b"2 b21.diff%:=bb2l-(+b2-b3-ul-y3-y4); «C l b22.diff%:=bb22-(-b1-b2+b3-u2+y4); «RC b23.diff%:=bb23-(-b4—b6-b7+yl-y2); «Q2 b24.diff%:=bb24-(-b4+b5-b6-b7-y2); «RL END RELATION; END ARCHITECTURE P3; (C) Fig. 6-3. HDL-A Modeled Pseudo Circuit: (a) B1_block; (b) A2_block; and (c) DIFF_block. 89 Once the values of a1=(a1 1 ~ al7) in Bl-block are obtained, the HDL-A description for the components in the Tester Group will derive the values of b1=(bll ~ b17) which will be used in Step 2. Again, from the K-matrix, a2=(a21,a22,a23,a24)=(VC1,VRC,IQ2,VRL). where a21=y2; a22=b5-y1; a23=b2+u2-y4; and a24=b2-u2-y3. The corresponding HDL-A description is illustrated in Fig. 6-3(b), and its ENTITY is referred to as A2-block. Once the values of a2 are obtained, the HDL-A description of the components in the Testee Group will derive the values of'52=(bb1,bb2,bb3,bb4) which will be used in Step 3. The values of b2=(b21,b22,b23,b24) are first computed and then compared with E2. The differences can be expressed as follows, b21diff=bb21 -b21=bb21-(b2-b3-u 1-y3-y4); b22diff=bb22-b22=bb22-(-b1-b2+b3-u2+y4); b23diff=bb23-b23=bb23-(-b4—b6-b7+yl-y2); b24diff=bb24~b24=bb24—(-b4+b5—b6-b71-y2). Fig. 6-3(c) shows the HDL-A description of DIF F -block for Step 3. In summary, the HDL-A description of a pseudo circuit includes three ENTITY blocks, B l-block, A2-block, and DIFF-block. As illustrated in Fig. 6-3, the detailed structures of the three ENTITY blocks are described by the architectures p1, p2, and p3. 6.3 Test Program Generation Process In the test program generation process, the generated test programs should be verified and validated. A simulation-based verification process using HDL-A simulator, AccuSim, has been developed to check if the test programs are properly generated and to 90 verify whether the test programs are capable of identifying fault(s) effectively. After the generated test programs are completely verified, they will be validated by emulating the UUT with injected faults. With the measured test responses obtained from the faulty UUT through a virtual instrument, the test programs will be validated if they can properly identify fault(s). Fig. 64 illustrates the Simulation-based verification and validation process. A test program includes the compiled HDL-A codes for Bl-block, A2-block, and DIFF-block. The test program for the example circuit takes four input pins, ul, yl, y2,y3 and y4, and produces three output pins, b21diff, b22diff, b23diff, and b24diff. In this development, the test programs will receive the simulated test responses from the UUT or faulty UUT during the verification process, and they will takes measured test responses during the validation process. Thus, each test program require an interface, as Shown in Fig. 6-4, and its HDL-A code is described in Fig. 6-5(a). In the Mentor Graphics design system, where the I-IDL-A codes are compiled and executed, a circuit description can be either provided by the test system designer with a netlist, or imported from the schematic diagram generated by Design Architect. This implementation takes the latter approach. During the verification process, the responses measured at various test points in a UUT are modeled as controlled sources. Fig. 6—5(b) illustrates the HDL-A description of the test points. Their measured voltages/currents are obtained by "Coupling" the corresponding component measurements in the schematic diagram. For simplicity, all current measurements are converted to voltage measurements. For example, "ylpin.v%= iCl*1.0;" in Fig. 6-5(b), means that the voltage across the pin "ylpin" is defined as that across the lg-resistor connected in series with the current "iCl 91 Test Program Verification HDL-A Modeled U U T HDL-A Modeled Sources 11 Test Program Validation UUT Test Instrument 33 174 HDL-A Modeled Interface . 1 Bill-block .‘j A2-block > DIFF-block . . - , w— I g - V - '14-" . , 2:, .~.int§.tr-su; ., -. - T- I‘ if: "fl'fu/J :3 7.,‘ xi ‘ . . 43"! JR“: :2“ '_ . b21diff b22diff b23diff b24diff HDL-A Modeled Pseudo Circuit Fig. 6-4. HDL-A Modeled Test Program Process. 92 Virtual Instrument « Interface Description ENTITY interface IS COUPLING(u1,y1,y2.y3,y4:analog); PIN (ulpin,y1pin,y2pin, y3pin,y4pin,gnd:electrical); END ENTITY interface; ARCHITECTURE itrface OF interface IS BEGIN RELATION PROCEDURAL FOR ac, dc, transient => . ulpin:=[u1,gnd].v; ylpin:=[yl,gnd].v; y2pin:=[y2,gnd].v; y3pin:=[y3,gnd].v; y4pin:=[y4,gnd].v; END RELATION; END ARCHITECTURE itrface; (a) -- Source Description ENTITY sources IS COUPLING(iCl ,iRl ,le 3,vX45 :analog); PIN (y1pin,y2pin,y3pin,y4pin:electrical); END ENTITY sources; ARCHITECTURE uy OF sources IS BEGIN RELATION . PROCEDURAL FOR ac, dc, transient => « output y values to interface pins ylpin.v%=iCl*1.0; y2pin.v%=iRl * 1.0; y3pin.v%=le3; y3pin.v%=vX45; END RELATION; END ARCHITECTURE uy; (b) Fig. 6-5. HDL-A Descriptions: (a) for interface; and (b) for Sources. 93 6.4 Discussion HDL-A is an analog version of hardware description language which is suitable for the structural, behavioral descriptions and simulations of digital, analog, and mixed-signal electronic circuits and systems. It is able to support any design methodology and is tech- nology independent. This chapter presents the development of the ATPRG system, an au- tomatic test program generator using HDL-A model, for fault diagnosis of analog circuits. The components in the system model, CCM, can be analog discrete components, digital logic gates, integrated circuits, or subsystem. With the hardware description languages, VHDL for digital and HDL-A for analog, the developed ATPRG system can be applied for mixed-signal integrated circuits [30,33]. The generation core of ATPRG has been integrat- ed into the test system, ADTS, as a “HDL-A Test Program Generation” process. To keep pace with the ever increasing demands on higher productivity and shorter development cy- cles, Labview, a virtual test environment, as shown in Fig. 6—4, is used to derive quality- assured test program from high-level specifications [30]. The reliability and quality of the test program can be increased using simulation-based test program verification tools. 94 Chapter 7 CONCLUSION Mixed-signal ICs have become the main-stream solutions for the applications such as portable data systems, wireless communication, and multimedia. Due to the increasing complexity and circuit density, manufacturers confront the problem of long testing cycle by using the conventional external functional test performed on ATE (Automatic Tesr Equipment). AS a result, this not only reduces the testing confidence, but also increases the cost directly. Therefore, it is necessary to develop efficient test/diagnosis strategies that will not only help finding the causes of common failure mechanism, but may also help to resolve testing complexity problem by providing inforrnations of proper locations of test points. This thesis study presents the development of an automated diagnostic test system that includes several features such as diagnosability analysis, redesignability analysis, test points selections, and HDL-A test program generations. All these processes have been integrated as a complete test system, the Automated Diagnostic Test System. 7.1 Summary and Contributions The framework of the test system, as illustrated in Fig. 14, includes diagnosability analysis, redesignability analysis, and diagnosability design methodologies. Chapter 3 pre- sents the diagnosability analysis process. Given a circuit topology and test points, Algo- 95 rithm 3-1 assigns the components to tree/co-tree edges of the graph representing the circuit topology. Based on the all possible component assignments, candidate diagnosable config- urations are generated and the one with the maximum diagnosability is chosen. The config- urations having poor diagnosability are also identified. The diagnosability of the portion having poor diagnosability can be enhanced by redesigning the portion. An efficient redesign analysis process presented in Chapter 4 checks if the redesign is feasible. Two major steps were developed: (a) redesignability check; and (b) redesign solution. A set of component assignment rules, similar to those in diagnosability analysis, is applied to check if the associated MP-matrix is left invertible for deriving the I/O relationships of those components. If no such MP-matrices exist, the cir- cuit is not redesignable. Otherwise, the developed 110 relations are used to reconstruct the components. Several redesign methodologies are also discussed to speed up the process. In Chapter 5, the test points selection problem is formulated as a minimum covering problem on a circuit graph. The selection of VMTPs is the problem of finding a minimum set of valid paths that cover all nodes in the graph, while the selection of IMTPS is to find a minimum set of cut-sets that cover all co-tree edges. Two efficient algorithms were devel- oped to define the number of test points required and identify their locations. In Chapter 6, an automatic test program generator, ATPRG, were developed. The circuit model process using HDL-A was presented, including the development of the HDL-A modeled control sources and HDL-A modeled pseudo circuits. The major contributions in this thesis study can be categorized as follows: (a) Developing an efficient diagnosability analysis process to evaluate the diagnosabil- ity of a circuit from the given circuit topology and selected test points. The process 96 can also identify the portion with poor diagnosability; (b) Developing an effective redesignability analysis process to check if a portion with poor diagnosability can be redesigned; (c) Developing an efficient test points section process to select the number of test points required and their locations to meet the desired diagnosability; ((1) Developing the first automatic test program generator with HDL-A so that the developed fault diagnosis process can be used for large analog/mixed-signal inte- grated circuits; and (e) Integrating the developed process to an automated diagnostic test system. 7.2 Future Work It is believed that the complexity of analog/mixed-signal ICs will continuously increase. Further enhancing circuit testability and diagnosability becomes very important tasks and developing efficient and effective diagnosable design methodology becomes a great demand for IC industrials. This thesis study has effectively demonstrate the feasibility of the developed anal- ysis processes and design methodologies. However, for practical large analog/mixed-signal integrated circuits, further quality improvements are necessary and can be achieved in the following different ways. As the circuit complexity increases, searching the valid diagnos- able configurations in the diagnosability analysis process becomes very complex. Thus, developing efficient searching algorithms will promote the developed diagnosability anal- ysis process to be applied for practically large analog/mixed—signal circuits. Similarly, the searching complexity for redesignability analysis, test points section, and test program gen- 97 eration increases as the Circuit complexity increases. For the redesignability analysis process, the emphasis of this study was placed on the development of redesignability check. Once a circuit is determined to be redesignable, the I/O relations of the missing components are derived. Efficiently deriving the I/O rela- tions becomes an important tasks for the redesignability analysis and should be investigated further. How to select the appropriate test signals to derive the I/O relations is also an important tasks to work. The automatic test program generation process can effectively generate the test pro- grams for fault diagnosis of analog/mixed-signal circuits. It is efficient and effective because the use of hardware description languages. Once the generated test programs are used for fault diagnosis, the test programs are simulated. The developed system ADTS is capable of simulating any reasonably large linear analog circuits. For nonlinear circuits, however, the fault simulations become the bottleneck of the fault diagnosis process. Devel- oping an efficient simulator for simulating such test programs efficiently is also an impor- tant research topic for further investigation. 98 10. ll. 12 13. REFERENCES . A. Mastsuzawa, “Low-Voltage and Low-Power Circuit Design for Mixed Analog/ Digital Systems in Portable Equipment”, IEEE Journal of Solid-State Circuits, Vol. 29, No.4. pp. 470-480, April 1994. CL. Wey, “Mixed-Signal Testing « a Review”, (invited), Proc. of the IEEE International Conference on Electronics, Circuits, and Systems, Rodos, Greece, pp. 1064-1067, 1996. CL. Wey, “Mixed-Signal Fault Models and Design For Test”, (Tutorial Course), IEEE Asian Test Symposium, Hsinchu, Taiwan, 1996. C.-P. Wang, “Efficient Testability Design Methodologies for Analog/Mixed-Signal Integrated Circuits”, Ph.D. Dissertation, Department of Electrical Engineering, Michigan State University, 1997. W.-H. Huang, J.A. Resh, and CL. Wey, "On Synthesis of Manufacturable and Testable Analog Integrated Circuits," Proc. of the 41th Midwest Symposium on Circuits and Systems, Notre Dame, IN, 1998. R. Spence, Tolerance Design of Electronic Circuits, Addison-Wesley Publishing Company, 1988. M. Li and L. Milor, "Computing Parametric Yield Adaptively Using Linear Modelis," Proc. Design Automation Conference, pp. 831-836, 1996. C.-P. Wang and CL. Wey, “Development of Hierarchical Testability Design Methodologies for Mixed-Signal/Analog Integrated Circuits”, Proc. of the International Conference on Computer Design (ICCD 97), pp. 468-474, 1997. R.-W. Liu, “Testing and Diagnosis of Analog Circuits and Systems”, North-Holland, 1991. J.W. Bandler and A.E. Salama, “Fault Diagnosis of Analog Circuits”, IEEE Proceedings, pp. 1279-1325, August 1985. R. Sacks, “Criteria For Analog Fault Diagnosis”, Proc. of the European Conference on Circuit Theory and Design, pp. 75-78, 1981. L. Rapisarda and R. DeCarlo, “Analog Multi-frequency Fault Diagnosis”, IEEE Trans. on Circuits and Systems, Vol.CAS-30, No.4, pp. 223-234, April 1983. Z.F. Huang, C.-S. Lin, and R.-W. Liu, “Node-fault Diagnosis and a Design of Testability”, IEEE Trans. on Circuits and Systems, Vol. CAS-30, pp. 257-265, May 1983. 99 14. M. Slamani and B. Kaminska, “Analog Circuit Fault Diagnosis Based on Sensitivity Computation and Functional Test”, IEEE Design & Test of Computers, pp. 30-39. 1992. 15. A. Charoenrook and M. Soma, “Fault Diagnosis of Flash ADC Using DNL Test”, Proc. of the International Test Conference, pp. 680-689, 1993. 16. CL. Wey and R. Sacks, “On the Implementation of An Analog ATPG: The Linear Case”, IEEE Trans. on Instrumentation and Measurement, Vol. IM-34, No.3, pp. 277- 284, Spetember, 1985. 17. CL. Wey and R. Sacks, “On the Implementation of An Analog ATPG: The Nonlinear Case”, IEEE Trans. on Instrumentation and Measurement, Vol. IM-37, No.2, pp. 252- 258, June 1988. 18. CL. Wey, “A Searching Approach Self-testing Algorithm For Analog Fault Diagnosis”, in Testing and Diagnosis of Analog Circuits and Systems, edited by R.-W. Liu, Chapter 6. pp. 147-186, North-Holland, 1991. 19. H. Dai and TM. Souders, “Time-Domain Testing Strategies and Fault Diagnosis For Analog Systems”, IEEE Trans. on Instrumentation and Measurement, Vol. IM-39, No.1, pp. 157-162, February 1990. 20. F. Lin, J. Markee and B. Rado, “Design and Test of Mixed Signal Circuits: A discrete- Event Approach”, Proc. of the 32nd Conference on Decision Control, pp. 217-222, 1993. 21. TH. Morrin, “Mixed-Mode Simulation for Time-Domain Fault Analysis”, Proc. of the International Test Conference, pp. 231-241, 1989. 22. A. Balivada, J. Chen and LA. Abraham, “Analog Testing with Time Response Parameters”, IEEE Design & Test of Computers, pp. 18—25, 1996. 23. Z. You and E. Sanchez-S, “Analog System-level Fault Diagnosis Based on a Symbolic Method in the Frequency Domain”, IEEE Tran. on Instrumentation and Measurement, Vol. IM-44, No.1, pp. 28-35, February 1995. 24. M. Slamani and B. Kaminska, “Multi-frequency Testability Analysis for Analog Circuits”, Proc. of the 12th IEEE VLSI Test Symposium, pp. 54-59, 1994. 25. M. Slamani and B. Kaminska, “Fault Obervability Analysis of Analog Circuits in Frequency Domain”, Proc. of the IEEE Trans. on Circuits and Systems, Part.II, Vol. 43, No.2. pp. 134-139, February 1996. 26. S. S. Somayajula, E. Sanchez-S and J. Pineda de Gyvez, “Analog Fault Diagnosis Based on Ramping Power Supply Current Signature Clusters”, IEEE Trans. on Circuits and Systems. Part. II, Vol.43, No. 10, pp. 703-712, October 1996. 27. Z. Wang, G. Gielen and W. Sansen, “Testing of Analog Integrated Circuits Based on Power-Supply Current Monitoring and Discrimination Analysis”, Proc. of the 3rd Asian Test Symposium, pp. 126-131, 1996. 28. A. Walker, P.K. Lala and WE. Alexander, “Analogue Fault Diagnosis of Active 100 Networks Via Bias Modulation”, Electronics Letters, Vol. 27, No. 24, pp. 2279-2281, 1991. 29. A. Walker, W.E. Alexander and PK. Lala, “Fault Diagnosis in Analog Circuits Using Element Modulation”, IEEE Design & Test of Computers Vol. 9, No. 1, pp. 19-29, 1992. 30. W.-H. Huang and CL. Wey, “Development of Automated Diagnostic Test System for Mixed-Signal/Analog Integrated Circuits”, Proc. of the 40th Midwest Symposium on Circuits and Systems, Davis, pp. 1434-1437, CA, 1997. 31. W.-H. Huang and CL. Wey, “Diagnosability Analysis For Mixed-signal Integrated Circuits”, International Journal of Circuit Theory and Applications, Wiley, NY, Vol. 26, December 1998. 32. CL. Wey and W.-H. Huang, “Redesignability Check of Analog Circuits with Incomplete Implementation Information,” Accepted to appear in IEEE Trans. on Circuit and System, Part I, Fundamental Theory and Applications. 33. W.-H. Huang and CL. Wey, “Development of HDL-A Modeled Test Programs for Fault Diagnosis of Analog/Mixed-Signal Circuits”, Proc. of the 3rd IEEE International Mixed Signal Testing Workshop, Seattle, WA, pp. 344, 1997. 34. R.C.-J. Shi, “AHDL Tutorial”, presented in 3rd IEEE International Mixed Signal Testing Workshop, Seattle, WA, 1997. 35. J. Bhasker, “A VHDL Premier”, Prentice Hall, 1992. 36. W.-H. Huang, “ADTS: An Automatic Diagnostic Test System for Analog Circuits - User’s Manual and Programmer’s Guide”, Department of Electrical Engineering, Michigan State University, 1998. 37. P. Duhamel and J.-C. Rault, “Automatic Test Generation Techniques for Analog Circuits and Systems: A Review”, IEEE Trans. on Circuits and Systems. Vol. CAS-26, No.7. PP. 411-439, February 1979. 38. CL. Wey, “Parallel Processing for Analog Fault Diagnosis”, International Journal of Circuit Theory and Applications, Wiley, NY, Vol.16, No.3. pp. 303-316, July 1988. 39. CL. Wey, “Design of Testability for Analog Fault Diagnosis”, International Journal of Circuit Theory and Application, Vol.15, No.2, pp. 123-142, April 1987. 40. C.-K. Ho, P.R. Shepherd, W. Tenten and R. Kainer, “Improvements in Analogue Fault Diagnosis Techniques”, Proc. of the 2nd IEEE International Mixed Signal Testing Workshop, Quebec, Canada, pp. 81-97, 1996. 41. CL. Wey, "Built-In Self-Test (BIST) Structure for Analog Circuits Fault Diagnosis," IEEE Trans. on Instrumentation and Measurement. Vol. IM-39, No.2, pp. 517-521, June 1990. 42. CL. Wey, "Alternative Built-In Self-Test Structure (BIST) for Analog Circuit Fau1t Di- agnosis," Electronics Letters. Vol.27, No.18, pp. 1627-1628, August 1991. 43. CL. Wey and S. Krishnan, "Built-In Self-Test (BIST) Structures for Analog Circuit Fault Diagnosis with Current Test Data," IEEE Trans. on Instrumentation and Measure- 101 ment, Vol. IM-4l, No.4, pp. 535—539, August 1992. 44. M. Soma, "Structure and Concepts for Current-based Analog Scan," Proc. of the Cus- tom Integrated-Circuits Conference, pp. 517-520, 1995. 45. CL. Wey, "Built-in Self-Test (BIST) Design of Current-mode Algorithmic AID Con- verter" IEEE Trans. on Instrumentation and Measurement, Vol.1M-46, No.3, pp. 667- 671, June 1997. 46. MS. Nejad, L. Sebaa, A. Ladick and F. Kuo, “Analog Built-in Self-test”, Proc. of the 7th Annual IEEE International ASIC Conference and Exhibit, pp. 407-411, 1994. 47. A. Chatterjee, B.C. Kim and N. Nagi, “DC Built-in Self-test for Linear Analog Circuits”, IEEE Design & Test of Computers, Vol. 13, No. 2, pp. 26-33, 1996. 48. “AccuSim II HDL-A/DEV User and Reference Manual”, Software Version 8.4_1, Mentor Graphics Corporation, 1994. 49. RA. Saleh, D.L. Rhodes, E. Christen, and B.A.A. Antao, “Analog Hardware Description Languages”, Proc. of the IEEE Custom Integrated Circuits Conference, pp. 349-356, 1994. 50. R.C.-J. Shi, “HDL-A Design Objectives and Rationale”, Technical Report, Analogy, Inc., 1994. 51. M. Pierzchala and B. Rodanski, “Algebraic Method for Calculating Symbolic Network Functions of Large Electronic Networks”, Proc. of the 37th Midwest Symposium on Circuits and Systems, 1994. 52. TM. Souder and ON. Stenbakken, “A Comprehensive Approach For Modeling and Testing Analog and Mixed-Signal Devices”, Proc. of the International Test Conference, pp. 169-176, 1990. 53. CL. Wey, "Development of Redesign Process for Digital VLSI Systems,” Proc. 40th Midwest Symposium on Circuits and Systems, Davis, CA, pp. 177-180, 1997. 54. RP. Preparata, G. Metze, and RT. Chien, "On the Connection Assignment Problem of Diagnosable Systems," IEEE Trans. on Electronic Computers, Vol. EC-l6, pp. 448- 454,1967. 55. CS. Lin, Z.F. Huang, and R.-W. Liu, "Fault Diagnosis of Linear Analog Networks: A Theory and Its Application," Proc. of the IEEE International Symposiums on Circuits and Systems, pp. 1090-1093, 1983. 56. MA. Khalil, “Efficient Redesign Process for Digital VLSI Circuits”, Master Thesis, Department of Electrical Engineering, Michigan State University, 1998. 57. GM. Wierzba, Sspice User Manual, East Lansing, MI: Michigan State University Instructional Media Center, 1991. 58. S-M. Chang and GM. Wierzba, "Circuit Level Decomposition of Networks with Nullor for Symbolic Analysis," IEEE Transactions on Circuits and Systems, Vol. CAS-41, pp. 699-71 1, November 1994. 59. M.N.S. Swamy and K. Thulasiraman, Graph, Networks, and Algorithms, Wiley, 1981. 102 60. El. McCluSkey, Logic Design Principles with empahsis on Testable Semicustom Circuits, Prentice-Hall, Englewood Cliffs, New Jersey, 1986. 61. W.-H. Huang and CL. Wey, “Test Point Selection Process and Diagnosability Analysis for Analog Integrated Circuits,” IEEE International Concerence on Computer Design: VLSI in Computers & Processors (ICCD 98), pp. 582-587, 1998. 103 l'lIC HIan STATE UNIV. LIBRARIES llllllllllllllllllllllllllIllllllllllllllllllllllllllllllllll 31293018017164