Janusz A. Starzyk Topological Analysis and Diagnosis of Analog Circuits Wydawnictwo Politechniki Śląskiej Gliwice 2007 2 Contents List of Selected Symbols and Abbreviations......................................................................7 1. Introduction..................................................................................................................... 9 2. Graphs and Network Topology..................................................................................... 12 2.1. Graph Representations of Electronic Circuits........................................................ 12 2.2. Graph Decomposition............................................................................................ 17 2.2.1. Types of Graph Decomposition......................................................................18 2.2.2. Algorithms of Graph Decomposition.............................................................. 19 3. Topological Analysis ....................................................................................................21 3.1. Foundations of Topological Analysis ...................................................................21 3.2. Signal-Flow Graph Analysis of Electronic Circuits .............................................25 3.2.1. Direct Signal-Flow Graph Analysis................................................................ 29 3.2.2. Descending Hierarchical Signal-Flow Graph Analysis..................................30 3.2.3. Ascending Hierarchical Signal-Flow Graph Analysis....................................33 3.3. Directed Graph Analysis of Electronic Circuits .................................................... 35 3.3.1. Direct Directed Graph Analysis......................................................................37 3.3.2. Descending Hierarchical Directed Graph Analysis ........................................38 3.3.3. Ascending Hierarchical Direct Graph Analysis..............................................40 3.4. Conjugated Graph Analysis of Electronic Circuits ................................................ 41 3.4.1. Direct Conjugated Graph Analysis .................................................................42 3.4.2. Descending Hierarchical Conjugated Graph Analysis ...................................43 3.5. Algorithms for Topological Analysis Methods ..................................................... 45 3.5.1. Multiconnections of a Signal-Flow Graph...................................................... 46 3.5.2. Multitrees of a Directed Graph .......................................................................48 3.6. Other Advances in Topological Analysis Methods...............................................49 3.6.1. Hierarchical Analysis of High Frequency Interconnect Networks ................. 50 3.6.2. Large Change Sensitivity Based Diakoptic of Large Analog Networks ........57 3.7 Summary of Topological Analysis Methods ........................................................ 65 4. Topological Diagnosis ..................................................................................................67 4.1. Fault Location in Nonlinear Networks ..................................................................68 4.1.1. Network Decomposition................................................................................. 69 4.1.2. Faulty Regions................................................................................................ 73 4.2. Fault Location in Linear Networks .......................................................................76 4.2.1. Location of Faulty Elements...........................................................................77 4.2.2. Fault Location by Nodal Analysis ..................................................................78 4.2.3. Topological Conditions for Node Fault Diagnosis .........................................80 4.2.4. Parameter Tolerances...................................................................................... 82 4.2.5. Multiport Approach to Fault Location............................................................ 83 4.3. Sensitivity Approach............................................................................................. 86 3 4.3.1. Decomposition Approach to Sensitivity Based Testing .................................88 4.4. Fault Verification in Multiple-Fault Diagnosis of Linear Networks ..................... 93 4.4.1. Fault Diagnosis Equations ..............................................................................94 4.4.2. Fault Diagnosis Process.................................................................................. 97 4.4.3. Large Change Sensitivity in Fault Diagnosis................................................ 103 4.5. Low Testability Analog Circuits..........................................................................107 4.5.1. Fault Verification by Locating Ambiguity Groups.......................................111 4.5.2. Fault Diagnosis in Mixed-Signal Low Testability System........................... 113 4.6. Entropy Based Optimum Test Points Selection................................................... 115 4.6.1. Integer Coded Dictionary..............................................................................116 4.6.2. Entropy Test Point Selection ........................................................................117 4.6.3. Statistical Experiments.................................................................................. 119 4.7. Summary of Topological Diagnosis Methods ..................................................... 120 5. Concluding Remarks...................................................................................................122 References....................................................................................................................... 124 Summary......................................................................................................................... 139 4 Spis Treści Wykaz Wybranych Symboli i Skrótów .....................................................................................7 1. Wstęp......................................................................................................................................9 2. Grafy i Topologia Układu....................................................................................................12 2.1. Grafy Układów Elektronicznych...................................................................................12 2.2. Dekompozycja Grafu ....................................................................................................17 2.2.1. Rodzaje Dekompozycji Grafu................................................................................18 2.2.2. Algorytmy Dekompozycji Grafu ...........................................................................19 3. Analiza Topologiczna ..........................................................................................................21 3.1. Podstawy Analizy Topologicznej .................................................................................21 3.2. Analiza Układów Elektronicznych przy Reprezentacji Grafem Przepływu Sygnału..........................................................................................................................25 3.2.1. Analiza Bezpośrednia przy Reprezentacji Grafem Przepływu Sygnału ..............29 3.2.2. Analiza Hierarchiczna Zstępująca przy Reprezentacji Grafem Przepływu Sygnału………………….......................................................................................30 3.2.3. Analiza Hierarchiczna Wstępująca przy Reprezentacji Grafem Przepływu Sygnału…...............................................................................................................33 3.3. Analiza Układów Elektronicznych przy Reprezentacji Grafem Skierowanym ............35 3.3.1. Analiza Bezpośrednia przy Reprezentacji Grafem Skierowanym .........................37 3.3.2. Analiza Hierarchiczna Zstępująca przy Reprezentacji Grafem Skierowan ym......38 3.3.3. Analiza Hierarchiczna Wstępująca przy Reprezentacji Grafem Skierowanym .....40 3.4. Analiza Układów Elektronicznych przy Reprezentacji Parą Grafów Sprzężonych .... 41 3.4.1. Analiza Bezpośrednia przy Reprezentacji Parą Grafów Sprzężonych ..................42 3.4.2. Analiza Hierarchiczna Zstępująca przy Reprezentacji Parą Grafów Sprzężonych...........................................................................................................43 3.5. Algorytmy Metod Analizy Topologicznej ....................................................................45 3.5.1. Wielo-połączenia Grafu Przepływu Sygnału.........................................................46 3.5.2. Wielo-drzewa Grafu Skierowanego.......................................................................48 3.6. Inne Usprawnienia Metod Analizy Topologicznej .......................................................49 3.6.1. Analiza Hierarchiczna Sieci Połączeń Wysokiej Częstotliwości ..........................50 3.6.2. Diakoptyka Dużych Układów Analogowych w Oparciu o Metodę Wrażliwości Wielkoprzyrostowej..........................................................................57 3.7 Podsumowanie Metod Analizy Topologicznej .............................................................65 4. Diagostyka Topologicza.......................................................................................................67 4.1. Lokalizacja Uszkodzeń w Układach Nieliniowych ......................................................68 4.1.1. Dekompozycja Układu...........................................................................................69 4.1.2. Obszary Uszkodzeń................................................................................................73 4.2. Lokalizacja Uszkodzeń w Układach Liniowych...........................................................76 4.2.1. Lokalizacja Uszkodzonych Elementów.................................................................77 4.2.2. Lokalizacja Uszkodzeń przy Pomocy Analizy Węzłowej .....................................78 5 4.2.3. Warunki Topologiczne Diagnostyki przy Pomocy Analizy Węzłowej .................80 4.2.4. Tolerancje Parametrów ..........................................................................................82 4.2.5. Metody Wielo-wrotnikowe Lokalizacji Uszkodzeń ..............................................83 4.3. Metody Wrażliwościowe ..............................................................................................86 4.3.1. Testowanie Wrażliwościowe z Dekompozycją .....................................................88 4.4. Weryfikacja Uszkodzeń w Diagnostyce Układów Liniowych z Wieloma Uszkodzeniami..............................................................................................................93 4.4.1. Równania Diagnostyczne.......................................................................................94 4.4.2. Proces Diagnozowania Uszkodzeń........................................................................97 4.4.3. Diagnozowanie Uszkodzeń w Oparciu o Metodę Wrażliwości Wielkoprzyrostowej.............................................................................................103 4.5. Układy Analogowe o Niskiej Testowalności .............................................................107 4.5.1. Weryfikacja Uszkodzeń poprzez Lokalizację Grup Wieloznacznych.................111 4.5.2. Diagnozowanie Uszkodzeń w Układach Mieszanych o Niskiej Testowalności..113 4.6. Optymalny Wybór Punktów Pomiarowych w Oparciu o Entropię.............................115 4.6.1. Słownik Kodowany Liczbami Całkowitymi........................................................116 4.6.2. Wybór Punktów Pomiarowych w Oparciu o Entropię.........................................117 4.6.3. Eksperymenty Statystyczne .................................................................................119 4.7. Podsumowanie Metod Diagnostyki Topologicznej ....................................................120 5. Wnioski Końcowe..............................................................................................................122 Bibliografia.............................................................................................................................124 Streszczenie.............................................................................................................................139 6 List of Selected Symbols and Abbreviations A coefficient matrix A determinant of coefficient matrix B test verification matrix BDF backwards differentiation formula BiMOS bipolar MOS C set of connections C cardinality of the set C C weight of the set C cp proper multiconnection c multiconnection W CPU central processing unit CUT circuit under test CAD computer aided design CMOS complementary MOS d symbolic denominator terms DFT design for test E set of graph edges, entropy e unit vector F transfer function, set of faults FET field effect transistor f number of faults G(V,E), G graph Gs substitute graph of subgraph G i i G (cid:61637)G direct sum of subgraphs 1 2 G (cid:61639)G intersection of subgraphs 1 2 G (cid:61640)G union of subgraphs 1 2 G (cid:61485)G difference of subgraphs 1 2 GMTC generalized mutual-testing condition H hybrid matrix HOS hierarchically organized structure h characteristic function I current vector IC integrated circuit J independent current excitations K voltage gain vv KCL Kirchhoff current law KVL Kirchhoff voltage law L symbolic numerator terms l decomposition level 7 M measurement set m number of measurements MOS metal-oxide semiconductor MTC mutual-testing condition n number of nodes O order of complexity P set of path, current graph incidence matrix Q voltage graph incidence matrix R upper triangular matrix S set of subgraphs, subnetworks s complex frequency variable SAT simulation after test SBT simulation before test SC switched capacitor SOC system on chip STC self-testing condition T set of trees, transmission matrix t time variable tp proper multitree t multitree V V set of graph vertices (nodes), voltage vector VLSI very large scale integrated circuits W set of pairs of vertices, excitation vector X solution vector Y admittance Z impedance (cid:61540) parameter deviation (cid:61542) vector of network parameters (cid:61548) indefinite incidence matrix (cid:61638) empty set 8 1. Introduction Did you ever wonder what graphs, Kirchhoff laws, the Internet, rough sets, neural networks, and brain organization have in common? The answer may be very simple - the system topology. Whether it is a flow-graph that describes the flow of signals between the nodes of a graph, Kirchhoff laws that describe relation ships between currents or voltages in an electronic network, or the Internet that uses a web of interconnected computers to move packets of data between the end users, they all rely on specific topological information about the system structure. A similar argument can be used for rough sets that describe features of the information system; neural networks that implement the connectionist concept of massively parallel interconnect structures of processing elements; or the human brain - the most complex, and still only sketchily described, system of interconnected neurons. In all of these systems topology determines how the system operates. Topology is a silent system of constrai nts imposed on an electronic network, governing the signal flow between its components. Thus it is used in all aspects of system design from system analysis and synthesis through diagnosis. Over many years computer analysis of large analog circuits was an important research topic presented in many monographs and research papers [23], [55], [56], [104], [138], [174], [193], [203], [281]. The main objective of these works was to improve computational efficiency of the computer analysis methods (like accuracy of the results, analysis time, memory requirements, numerical stability and convergence, etc.) and to obtain full, accurate, and illustrative information about the analyzed circuits. These were also the objectives of the symbolic or semi symbolic network analyses [5], [83], [145], [205], [206], [215], [216]. Since it was difficult to develop effective programs of topological analysis for large networks, the development in these years was focused on numerical methods for sparse matrices [27], [55], [99], [105] or eigenvalues methods [41], [121], [139], [155], [177], [202], [218]. Since then computer aided analysis and computer aided design of electronic circuits developed into a leading industry behind the microelectronic revolution with many professional conferences, design tools, software vendors, design houses, and fabrication facilities. In this development the symbolic analysis methods played an important role. Also for many years the analog fault diagnosis and fault location in analog circuits have been challenging tasks for both design researchers and practitioners [69], [259]. Relationships between the input and output signals in analog circuits are obscure compared to precise relationships in digital circuits. Statistical distribution of faults or their character is unpredictable. Changes in the circuit response are not linear functions of changes in the parameter values even if a circuit is linear. Modern VLSI technology integrates many thousands of analog components sharing the same silicon substrate with even more numerous digital components, with relatively few points accessible for measurements. Lack of access to the internal points for measurements and lack of good fault models are making design for test difficult, and the analog nature of parameter changes compounds the problem. Over the years importance of the analog testing grew. As the testing costs started to exceed the design costs, the integrated circuit industry needed more effective design for test techniques and good testing standards. Many 9 conferences devoted to design automation and test have been organized , attracting constant attention and research efforts in this area. Topological analysis of electronic circuits relates to learning circuit properties based on the circuit components and the way they are connected (circuit topology) without using numerical methods to solve the circuit equations. It results in transfer functions of the analyzed circuits that represent ratio of the Laplace transform of the output and input signals. Network topology can also be used indirectly to aid the circuit analysis or to simplify organization of its numerical analysis. Topological diagnosis uses network topology to determine testability conditions, isolate faulty subnetworks and locate faulty parameters, determine test coverage and test point selection, and identify ambiguity conditions. It can do so without regard the amount of p arameter deviations from their nominal values. The main objective of this work is to show how topological methods can be used in the analog circuit analysis and testing techniques, how they can enrich the software tools used in computer aided analysis, and how they can enhance the design for testability process. More specific objective of this work is to address the problems of topological analysis of large analog networks, considering various topological representations of the circuit elements. These problems include the development of effective methods and algorithms of topological analysis of large electronic networks that lead to analysis time comparable with time needed for the numerical analysis. The practical need to consider various topological representations stems from the differences in the topological analyses, different treatment of such representations in the literature , and problems with identifying the optimum representation for the topological analysis. Another specific objective is to show how the network topology can be used to develop the testing tolls for analog circuits. These include the development of testability requirements, formulation of effective test equations, selection of test points, multiple fault verification techniques, fault location in large analog networks to identify faulty nodes and faulty components, and an effective treatment of the low testability circuits. Presented approaches to reach these objectives were proposed first at the beginning of nineteen eighties [226] and elaborated and extended over the years to encompass the above mentioned problems [10], [40], [77], [133], [134], [148], [182], [201], [221], [223], [224], [227]-[242], [244]-[248], [251]. Development of computer analysis programs and inclusion of the discussed topological approaches in the software tools [21], [37]-[39], [98], [132], [222], [225], [234], [243] facilitated the use of the proposed methods in practical projects. Fragments of such projects are presented in this work to illustrate principles and forms of topological network analysis and diagnosis. The work focuses on author’s research work in topological analysis and diagnosis. It tries to put a framework over two disciplines related through topological treatment of the discussed analysis and testing problems. It explores dependencies that relate a topological description to the flow of information between the processing nodes, and provides elegant, mathematically simple relationships, independent of the system size and complexity. Yet system size and complexity affect the computational effort needed to compute the results using the network topology. Therefore, special attention is paid to developing algorithmic approaches that facilitate working with large systems. This work discusses only major results that author obtained in topological analysis and diagnosis, with references to published work for further details. When needed for clarity of 10