Fault Diagnosis in Analog Circuits via Symbolic Analysis Techniques

1. Introduction

Fault diagnosis of analog circuits has been one of the most challenging topics for researchers and test engineers since the 1970s. Given the circuit topology and nominal circuit parameter values, fault diagnosis is to obtain the exact information about the faulty circuit based on the analysis of the limited measured circuit responses. Fault diagnosis of analog circuits is essential for analog and mixed-signal systems testing and maintenance both during the design process and the manufacturing process of VLSI ASICs.

There are three dominant and distinct stages in the process of fault diagnosis: fault detection to find out if the circuit under test (CUT) is faulty comparing with the fault-free circuit, or golden circuit (This stage is usually called test in industry), fault identification to locate where the faulty parameters are inside the faulty circuit, and parameter evaluation to obtain how much the faulty parameters deviated from their nominal values and to obtain values of other circuit parameters such as branch and nodal voltages. The bottlenecks of analog fault diagnosis primarily lie in the inherited features of analog circuits: nonlinearity, parameter tolerances, limited accessible nodes, and lack of efficient models. Multiple fault diagnosis techniques are even less developed than single fault diagnosis because it is more difficult to model and detect multiple faults, particularly in the presence of tolerance or measurement noise. In addition, in multiple fault situation, one fault’s effect on the circuit could be masked by the effects of the other faults. Generally speaking, there is no widely accepted paradigm for analog test or fault diagnosis even with the introduction of IEEE 1149.4 standard for mixed-signal test bus.

With recent sharp development of electronic design automation tools and widespread application of analog VLSI chips and mixed-signal systems in the area of wireless communication, networking, neural network and real-time control, the interests in analog test and fault diagnosis revives. System-on-chip solutions favored by modern electronics pose new challenges in this topic such as increased complexity and reduced die size and accessibility.

Several methods have been proposed for single fault diagnosis in linear analog circuit in the past. Multiple excitations are required and Woodbury formula in matrix theory is applied to locate the faulty parameters. This method is also applied to multiple fault diagnosis by decomposition technique assuming that each sub-circuit contains at most a single faulty parameter.

Among the different methods of fault diagnosis, the parametric fault diagnosis techniques hold an important part in the field of analog fault diagnosis. These techniques, starting from a series of measurements carried out on a previously selected test point set, given the circuit topology and the nominal values of the components, are aimed at determining the effective values of the circuit parameters by solving a set of equations generally nonlinear with respect to the component values. In this chapter the role of symbolic techniques in the automation of parametric fault diagnosis of analog circuits is investigated followed by a practical numerical procedure to evaluate the faults. Being in fact the actual component values that represent the unknown quantities, fault diagnosis aims also at finding the faults locations. Symbolic approach results are particularly suitable for the automation of parametric fault diagnosis techniques [1]. Obviously all this is applicable to linear analog circuits or to nonlinear circuits suitably linearized. On the other hand, present trend is moving as much as possible to design techniques that lead to linear analog circuits, so linearity is not a so serious restriction any more [2]. It is important to note that in the analog fault diagnosis two phases can be considered: the first one is the phase of testability analysis and ambiguity group determination, while the second one is the phase of fault location and fault value determination. Testability gives theoretical and rigorous upper limits to the degree of solvability of fault diagnosis problem once the test point set has been chosen, independently of the method effectively used in fault location phase. This becomes very important in the design stage of the linear circuit in which the designer can determine the list of accessible nodes for the operator and the fault detection ability that they can provide. Concerning ambiguity groups, they can be considered as sets of circuit components that, if considered as potentially faulty, yield an undetermined system of equations. For the testability evaluation problem symbolic approach is a natural choice, because a circuit description made by means of equations in which the component values are the unknowns is properly represented by symbolic relations. Also for ambiguity group determination the symbolic approach gives excellent results [3].

For the fault location phase several different approaches can be used and all of them can be considered as an optimization problem, because, starting from measurements carried out on the CUT, the component values better fitting them have to be determined. Generally symbolic techniques are suitable for optimization problems, because the relations required by specific optimization strategies are easily generated using symbolic methods.

The aim of this chapter is to present a unified treatment of the subject with emphasis on a generalized method for multiple fault diagnosis of linear analog circuits in frequency domain. In this approach, multiple excitations and Woodbury formula are also required for fault identification. However, a recently developed ambiguity group locating technique is applied for fault identification which reduces computational cost of the test method. Multiple faults can be located directly and efficiently, thus eliminating the requirement for decomposition and the corresponding restrictions. Moreover, the methodology developed in the proposed method, (i.e., constructing fault diagnosis equation on the basis of the analysis of the fault-free circuit and the measured responses of faulty circuit, then applying the ambiguity group locating technique to identify the faulty parameters, finally evaluating all parameter values of faulty circuit exactly), can be applied to other methods developed for multiple analog fault diagnosis.

The dominant differences among these methods are the distinct fault diagnosis equations resulting from distinct circuit analysis methods and distinct excitation and measurement methods. The methods proposed in this chapter can be classified as fault verification methods under the category of Simulation-after-Test (SAT), which can provide the exact solution to the circuit parameters and can be applied to detect large parameter changes when the number of independent measurements are greater than the number of faults in the CUT.

A major improvement of these techniques is achieved through the use of symbolic techniques in formulating the fault equations and in addressing the testability problem. Furthermore a developed method for minimum size ambiguity group locating technique is used based on QR factorization and is applied to detect and identify the multiple faults. Detailed procedures for a proposed fault diagnosis program are given to help practitioners and researchers as well to grasp the basic concepts of the topic and be able to contribute to this field.

2. Basic circuit formulations

Generally, the circuit topology as well as its parameters nominal values are known in advance. Consider for example a continuous-time, time-invariant, strongly connected, linear circuit with n+1 nodes and p parameters. The (n+1)^st node, denoted by zero, is assigned to be the grounded reference node while the remaining n nodes are ungrounded. All p parameters are divided into two categories: one is parameters which have admittance description such as conductance, capacitor and voltage- controlled-current source, another is parameters which have no admittance description such as impedance, inductor, current-controlled-source, operational amplifier, etc.

Of course the conventional method of analysis would be to apply the KCL to each circuit node to obtain n equations with variables being nodal voltages and parameter currents. Then constitutive equations in terms of nodal voltages and parameter currents, which define the characteristics of all parameters without admittance description, are appended to the above n KCL-based equations. The resulting system matrix from this approach would be

$${\mathit{T}}_{\mathit{g}}{\mathit{X}}_{\mathit{g}}={\mathit{W}}_{\mathit{g}}$$E1

where T_g is a g×g coefficient matrix consisting of circuit parameters, X_g is a g×1 solution vector of node voltage and parameter currents, and W_g is a g×1 excitation vector composed of independent current and voltage sources, and initial conditions of capacitors and inductors. The first n rows in T_g, X_g and W_g correspond to n nodes. The resulting system equation (1) is called the modified nodal analysis equation MNA [4]. Note that g=n for normal nodal analysis of a circuit in which all parameters have admittance description, and g>n for modified nodal analysis of a circuit in which some parameters have a non-admittance description.

Traditionally, the system matrix generated from the MNA method may still have many redundant variables for analysis purposes; for example: voltages of inaccessible nodes inside sub-circuits like op-amps or currents through nonphysical branches generated from sophisticated element models. A major development step to the MNA method is to eliminate all redundant variables to generate a compacted or reduced system matrix. The reduced system matrix is formulated by programming a lookup table for every element in the network. This table has conditioned link-lists that will test which variables of the element are actually needed in the final compacted matrix and introduce the element in a way so as to eliminate the redundant variables during the formulation process. This method is termed the compacted modified nodal analysis CMNA [5]. Provided that the circuit functions in a stable state, the parametric values of nodal voltages and parameter currents will be finite and unique. The coefficient matrix T_g is non-singular since the circuit is a strongly connected network.

Generally the system matrix described above cannot be formulated smoothly in a computerized solution without taking the circuit topology into consideration. One important fact about circuit topology is that each parameter, say h_v ( v = 1, 2,..., p ), can be located by at most 4 circuit nodes [6]: 2 input nodes k_v and l_v, and 2 output nodes i_v and j_v. For 2-terminal parameters such as resistors and capacitors, the input nodes will be the same as the output nodes: k_v = i_ν and l_v = j_ν. Based on this fact, the circuit topology can be completely described by two g×p structural matrices P and Q which are defined as follows:

$$\begin{array}{c}\mathit{P}=\left[{\mathit{p}}_1\mathrm{ }{\mathit{p}}_2\mathrm{ }\cdots \mathrm{ }{\mathit{p}}_{\mathit{p}}\right]=[{\mathit{\delta }}_{{\mathit{i}}_1}-{\mathit{\delta }}_{{\mathit{j}}_1}\mathrm{ }{\mathit{\delta }}_{{\mathit{i}}_2}-{\mathit{\delta }}_{{\mathit{j}}_2}\mathrm{ }\cdots \mathrm{ }{\mathit{\delta }}_{{\mathit{i}}_{\mathit{p}}}-{\mathit{\delta }}_{{\mathit{j}}_{\mathit{p}}}]\\ \mathit{Q}=\left[{\mathit{q}}_1\mathrm{ }{\mathit{q}}_2\mathrm{ }\cdots \mathrm{ }{\mathit{q}}_{\mathit{p}}\right]=[{\mathit{\delta }}_{{\mathit{k}}_1}-{\mathit{\delta }}_{{\mathit{l}}_1}\mathrm{ }{\mathit{\delta }}_{{\mathit{k}}_2}-{\mathit{\delta }}_{{\mathit{l}}_2}\mathrm{ }\cdots \mathrm{ }{\mathit{\delta }}_{{\mathit{k}}_{\mathit{p}}}-{\mathit{\delta }}_{{\mathit{l}}_{\mathit{p}}}]\end{array}$$E2

where δ_ν represents a g×1 vector of zeros except for the v entry, which is equal to one, and p_ν and q_ν represent g×1 vectors describing the locations of output nodes and input nodes, respectively. Matrices P and Q are only determined by the locations, not the values of the circuit parameters. The columns of matrix P correspond to the locations of the output nodes of circuit parameters while the columns of matrix Q correspond to the locations of the input nodes of circuit parameters.

Another important fact is that most parameters in linear circuits will enter the coefficient matrix T_g in the symbolic form

$$\begin{array}{c}\begin{array}{cc}{\mathrm{ } k}_v& {\mathrm{ } l}_v\end{array}\\ \begin{array}{cc}\begin{array}{c}{i}_v\\ j_v\end{array}& \left[\begin{array}{cc}{h}_v& -h_v\\ -h_v& h_v\end{array}\right]\end{array}\end{array}$$E3

with the equivalent algebraic representation being

$$\left({\mathit{\delta }}_{{\mathit{i}}_{\mathit{v}}}-{\mathit{\delta }}_{{\mathit{j}}_{\mathit{v}}}\right)h_v{\left({\mathit{\delta }}_{{\mathit{k}}_{\mathit{v}}}-{\mathit{\delta }}_{{\mathit{l}}_{\mathit{v}}}\right)}^t={\mathit{p}}_{\mathit{v}}{h}_v{\mathit{q}}_{\mathit{v}}^t$$E4

where superscript t denotes transpose of matrix or vector. For any grounded node, the corresponding row or column in the symbolic form will be removed together with the δν in the algebraic form. Resistor, inductor, capacitor, dependent sources, and operational amplifier with its negative inverse gain being a parameter are examples of circuit devices described in this way. Thus the system matrix can be easily formulated using the equation

$${\mathit{T}}_{\mathit{g}}=\mathit{P}diag\left(\mathit{h}\right){\mathit{Q}}^t\mathrm{ }$$E5

This topological formulation allows for the automatic direct translation of the Netlist (which is the list describing the values of the circuit elements and their connections to the corresponding nodes) into circuit equations. As an example consider the circuit shown in Figure 1 following [7]. This circuit will be used later in the analysis of fault equations.

Figure 1.

Example circuit

This circuit can be represented by the Netlist shown in Table 1. The first column of Table 1 is the element name and type (e.g. R for resistor, G for conductance, C for capacitor and so on). The second and third (possibly fourth and fifth depending on the element type) represent the connection nodes. Note that the ground is identified with node 0. The last column is the element value. It is possible for some elements (like a two port network or an active element model) to have more columns for its values. For the circuit in Figure 1 with unity current source J=1A applied to nodes {0,1}, it is assumed that the nominal values of the resistors are as follows (all resistors in Ω): R₁=2.125, R₂=3.6, R₃=4.7, R₄=11.5, R₅=12.6, R₆=21.2, R₇=3.7, R₈=0.54, R₉=3.54, R₁₀=3.125, R₁₁=6.6, R₁₂=5.7, R₁₃=19.5, R₁₄=12.8, R₁₅=12.2, R₁₆=3.2, R₁₇=1.54, R₁₈=8.7, R₁₉=2.27, R₂₀=3.16, R₂₁=41.7, R₂₂=31.5, R₂₃=22.6, R₂₄=51.2, R₂₅=13.7, R₂₆=3.44, R₂₇=13.4, R₂₈=31.9, R₂₉=16.1, R₃₀=11.7, R₃₁=11.5, R₃₂=17.8, R₃₃=22.2, R₃₄=23.2, R₃₅=11.4, R₃₆=18.7, R₃₇=3.12, R₃₈=33.2, R₃₉=8.67.

Element	From Node	To Node	Value
J	0	1	1
R1	1	2	2.1250
R2	2	4	3.6000
R3	2	3	4.7000
R4	3	4	11.5000
R5	1	4	12.6000
R6	3	5	21.2000
R7	5	6	3.7000
R8	0	5	0.5400
R9	0	1	3.5400
R10	0	6	3.1250
R11	6	8	6.6000
R12	6	8	5.7000
R13	8	9	19.5000
R14	0	9	12.8000
R15	15	16	12.2000
R16	15	17	3.2000
R18	3	10	8.7000
R19	8	10	2.2700
R20	7	9	3.1600
R21	0	13	41.7000
R22	7	11	31.5000
R23	7	12	22.6000
R24	11	12	51.2000
R25	11	19	13.7000
R26	12	19	3.4400
R27	12	20	13.4000
R28	7	13	31.9000
R29	13	20	16.1000
R30	19	20	11.7000
R31	18	19	11.5000
R32	18	20	17.8000
R33	17	18	22.2000
R34	13	16	23.2000
R35	16	17	11.4000
R36	14	17	18.7000
R37	14	16	3.1200
R38	14	15	33.2000
R39	0	14	8.6700

Table 1.

Netlist for the circuit shown in Figure 1

It can be shown easily [4] that the node numbers in the second column of Table 1 represent the values of i in equation (2) as long as they are not zero. Similarly column 3 gives the values of j in equation (2). Thus it is very straight forward to find the P and Q matrices by tracing through the Netlist. Additionally, the system matrix can be either formulated numerically or symbolically depending on the values used for h in the diagonal matrix of equation (5). This automatic formulation procedure can be easily extended to MNA and CMNA methods with proper rubber stamps for circuit elements.

3. Conventional fault analysis methods

As discussed earlier, the conventional method for multiple fault diagnosis can be divided into three steps: fault detection, fault location determination, and finding the faulty elements values. This conventional method is readily deemed to be a numerical method by its very own nature but it is presented here as it provides basic insight to the problem and the limitations facing all numerical methods. The problem is even more complicated for multiple faults due to ambiguity presented by element tolerances not to mention that different sets of certain faults may produce very similar measured values. Further complication is present owing to the fact that only a limited number of nodes are actually accessible for measurements and testing. The conventional method will be presented without derivation which can be found in [6-8]. Despite its effectiveness in dealing with ambiguity groups, the method has several limitations:

1. The method requires multiple independent excitations among the accessible nodes. That is applying an independent source of excitation to a subset of the accessible nodes and measuring the circuit response for each source. By this, the method not only assumes that the circuit will remain linear and well-behaved under multiple excitations, it also destroyes the natural input-output relation of the circuit components and overlooks any form of signal isolation.

2. The method needs a dictionary for the behavior of the fault-free circuit under multiple excitations. The dictionary must be extensive enough to enable detecting and locating a number of simultaneous faults. Yet even when the dictionary is extensive enoguh the method may still fail in differentiating certain ambiguity groups subject to rounding errors, inaccuracies and noise that may occur in the measurements.

3. Depending on the set of accessible nodes the problem of testability and detectability of multiple faults immediately arises.

Symbolic analysis techniques aim at resolving or at least reducing some or all of these limitations thus proving to be very vital to this subject. Having that said let us begin by showing the applications of symbolic analysis techniques for multiple fault diagnosis in linear circuits.

3.1. Symbolic analysis in fault diagnosis problem

As mentioned earlier, the symbolic circuit matrix T can be easily described by the multiplication of a row operator P and a column operator Q with a diagonal matrix of symbols, where P and Q are the matrix operators (or topological matrices) that indicate location of the matrix element value in the symbolic matrix T as was given in equation (5). One can immediately notice that the diagonal matrix can be represented by a simple array while both P and Q are sparse numerical matrices. One benefit of this representation is that linear operations on rows such as addition or subtraction can be simply implemented on P while linear operations on columns can be implemented on Q without altering the diagonal symbolic matrix. For most circuit analysis applications, system equations are rarely fully dense or fully symbolic. In that respect, some matrix elements may contain not only a single symbolic element value but constant values as well. These constants do not affect the structures of matrices P and Q. In fact even if the element values are complete polynomials the representation is still not altered. Hence in solving a matrix equation like equation (1) only arrays of symbolic polynomial data structures need to be stored to represent the diagonal matrix while numerical matrices P, Q can be manipulated to solve this system using topological methods like determinant decision diagrams DDD [9] or matrix reduction methods [10].

Traditionally symbolic techniques have been used along two separate paths in fault analysis: To introduce comprehensive fault models in small and moderate sized circuits and to find the optimum set of testable components in a faulty circuit. We will describe here both techniques and show ways of utilizing them later.

3.1.1. Symbolic techniques in comprehensive fault modeling

The method described before for tracing through the Netlist to generate the P and Q topological matrices is not the only way to generate the system matrix. In fact, most of the modified and compacted methods like the tableau, MNA and CMNA methods focus on tracing through the Netlist in an element-by-element fashion, increasing the size of the generated system matrix iteratively. This approach has the advantage of providing a way to reduce the system matrix during the formulation step as will be shown shortly [5].

Consider a general admittance y connected between nodes i and j as shown in Figure 2. Assuming that the system matrix T is already generated for the other branches, the impact of this admittance (following the tableau formulation) on the system matrix is to add an additional row and column corresponding to the new system variable i_y

$$\left[\begin{array}{ccc}{y}_{ii}& y_{ij}& 1\\ y_{ji}& y_{jj}& -1\\ y& -y& -1\end{array}\right]\times \left[\begin{array}{c}{V}_i\\ V_j\\ i_y\end{array}\right]=\left[\begin{array}{c}{w}_i\\ w_j\\ 0\end{array}\right].$$E6

Now, if i_y is not a solution variable then it can be eliminated from the system matrix to generate a compacted matrix with respect to the axis i_y. Applying Kron’s reduction to eliminate axis-3 of this matrix we get [5]

$$\left[\begin{array}{c}{y}_{ii}+y y_{ij}-y\\ y_{ji}-y y_{jj}+y\end{array}\right]\times \left[\begin{array}{c}{V}_i\\ V_j\end{array}\right]=\left[\begin{array}{c}{w}_i\\ w_j\end{array}\right].$$E7

Equations (6) and (7) are the conditioned stamps for the admittance y and they can be programmed into a lookup table easily.

The occurrence of faults in circuit elements generally leads to a deviation in node voltages and branch currents from nominal values. The purpose of fault diagnosis is to use voltage measurements on a limited number of nodes to verify the presence of a fault in the circuit then identify the fault location and value through simulation. However additional care must be taken since the deviations in the measured values may very well result from normal parameter tolerances.

In general a fault is generated if the nominal element value is changed from y to y+dy beyond its tolerance. However instead of changing the value of y in the system matrix, owing to the symbolic approach we can simply introduce an extra faulty element dy and an extra faulty variable f as shown in Figure 3 for the passive admittance case. This deviation from nominal value will result in deviation in node voltages from V to V+dV and branch currents from I to I+I_f where I_f is the set of fault currents. As an example consider a linear admittance y connected between nodes i and j as shown in Figure 3.

Figure 2.

A general admittance example

Figure 3.

Fault element model for a linear admittance

Due to a fault the value of the admittance is changed to y+dy. Now following [5] the fault rubber stamp of (7) is changed to

$$\left[\begin{array}{ccc}{y}_{ii}+y& y_{ij}-y& 1\\ y_{ji}-y& y_{jj}+y& -1\\ 1& -1& \mathrm{\zeta }\end{array}\right]\times \left[\begin{array}{c}{V}_i\\ V_j\\ i_{\mathrm{f}}\end{array}\right]=\left[\begin{array}{c}{w}_i\\ w_j\\ 0\end{array}\right]$$E8

where we have appended the faulty element equation

$$v_i-v_j+\mathrm{\zeta }{i}_f=0,$$E9

in which ζ = (dy)^-1. We must emphasize here that this equation is appended to the original system matrix after the last nodal equation so that the faulty i_f variable will appear after the last solution variable in the fault-free system equation. The impact of this on the solution will be apparent shortly. Assuming that i_f is a solution variable, we can proceed by eliminating any non-solution variables in the stamp just like we did before to generate the faulty compacted system matrix stamp while leaving all the faulty currents as solution variables.

Clearly other fault models for the different circuit elements can also be developed by inspection. The stamping procedure for the faulty circuit elements generates the fault analysis equations. However, additional circuit elements and thus additional symbolic variables were introduced in the circuit to simulate the fault thus deeming this method suitable only for small and moderate sized networks. Assuming the original fault-free system equations were given by equation identical to (1) where T is the compacted modified system matrix, X is the chosen solution vector and W is the vector of excitation sources which might be a combination of currents and voltages. With the introduction of the faulty elements the size of the system matrix has increased. Careful consideration of element stamps like (8) show that the new faulty system equations can be written as

$$\left[\begin{array}{cc}T& P\\ Q& R\end{array}\right]\times \left[\begin{array}{c}X\\ X_f\end{array}\right]=\left[\begin{array}{c}W\\ 0\end{array}\right]$$E10

where X is the original solution vector while X_f is the solution vector of the fault currents and voltages. This formulation resulted from the fact that the fault variable was added after the last solution variable of the fault-free circuit. Expanding this equation, it can be shown that [5]

$$\left(T-P{R}^{-1}Q\right)X=W$$E11

where X is now the solution vector of the faulty system. Applying Woodbury formula [5] on (11) we get

$$X=\left[T^{-1}+T^{-1}P{\left(R+Q{T}^{-1}P\right)}^{-1}Q{T}^{-1}\right]W$$E12

Expanding (12) using (10) we get

$$X=X_o+∆X$$E13

where

$$∆X=T^{-1}P{\left(R+Q{T}^{-1}P\right)}^{-1}Q{X}_o$$E14

This gives the variation in the solution vector in terms of the nominal fault-free solution vector, the topological matrices and the original system matrix. The benefit of having this variation solved symbolically is that it gives direct relationship between shifts in element values and the corresponding variation in circuit response. Once those variables are obtained symbolically it is very easy to carry out an analysis like Monte-Carlo analysis [5] to help solve the fault/tolerance ambiguity and verify the presence of a fault. Not only fault verification is possible with this equation but also locating the faulty element(s) can be done even with measurements taken from a limited set of accessible nodes using the k-fault method [11] or a linear combination matrix which will be explained later on where only a small set of the solution variables are measured to estimate the fault location.

Despite the usefulness of this approach in finding the fault model, it is highly restricted to small and moderate scale circuits. In addition, due to ambiguities, it is customary to find that the inner matrix R+QT^-1P has become singular therefore limiting the practical use of equation (14). Nevertheless the approach is still needed to model the faults symbolically and to tackle the testability problem.

3.1.2. Symbolic solution of the testability problem

Fault diagnosis and fault location in analog circuits are of fundamental importance for design validation and prototype characterization in order to improve yield through design modification. In the analog fault diagnosis field, an essential point is constituted by the concept of testability which, independently of the method that will be effectively used in fault location, gives theoretical and rigorous upper limits to the degree of solvability of the problem, once the test point set has been chosen by the circuit designer. A well-defined quantitative measure of testability can be deduced by referring to fault diagnosis techniques of the parametric kind [12]. These techniques, starting from a series of measurements carried out on previously selected test points, are aimed at determining the upper limit of solvable circuit parameters by solving a set of equations (the fault diagnosis equations as will be shown later) which are nonlinear with respect to the component values.

The solvability degree of these nonlinear equations constitutes the most used definition of testability measure [12]. This measure can be also interpreted as an indication of the ambiguity resulting from any attempt to solve the fault equations in a neighborhood of almost any failure. In addition to being valuable for the circuit designer in determining the number of accessible nodes, it is also very important for the circuit operator since attempting to address the fault-diagnosis equation without having an estimate on the maximum number of faults that can be detected from the available test set is highly prohibited. In other words, the testability measure provides information about the number of testable components with the selected test point set. When the testability value is not at its maximum, that is when it is less than the total number of potentially faulty circuit components, the problem is not uniquely solvable and it is necessary to consider further measurements, i.e., other test points. Alternatively we can accept a reduced number of potentially faulty components in order to locate the elements which have caused the incorrect behavior of the CUT.

Generally, the second alternative is used for two reasons. First, not all the possible test points can actually be considered because of practical and economic measurement problems strictly tied with the used technology and with the application field of the circuit under consideration. Second, the number of faulty components is generally smaller than the total number of circuit components. The single fault case is the most frequent while double or triple cases are less frequent, and the case of all faulty components is almost impossible. Therefore, as the testability is normally not at its maximum, the fault diagnosis problem is dealt with by assuming the quite realistic hypothesis that the number of faulty components is bounded; that is, the k-fault hypothesis is made. Under this hypothesis, in order to locate the faulty elements with as low ambiguity as possible, it is of fundamental importance to determine a set of components that is representative of all the circuit elements. This helps reducing the solution time by providing a stopping criterion instead of wasting computer resources seeking unattainable solutions. In this section a procedure for the determination of the optimum set of testable components in the k-fault diagnosis of analog linear circuits is presented, where by the optimum set we mean a set of components representing all the circuit elements and giving a unique solution.

The procedure is based on the testability evaluation of the circuit and on the determination of the canonical ambiguity groups. Referring again, for the sake of simplicity, to parametric fault diagnosis techniques we need to make some definitions first. An ambiguity group can be defined as a set of components that, if used as unknowns (i.e., if considered as potentially faulty), gives infinite solutions during the phase of fault location determination. A canonical ambiguity group is simply an ambiguity group that does not contain other ambiguity groups. It is worth pointing out that the proposed procedure gives information independently of the method that will be effectively used in the fault location phase (both simulation after test and simulation before test methods), even if it has been developed by referring to parametric fault diagnosis techniques. Furthermore, in the automation of the procedure the use of symbolic techniques is of fundamental importance because symbolic analysis, due to the fact that it gives symbolic rather than numerical results, is particularly suitable for applications such as testability and canonical ambiguity group determination, as will be shown later.

It is necessary in this procedure to determine a set of equations describing the circuit under test and solve it with respect to the component values. In the case of analog linear time-invariant circuits, the fault diagnosis equations can be constituted by the network functions relevant to the selected test points [12] which are nonlinear with respect to the potentially faulty circuit parameters. By assuming that the faults can be expressed as parameter variations without influencing the circuit topology (as was done in the previous section where faults like short and open are not considered), the testability measure τ is given by the maximum number of linearly independent columns of the Jacobian matrix associated with the fault diagnosis equations, and it represents a measure of the solvability degree of the nonlinear fault diagnosis equations. The entries of the Jacobian matrix are rational functions depending on the complex frequency and the potentially faulty parameters. Thus, in order to evaluate the testability it is necessary to select fixed values for the potentially faulty parameter and the complex frequency. It can be shown that, once the frequency values are fixed, the rank of the obtained Jacobian matrix is constant almost everywhere, i.e., for all the potentially faulty parameter values except those lying in an algebraic variety [13]. Using this approach, the testability value, although independent of component values, is very difficult to handle and subject to round off errors if a numerical approach is used in its automation.

Generally the Jacobian matrix is very costly to find in fully symbolic form. It has been shown in [14] that starting from the network symbolic transfer functions expressed in the following way:

$$t_l\left(\mathit{h},s\right)=\frac{N_l\left(\mathit{h},s\right)}{D\left(\mathit{h},s\right)}=\frac{\sum _{i=0}^{n_l}\frac{a_i^{\left(l\right)}\left(\mathit{h}\right)}{b_m\left(\mathit{h}\right)}.s^i}{s^m+\sum _{j=0}^{m-1}\frac{b_j\left(\mathit{h}\right)}{b_m\left(\mathit{h}\right)}.s^j},\mathrm{ } l=1,\cdots ,\mathrm{ }K$$E15

where h = [h₁, h₂, …, h_p]^t is the vector of the potentially faulty parameters and K is the total number of equations, the testability is equal to the rank of a matrix E given by

$$E=\left[\begin{array}{cc}\begin{array}{cc}\begin{array}{c}\begin{array}{c}\frac{\partial \frac{a_0^{\left(1\right)}}{b_m}}{\partial h_1}\\ ⋮\end{array}\\ \frac{\partial \frac{a_{n_1}^{\left(1\right)}}{b_m}}{\partial h_1}\\ \begin{array}{c}⋮\\ \frac{\partial \frac{a_0^{\left(K\right)}}{b_m}}{\partial h_1}\\ \begin{array}{c}⋮\\ \frac{\partial \frac{a_{n_K}^{\left(K\right)}}{b_m}}{\partial h_1}\\ \begin{array}{c}\frac{\partial \frac{b_0}{b_m}}{\partial h_1}\\ ⋮\\ \frac{\partial \frac{b_{m-1}}{b_m}}{\partial h_1}\end{array}\end{array}\end{array}\end{array}& \begin{array}{c}\frac{\partial \frac{a_0^{\left(1\right)}}{b_m}}{\partial h_2}\\ ⋮\\ \begin{array}{c}\frac{\partial \frac{a_{n_1}^{\left(1\right)}}{b_m}}{\partial h_2}\\ ⋮\\ \begin{array}{c}\frac{\partial \frac{a_0^{\left(K\right)}}{b_m}}{\partial h_2}\\ ⋮\\ \begin{array}{c}\frac{\partial \frac{a_{n_K}^{\left(K\right)}}{b_m}}{\partial h_2}\\ \frac{\partial \frac{b_0}{b_m}}{\partial h_2}\\ \begin{array}{c}⋮\\ \frac{\partial \frac{b_{m-1}}{b_m}}{\partial h_2}\end{array}\end{array}\end{array}\end{array}\end{array}\end{array}& \begin{array}{cc}\begin{array}{c}\\ \cdots \\ \begin{array}{c}\\ \\ \begin{array}{c}\cdots \\ \\ \begin{array}{c}\\ \\ \begin{array}{c}\cdots \\ \end{array}\end{array}\end{array}\end{array}\end{array}& \begin{array}{c}\frac{\partial \frac{a_0^{\left(1\right)}}{b_m}}{\partial h_p}\\ ⋮\\ \begin{array}{c}\frac{\partial \frac{a_{n_1}^{\left(1\right)}}{b_m}}{\partial h_p}\\ ⋮\\ \begin{array}{c}\frac{\partial \frac{a_0^{\left(K\right)}}{b_m}}{\partial h_p}\\ ⋮\\ \begin{array}{c}\frac{\partial \frac{a_{n_K}^{\left(K\right)}}{b_m}}{\partial h_p}\\ \frac{\partial \frac{b_0}{b_m}}{\partial h_p}\\ \begin{array}{c}⋮\\ \frac{\partial \frac{b_{m-1}}{b_m}}{\partial h_p}\end{array}\end{array}\end{array}\end{array}\end{array}\end{array}\end{array}\right]$$E16

This matrix is independent of the complex frequency whose entries are constituted by the derivatives of the coefficients of the fault diagnosis equations with respect to the potentially faulty circuit parameters. If the fault diagnosis equations are generated in a completely symbolic form, the testability evaluation becomes easy to perform. In this case, the entries of the matrix E can be simply led back to derivatives of sums of products and the computational errors are drastically reduced in the automation phase. Once the matrix E has been determined, testability evaluation can be performed by triangularizing E and assigning arbitrary values to the components (since as was previously mentioned, testability does not depend on component values). Yet selecting the matrix E instead of the Jacobian matrix as the testability matrix results in a different testability measure not directly related to the desired measure. However, this limitation can be overcome by splitting the fault diagnosis equation solution into two phases. In the first phase, starting from the measurements carried out on the selected test points at different frequencies, the coefficients of the fault diagnosis equations are evaluated, eventually exploiting a least-squares procedure in order to minimize the error due to measurement inaccuracy. In the second phase, the component values are obtained by solving the nonlinear system constituted by the equations expressing the previously determined coefficients as functions of the circuit parameters. In this way the following nonlinear system has to be solved:

$$\begin{array}{c}\begin{array}{c}\begin{array}{ccc}\frac{a_0^{\left(1\right)}\left(\mathit{h}\right)}{b_m\left(\mathit{h}\right)}=A_0^{\left(1\right)}& \cdots & \frac{a_{n_1}^{\left(1\right)}\left(\mathit{h}\right)}{b_m\left(\mathit{h}\right)}=A_{n_1}^{\left(1\right)}\end{array}\\ ⋮\end{array}\\ \begin{array}{c}\begin{array}{ccc}\frac{a_0^{\left(K\right)}\left(\mathit{h}\right)}{b_m\left(\mathit{h}\right)}=A_0^{\left(K\right)}& \cdots & \frac{a_{n_K}^{\left(K\right)}\left(\mathit{h}\right)}{b_m\left(\mathit{h}\right)}=A_{n_K}^{\left(K\right)}\end{array}\\ \begin{array}{ccc}\frac{b_0\left(\mathit{h}\right)}{b_m\left(\mathit{h}\right)}=B_0& \cdots & \frac{b_{m-1}\left(\mathit{h}\right)}{b_m\left(\mathit{h}\right)}=B_{m-1}\end{array}\end{array}\end{array}$$E17

where A_i^(l) and B_j(i=0,…, n_l, j=0, …, m-1) are the coefficients of the fault diagnosis equations in (15) which have been calculated in the previous phase. The Jacobian matrix of this system coincides with the matrix E in (16), hence, all the information provided by a Jacobian matrix with respect to its corresponding nonlinear system can be obtained from the matrix E. In particular, if rank(E) is equal to the number of unknown parameters, the component values can be uniquely determined by solving the equations in (17) through the consideration of a set of measurements carried out on the test points. If the testability τ= rank(E) is less than the number of unknown parameters R, a locally unique solution can be determined only if R-τ components are considered not faulty.

The matrix E does not give only information about the global solvability degree of the fault diagnosis problem. In fact, by noting that each column is relevant to a specific element or parameter of the circuit and by considering the linearly dependent columns of E, other information can also be obtained. For example, if a column is linearly dependent with respect to another one, this means that a variation of the corresponding component provides a variation on the fault-equation coefficients, indistinguishable with respect to that produced by the variation of the component corresponding to the other column. This means that the two components are not testable and they constitute an ambiguity group of the second order. As an example two parallel connected resistors in a circuit where we cannot distinguish which one caused the fault. By extending this reasoning to groups of linearly dependent columns of E, ambiguity groups of a higher order can be found. Then, in summary, the following definition can be formulated.

Definition 1: A set of components constitutes an ambiguity group of order j if the corresponding columns of the testability matrix E are linearly dependent. In other words, the ambiguity groups of a circuit in which a certain test point set has been chosen can be determined by locating the linearly dependent columns of the testability matrix E. Furthermore, as was mentioned, an ambiguity group that does not contain other ambiguity groups is called canonical. Therefore, a canonical ambiguity group can be defined as follows.

Definition 2: A set of k components constitutes a canonical ambiguity group of order k if the corresponding k columns of the testability matrix E are linearly dependent and every subset of this group of columns is constituted by linearly independent columns. It is important to notice that with this definition, the order of the canonical ambiguity groups cannot be greater than the testability value plus one τ +1.

In most cases the canonical ambiguity groups have some components in common. By unifying these types of groups, another ambiguity group, corresponding again to linearly dependent columns of the matrix E is obtained. We define as global an ambiguity group of the following type.

Definition 3: A set of m components constitutes a global ambiguity group of order m if it is obtained by unifying canonical ambiguity groups having at least one element in common.

Obviously, a canonical ambiguity group which does not have components in common with any other canonical ambiguity group can be considered as a global ambiguity group. Finally, the columns of the matrix E that do not belong to any ambiguity group are linearly independent. We define these as surely testable a group of components of the following kind.

Definition 4: A set of n components whose corresponding columns of the testability matrix E do not belong to any ambiguity group constitutes a surely testable group of order n.

Obviously, the number of surely testable components cannot be greater than the testability value τ, that is, the rank of the matrix E.

With these definitions in mind, the optimum set of testable components can be determined as in [12].

3.2. Formulation of fault equations

Applying equation (1) to fault-free and faulty circuits, respectively, with the same excitation sources we get

$${\mathit{T}}_{\mathit{o}}{\mathit{X}}_{\mathit{o}}={\mathit{W}}_{\mathit{o}}$$E18

$$\mathit{T}\mathit{X}=\left({\mathit{T}}_{\mathit{o}}+∆\mathit{T}\right)\left({\mathit{X}}_{\mathit{o}}+∆\mathit{X}\right)={\mathit{W}}_{\mathit{o}}$$E19

where

$$\mathit{T}={\mathit{T}}_{\mathit{o}}+∆\mathit{T}$$E20

$$\mathit{X}={\mathit{X}}_{\mathit{o}}+∆\mathit{X}$$E21

It can be easily shown that

$$∆\mathit{T}\mathit{X}=-{\mathit{T}}_{\mathit{o}}∆\mathit{X}$$E22

where the parameter variation can be found from the measured values of the faulty circuit, the original system matrix and an estimate of the change of the system matrix due to fault presence

$$∆\mathit{X}=-{\mathit{T}}_0^{-1}∆\mathit{T}\mathit{X}$$E23

It is customary to solve equation (23) as a constrained linear optimization problem. However such an approach is limited by the solution time and ambiguity leading to local minimum convergence. Suppose that the first f of p parameters are faulty and are changed from their nominal values h₁₀, h₂₀, …., h_f0 to new values h₁=h₁₀+d₁, h₂=h₂₀+d₂, …., h_f =h_f0+d_f, where d₁, d₂, …., d_f are the parameter deviations and the deviation vector d is an f×1 vector:

$$\mathit{d}={[d_1\mathrm{ }{d}_2\mathrm{ }\cdots d_f]}^t$$E24

Define F as the faulty parameter set, and assume that each faulty parameter F_v ( v = 1, 2,..., f ) is located on intersection of the corresponding rows i_v and j_v and columns k_v and l_v of the coefficient matrix T. The deviation of the coefficient matrices now has the following form:

$$∆\mathit{T}=\sum _{v=1}^f{p}_v{d}_v{q}_v^t={\mathit{P}}_{\mathit{f}}diag\left(\mathit{d}\right){\mathit{Q}}_{\mathit{f}}^{\mathit{t}}$$E25

where diag (d) is an f×f diagonal matrix and P_f and Q_f are g×f matrices which contain 0 and ±1 entries:

$$\begin{array}{c}{\mathit{P}}_{\mathit{f}}=\left[{\mathit{p}}_1\mathrm{ }{\mathit{p}}_2\mathrm{ }\cdots \mathrm{ }{\mathit{p}}_{\mathit{f}}\right]=[{\mathit{\delta }}_{{\mathit{i}}_1}-{\mathit{\delta }}_{{\mathit{j}}_1}\mathrm{ }{\mathit{\delta }}_{{\mathit{i}}_2}-{\mathit{\delta }}_{{\mathit{j}}_2}\mathrm{ }\cdots \mathrm{ }{\mathit{\delta }}_{{\mathit{i}}_{\mathit{f}}}-{\mathit{\delta }}_{{\mathit{j}}_{\mathit{f}}}]\\ {\mathit{Q}}_{\mathit{f}}=\left[{\mathit{q}}_1\mathrm{ }{\mathit{q}}_2\mathrm{ }\cdots \mathrm{ }{\mathit{q}}_{\mathit{f}}\right]=[{\mathit{\delta }}_{{\mathit{k}}_1}-{\mathit{\delta }}_{{\mathit{l}}_1}\mathrm{ }{\mathit{\delta }}_{{\mathit{k}}_2}-{\mathit{\delta }}_{{\mathit{l}}_2}\mathrm{ }\cdots \mathrm{ }{\mathit{\delta }}_{{\mathit{k}}_{\mathit{f}}}-{\mathit{\delta }}_{{\mathit{l}}_{\mathit{f}}}]\end{array}$$E26

Note that P_f and Q_f are sub-matrices of P and Q respectively. They can be constructed from P and Q by selecting all columns in P and Q corresponding to faulty parameters. As an example assume that there are two faulty parameters: R₉ is changed from 3.54Ω to 7.9Ω and R₃₇ is changed from 3.12Ω to 2.8 Ω. The corresponding admittance deviations are ΔG₉= 1/7.9 - 1/3.54 = -0.1559 / Ω and ΔG₃₇=1/2.8 ̶ 2/3.12 = 0.03663 /Ω. The corresponding faulty parameter set F=[9,37] and the faulty nodes will be [1,14,16]. It can be easily verified that P_f and Q_f are 20×2-matrices which can be obtained from the 9^th and 37^th columns of the matrices P and Q respectively. It can also be verified that ΔT will have entries only at locations {1,1}, {14,14}, {14,16}, {16,14}, {16,16}.

Substituting (25) in (20) we get

$$\mathit{T}={\mathit{T}}_{\mathit{o}}+{\mathit{P}}_{\mathit{f}}diag\left(\mathit{d}\right){\mathit{Q}}_{\mathit{f}}^{\mathit{t}}$$E27

and to obtain the solution vector for the faulty circuit we use

$$\mathit{X}={\mathit{T}}^{-1}{\mathit{W}}_{\mathit{o}}$$E28

It can be shown using Woodbury formula that the value of d_v (v=1,2,..., f ) cannot be zero or infinity to meet with the requirement of inverting [6]. Since d_v being zero means fault-free parameter and only faulty parameters will be identified by following fault diagnosis algorithm, we will have only one restriction: d_v cannot be infinite, which corresponds to the case of open admittance or short impedance. But open or short faults can be dealt with by ideal switches introduced in modified nodal analysis [4]. Therefore, the proposed method can handle open and short faults as well but only if combined with a procedure that repeats the analysis of the circuit after introduction of ideal switches.

The solution vector for fault-free circuit is

$${\mathit{X}}_0={[x_{\mathrm{1,0}}\mathrm{ }{x}_{\mathrm{2,0}}\mathrm{ }\cdots x_{g,0}]}^t$$E29

where subscript 0 indicates that the denoted parameters are for fault-free circuit. Hence the product of Q_f^t and X_o can be written as

$$\begin{array}{c}{\mathit{Q}}_{\mathit{f}}^{\mathit{t}}{\mathit{X}}_0={\left[{\mathit{\delta }}_{{\mathit{k}}_1}-{\mathit{\delta }}_{{\mathit{l}}_1}\mathrm{ }{\mathit{\delta }}_{{\mathit{k}}_2}-{\mathit{\delta }}_{{\mathit{l}}_2}\mathrm{ }\cdots \mathrm{ }{\mathit{\delta }}_{{\mathit{k}}_{\mathit{f}}}-{\mathit{\delta }}_{{\mathit{l}}_{\mathit{f}}}\right]}^t{\mathit{X}}_0\\ ={\left[{\mathit{x}}_{{\mathit{k}}_1,0}-{\mathit{x}}_{{\mathit{l}}_1,0}\mathrm{ }{\mathit{x}}_{{\mathit{k}}_2,0}-{\mathit{x}}_{{\mathit{l}}_2,0}\mathrm{ }\cdots \mathrm{ }{\mathit{x}}_{{\mathit{k}}_{\mathit{f}},0}-{\mathit{x}}_{{\mathit{l}}_{\mathit{f}},0}\right]}^t\\ ={\left[{\mathit{x}}_{{\mathit{k}}_1{\mathit{l}}_1,0}\mathrm{ }{\mathit{x}}_{{\mathit{k}}_2{\mathit{l}}_2,0}\mathrm{ }\cdots \mathrm{ }{\mathit{x}}_{{\mathit{k}}_{\mathit{f}}{\mathit{l}}_{\mathit{f}},0}\right]}^t\end{array}$$E30

and it has the physical interpretation of controlling nominal signal values (e.g. voltages) on faulty parameter input terminals.

Let us define

$$\begin{array}{c}\mathit{\beta }={[{\mathit{\beta }}_1\mathrm{ }{\mathit{\beta }}_2\mathrm{ }\cdots \mathrm{ }{\mathit{\beta }}_{\mathit{n}}]}^t={\mathit{T}}_0^{-1}{\mathit{P}}_{\mathit{f}}\\ \mathit{\gamma }={\mathit{Q}}_{\mathit{f}}^{\mathit{t}}{\mathit{T}}_0^{-1}{\mathit{P}}_{\mathit{f}}={\mathit{Q}}_{\mathit{f}}^{\mathit{t}}\mathit{\beta }\end{array}$$E31

It can be shown that the deviation vector ΔX can be obtained by [6]

$$\begin{array}{c}∆X=-\beta {\left[diag\left(d^{-1}\right)+\gamma \right]}^{-1}{Q}_f^t{X}_0\\ =\left[\begin{array}{cc}\begin{array}{cc}{\alpha }_{11}& {\alpha }_{12}\\ {\alpha }_{21}& {\alpha }_{22}\end{array}& \begin{array}{cc}\cdots & {\alpha }_{1f}\\ \cdots & {\alpha }_{2f}\end{array}\\ \begin{array}{cc}⋮& ⋮\\ {\alpha }_{g1}& {\alpha }_{g2}\end{array}& \begin{array}{cc}\cdots & ⋮\\ \cdots & {\alpha }_{gf}\end{array}\end{array}\right]\left[\begin{array}{c}\begin{array}{c}{x}_{k_1{l}_1,0}\\ x_{k_2{l}_2,0}\end{array}\\ \begin{array}{c}⋮\\ x_{k_f{l}_f,0}\end{array}\end{array}\right]\end{array}$$E32

where

$$\begin{array}{c}\alpha =-\beta {\left[diag\left(d^{-1}\right)+\gamma \right]}^{-1}\\ =\left[\begin{array}{cc}\begin{array}{cc}{\alpha }_{11}& {\alpha }_{12}\\ {\alpha }_{21}& {\alpha }_{22}\end{array}& \begin{array}{cc}\cdots & {\alpha }_{1f}\\ \cdots & {\alpha }_{2f}\end{array}\\ \begin{array}{cc}⋮& ⋮\\ {\alpha }_{g1}& {\alpha }_{g2}\end{array}& \begin{array}{cc}\cdots & ⋮\\ \cdots & {\alpha }_{gf}\end{array}\end{array}\right]=\left[\begin{array}{c}\begin{array}{c}{\alpha }_1\\ {\alpha }_2\end{array}\\ \begin{array}{c}⋮\\ {\alpha }_g\end{array}\end{array}\right]\end{array}$$E33

Usually voltage measurement is easier to carry out and is less invasive to analog circuit properties than current measurement. Therefore, we only consider the use of nodal voltage measurement in this formulation. As an example γ for our example circuit of Figure 1 assuming the aforementioned faults will be given by

$$\mathit{\gamma }=\left[\begin{array}{cc}2.4475& 0.0145\\ 0.0145& 2.5120\end{array}\right]$$E34

Once we have the fault equations formulated and the faults simulated we can proceed to fault diagnosis.

3.3. Fault diagnosis

During the fault diagnosis we have the CUT with only a limited set of accessible nodes for measurement and excitation. Suppose the i^th node is accessible for measurement, then by equation (32)

$$∆{\mathit{X}}_{\mathit{i}}=\left[\begin{array}{cc}\begin{array}{cc}{\alpha }_{i1}& {\alpha }_{i2}\end{array}& \begin{array}{cc}\cdots & {\alpha }_{if}\end{array}\end{array}\right]{\left[{\mathit{x}}_{{\mathit{k}}_1{\mathit{l}}_1,0}\mathrm{ }{\mathit{x}}_{{\mathit{k}}_2{\mathit{l}}_2,0}\mathrm{ }\cdots \mathrm{ }{\mathit{x}}_{{\mathit{k}}_{\mathit{f}}{\mathit{l}}_{\mathit{f}},0}\right]}^t$$E35

According to definition of g×f matrix α in equations (33) and (31), matrix α does not depend on the location of excitation sources. Thus matrix α is invariant when applying the multiple excitation method, i.e., the same coefficients α_ij links deviation of measurements ΔX_i and nominal signal values on faulty parameter ${\mathit{x}}_{{\mathit{k}}_{\mathit{j}}{\mathit{l}}_{\mathit{j}}}$ independent of the excitation vector applied. After measuring the corresponding nodal voltages on the i^th node with m independent excitation vectors We (e = 1, 2,..., m ), we then obtain

$$\begin{array}{c}{∆{\mathit{X}}_{\mathit{i}}}^{\left(1\right)}=\left[\begin{array}{cc}\begin{array}{cc}{\alpha }_{i1}& {\alpha }_{i2}\end{array}& \begin{array}{cc}\cdots & {\alpha }_{if}\end{array}\end{array}\right]{\left[{\mathit{x}}_{{\mathit{k}}_1{\mathit{l}}_1,0}^{\left(1\right)}\mathrm{ }{\mathit{x}}_{{\mathit{k}}_2{\mathit{l}}_2,0}^{\left(1\right)}\mathrm{ }\cdots \mathrm{ }{\mathit{x}}_{{\mathit{k}}_{\mathit{f}}{\mathit{l}}_{\mathit{f}},0}^{\left(1\right)}\right]}^t\\ {∆{\mathit{X}}_{\mathit{i}}}^{\left(2\right)}=\left[\begin{array}{cc}\begin{array}{cc}{\alpha }_{i1}& {\alpha }_{i2}\end{array}& \begin{array}{cc}\cdots & {\alpha }_{if}\end{array}\end{array}\right]{\left[{\mathit{x}}_{{\mathit{k}}_1{\mathit{l}}_1,0}^{\left(2\right)}\mathrm{ }{\mathit{x}}_{{\mathit{k}}_2{\mathit{l}}_2,0}^{\left(2\right)}\mathrm{ }\cdots \mathrm{ }{\mathit{x}}_{{\mathit{k}}_{\mathit{f}}{\mathit{l}}_{\mathit{f}},0}^{\left(2\right)}\right]}^t\\ \begin{array}{c}⋮\\ {∆{\mathit{X}}_{\mathit{i}}}^{\left(m\right)}=\left[\begin{array}{cc}\begin{array}{cc}{\alpha }_{i1}& {\alpha }_{i2}\end{array}& \begin{array}{cc}\cdots & {\alpha }_{if}\end{array}\end{array}\right]{\left[{\mathit{x}}_{{\mathit{k}}_1{\mathit{l}}_1,0}^{\left(m\right)}\mathrm{ }{\mathit{x}}_{{\mathit{k}}_2{\mathit{l}}_2,0}^{\left(m\right)}\mathrm{ }\cdots \mathrm{ }{\mathit{x}}_{{\mathit{k}}_{\mathit{f}}{\mathit{l}}_{\mathit{f}},0}^{\left(m\right)}\right]}^t\end{array}\end{array}$$E36

or in matrix form

$$\begin{array}{c}{∆X_i}^M=\left[\begin{array}{c}\begin{array}{c}{∆X_i}^{\left(1\right)}\\ {∆X_i}^{\left(2\right)}\end{array}\\ \begin{array}{c}⋮\\ {∆X_i}^{\left(m\right)}\end{array}\end{array}\right]=\left[\begin{array}{c}\begin{array}{c}{x}_{k_1{l}_1,0}^{\left(1\right)}{x}_{k_2{l}_2,0}^{\left(1\right)} \cdots x_{k_f{l}_f,0}^{\left(1\right)}\\ x_{k_1{l}_1,0}^{\left(2\right)}{x}_{k_2{l}_2,0}^{\left(2\right)} \cdots x_{k_f{l}_f,0}^{\left(2\right)}\end{array}\\ \begin{array}{c}⋮\\ x_{k_1{l}_1,0}^{\left(m\right)}{x}_{k_2{l}_2,0}^{\left(m\right)} \cdots x_{k_f{l}_f,0}^{\left(m\right)}\end{array}\end{array}\right]\left[\begin{array}{c}\begin{array}{c}{\alpha }_{i1}\\ {\alpha }_{i2}\end{array}\\ \begin{array}{c}⋮\\ {\alpha }_{if}\end{array}\end{array}\right]\\ ={X_b}^{MF}{\alpha }_i\end{array}$$E37

where superscript M denotes the set of multiple excitations and m is the number of these excitations. The single measurement node can be one of the nodes used for multiple excitation method, and then the total number of accessible excitation nodes should be m. Assume that f ≤ m-1 ≤ p, then the coefficient matrix Xb^MF has more rows than columns thus guaranteeing the uniqueness of the solution to equation (37) with verification. Equation (37) establishes the linear relationship between the measured responses of the faulty circuit ΔX_i^M and the faulty parameter deviations d since vector α_i is a linear functions of d according to equation (33). Therefore equation (37) is called the fault diagnosis equation, and the coefficient matrix Xb^MF is called the fault diagnosis matrix [6].

As said earlier, with only a limited number of accessible nodes the issue of testability and consistency of the selected set of accessible nodes to detect f number of simultaneous faults immediately arises. However, testability is not the focus of this chapter. We assume that the given measurement set can give at least one finite solution to circuit parameters.

As the first stage of fault diagnosis, fault detection is easily implemented. If the measurement deviation vector ΔX_i^M in the fault diagnosis equation is a zero vector, obviously the CUT is judged as fault-free for the given excitation and measurement sets. Otherwise, at least one fault is judged detected by the given measurement set. To identify the faulty parameters, first let us analyze the fault diagnosis equation. The left-side of equation (37) is a known vector from measurements; the right side is the product of an unknown coefficient matrix Xb^MF and an unknown solution vector α_i. According to equation (30), matrix Xb^MF is determined by faulty parameter locations and X₀, solution vector for the fault-free circuit. Hence the columns in Xb^MF represent the differences between the nominal values of nodal voltages or parameter currents across the 2 input nodes of the faulty parameters. Although we do not know matrix Xb^MF initially for the CUT since we do not know initially the location or number of faults, but we really know all of the nodal voltages and parameter currents in the fault-free circuit!

Similarly as in equation (30), we can construct a new m×p matrix Xb^MP as follows

$$\begin{array}{c}{{\mathit{Q}}^{\mathit{t}}\mathit{X}}_0={\left[{\mathit{\delta }}_{{\mathit{k}}_1}-{\mathit{\delta }}_{{\mathit{l}}_1}\mathrm{ }{\mathit{\delta }}_{{\mathit{k}}_2}-{\mathit{\delta }}_{{\mathit{l}}_2}\mathrm{ }\cdots \mathrm{ }{\mathit{\delta }}_{{\mathit{k}}_{\mathit{p}}}-{\mathit{\delta }}_{{\mathit{l}}_{\mathit{p}}}\right]}^t{\mathit{X}}_0\\ ={\left[{\mathit{x}}_{{\mathit{k}}_1,0}-{\mathit{x}}_{{\mathit{l}}_1,0}\mathrm{ }{\mathit{x}}_{{\mathit{k}}_2,0}-{\mathit{x}}_{{\mathit{l}}_2,0}\mathrm{ }\cdots \mathrm{ }{\mathit{x}}_{{\mathit{k}}_{\mathit{p}},0}-{\mathit{x}}_{{\mathit{l}}_{\mathit{p}},0}\right]}^t\\ ={\left[{\mathit{x}}_{{\mathit{k}}_1{\mathit{l}}_1,0}\mathrm{ }{\mathit{x}}_{{\mathit{k}}_2{\mathit{l}}_2,0}\mathrm{ }\cdots \mathrm{ }{\mathit{x}}_{{\mathit{k}}_{\mathit{p}}{\mathit{l}}_{\mathit{p}},0}\right]}^t\end{array}$$E38

$${X_b}^{MP}=\left[\begin{array}{c}\begin{array}{c}{x}_{k_1{l}_1,0}^{\left(1\right)}{x}_{k_2{l}_2,0}^{\left(1\right)} \cdots x_{k_p{l}_p,0}^{\left(1\right)}\\ x_{k_1{l}_1,0}^{\left(2\right)}{x}_{k_2{l}_2,0}^{\left(2\right)} \cdots x_{k_p{l}_p,0}^{\left(2\right)}\end{array}\\ \begin{array}{c}⋮\\ x_{k_1{l}_1,0}^{\left(m\right)}{x}_{k_2{l}_2,0}^{\left(m\right)} \cdots x_{k_p{l}_p,0}^{\left(m\right)}\end{array}\end{array}\right]$$E39

where superscript P denotes the set of all p circuit parameters. Each column of Xb^MP corresponds to one circuit parameter. Evidently, the fault diagnosis matrix Xb^MF is a sub-matrix of Xb^MP and can be constructed by collecting all columns in Xb^MP corresponding to the faulty parameters. Apparently matrix Xb^MF has more rows than columns whereas Xb^MP has less rows than columns due to the restriction f ≤ m-1 ≤ p.

For the purpose of fault identification, we need to find out which set or sets of columns in Xb^MP can satisfy the fault diagnosis equation, i.e. the dependency between ΔX_i^M and the desired coefficient matrix in fault diagnosis matrix.

Basically ΔX_i^M vector for all p parameters has to be generated from the fault-free circuit and stored as a dictionary of fault-free response to m multiple excitations over the designated m accessible nodes. This dictionary will be used later to determine whether the CUT is faulty and will be used in locating the faults. It must be emphasized that only one node for voltage measurement is sufficient for this method although multiple linearly-independent excitations are required across all m accessible nodes for successful fault location. It is thus possible to use only one of the accessible m nodes to carry out the measurements while using the rest to carry out the excitations. As an example node {2} in Figure1 is selected as the only measurement node, while nodes {2, 4, 15, 16, 17} are selected as accessible nodes for the multiple excitations. That is the unit current source is applied to these nodes respectively and the corresponding nodal voltage at node {2} is measured. Thus the measured changes of nodal voltage will be

$${∆X}^M=\left[\begin{array}{c}0.89005\\ 0.91400\\ \begin{array}{c}0.03651\\ 0.032306\\ 0.038445\end{array}\end{array}\right]$$E40

One obvious way is to have a combinatorial search through all columns in Xb^MP, which is the traditional way in the fault verification method [15] and requires a number of operations of the order $O\left(\sum _{i=1}^f\left(\begin{array}{c}p\\ i\end{array}\right)\right)$ for f limited faults among p parameters. This is equivalent to assuming that any number of faults up to f simultaneous faults have occurred randomly in any subset of the p parameters then evaluate the response to such faults and compare it to the measured response. However, the method being described here is more efficient than that and involves locating the minimum size ambiguity group which satisfies the fault diagnosis equation. An ambiguity group is defined as a set of parameters corresponding to linearly dependent columns of Xb^MP which in general does not give a unique solution in fault identification. Minimum size ambiguity groups (called canonical ambiguity groups) can be found using a linear combination matrix with minimum number of non-zero entries as will be shown shortly. But to generate this we need to perform a Gaussian elimination step.

3.3.1. Gaussian eliminaion step

Let us first denote an augmented m×(p+1) matrix B_S as the concatenation of the stored dictionary vector ΔX_i^M and the matrix Xb^MP:

$${\mathit{B}}_{\mathit{S}}=\left[\begin{array}{cc}{∆{\mathit{X}}_{\mathit{i}}}^M& {{\mathit{X}}_{\mathit{b}}}^{MP}\end{array}\right]$$E41

Then we will normalize the first column of matrix B_S to have a unity in its first row,

$${\widehat{\mathit{B}}}_{\mathit{S}}\left(i,1\right)=\frac{{\mathit{B}}_{\mathit{S}}\left(i,1\right)}{{\mathit{B}}_{\mathit{S}}\left(\mathrm{1,1}\right)},\mathrm{ } i=1,\mathrm{ }2,\mathrm{ }\cdots ,\mathrm{ }m.$$E42

If the first entry of matrix B_S, B_S(1,1) happens to be zero, just permute or swap the rows of B_S so that the first entry B_S(1,1) is non-zero. Such a nonzero entry must exist since ΔX_i^M is a non-zero vector for faulty circuit. Eliminate the remaining entries in the first row of matrix B_S by performing a similar operation to Gaussian elimination as follows:

$${\widehat{\mathit{B}}}_{\mathit{S}}\left(i,j\right)={\mathit{B}}_{\mathit{S}}\left(i,j\right)-\frac{{\mathit{B}}_{\mathit{S}}\left(i,1\right)}{{\mathit{B}}_{\mathit{S}}\left(\mathrm{1,1}\right)}{\mathit{B}}_{\mathit{S}}\left(1,j\right),\mathrm{ } i=1,\mathrm{ }2,\mathrm{ }\cdots ,\mathrm{ }m;j=\mathrm{2,3},\cdots ,\mathrm{ }p+1.$$E43

Finally we obtain m×(p+1) matrix ${\widehat{\mathit{B}}}_{\mathit{S}}$ in the following form:

$${\widehat{\mathit{B}}}_{\mathit{S}}=\left[\begin{array}{cc}{1}^{1\times 1}& 0^{1\times p}\\ {\left(∆{\widehat{\mathit{X}}}_{\mathit{i}}\right)}^{\left(m-1\right)\times 1}& {\mathit{B}}^{\left(m-1\right)\times p}\end{array}\right]$$E44

where the superscript represents the size of a vector or a matrix. Matrix B is obtained from Xb^MP after elimination of dependence on ΔX_i^M and is called the verification matrix [6]. The dependency of the desired columns of matrix B surely indicates the dependency between ΔX_i^M and the desired columns of matrix Xb^MP. Thus we can only concentrate on the dependency among the columns of the verification matrix B.

3.3.2. QR factorization

The rank r of the matrix B determines a maximum number of faults that can be uniquely identified by solving the fault diagnosis equation. Because m-1<p, B can be permuted column wise and decomposed into two linearly dependent sub-matrices as follows

$$perm\left(\mathit{B}\right)=\left[\begin{array}{cc}{\mathit{B}}_1& {\mathit{B}}_2\end{array}\right]={\mathit{B}}_1\left[\begin{array}{cc}\mathit{I}& \mathit{C}\end{array}\right]$$E45

$${\mathit{B}}_2={\mathit{B}}_1\mathit{C}$$E46

where perm refers to column-wise permutation, (m-1)×r matrix B₁ has the full column rank equal to the rank r of the matrix B, and r ×( p − r) matrix C is called linear combination matrix whose columns expand a set of basis columns from B₁ into the corresponding columns of B₂. It can be easily shown that B₁ is a sub-matrix of B with all the rows and only a subset of the columns (called the basis set) while B₂ is a sub-matrix of B with all the rows and the remaining set of the columns (called the co-basis set). Note that the selection of independent columns of B₁ is not unique and is an important issue in solving the fault diagnosis equation in the presence of ambiguities. Different partitions define different linear combination matrices C.

Since an ambiguity group is a set of circuit parameters corresponding to linearly dependent columns of B, we define a canonical ambiguity group as a minimal set of parameters corresponding to linearly dependent columns of B. This means that if any single parameter is removed from the canonical ambiguity group, then the remaining set corresponds to independent columns of B and can be uniquely solvable. A combination of canonical ambiguity groups with at least one common element was defined as ambiguity cluster.

To efficiently deal with fault verification problem, we will look for a partition (45) with the matrix C in a minimum form, which is defined as such a matrix that one or several of its columns have the maximum number of entries equal to zero. Thus, we can get the minimum number of columns in Xb^MP satisfying the fault diagnosis equation (37). The corresponding partition (45) is called a canonical form of the fault diagnosis equation. Notice that according to fault verification principles [15] it is enough to find a single entry in one column of C equal to zero to solve the fault diagnosis equation. Yet since many such solutions exist we will select the column with the maximum number of zeros assuming that the faulty response was caused by the smallest number of faults. This column and all rows with non-zero entries will correspond to the faulty parameters as indicated by the element of co-basis B₂ and elements of basis B₁, respectively.

One way to find these matrices from the matrix B with high numerical stability is based on QR factorization [8], which can find a solution of over determined system of linear equations that minimizes the least square error. As a result of the QR factorization of (m-1)×p verification matrix B, we obtain:

$$\mathit{B}\mathit{E}=\mathit{Q}\mathit{R}$$E47

where E is p×p column selection matrix, Q is (m-1)×(m-1) orthogonal matrix, and R is (m-1)×p upper triangular matrix. Each column of matrix E has only one nonzero entry, which is equal to one. Matrix product BE represents the permutation of the original columns of the verification matrix B requested in equation (45). Matrix R has its rank equal to the rank of matrix B. Since R is an upper triangular matrix and m-1<p, R can be written as

$$\mathit{R}=\left[\begin{array}{cc}{\mathit{R}}_1& {\mathit{R}}_2\end{array}\right]$$E48

where R₁ is r×r upper triangular and has its rank equal to the rank of the verification matrix B. Having this factorization computed, it can be shown that [8]

$$perm\left(\mathit{B}\right)=\mathit{B}\mathit{E}$$E49

$$\mathit{C}={{\mathit{R}}_1}^{-1}{\mathit{R}}_2$$E50

$${\mathit{B}}_1=\mathit{Q}{\mathit{R}}_1$$E51

Furthermore the basis set will be the row values of the non-zero elements in the first r columns of E while the co-basis will be the row values of the remaining p-r columns of E. As an example, the values of R₁ for our example circuit of Figure 1 is

$${\mathit{R}}_1=\left[\begin{array}{cc}\begin{array}{cc}10.5475& -2.9444\\ 0& 3.5435\end{array}& \begin{array}{cc}0.0028& 2.3965\\ -0.0014& -2.8011\end{array}\\ \begin{array}{cc}0& \mathrm{ } 0\\ 0& \mathrm{ } 0\end{array}& \begin{array}{cc}2.4161& -0.0005\\ 0& \mathrm{ } 1.7202\end{array}\end{array}\right]$$E52

The column permutation is {39, 15, 2, 35, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 3, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 4, 36, 37, 38, 1}. Thus the basis is {39, 15, 2, 35} and co-basis is {5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 3, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 4, 36, 37, 38, 1}.

3.3.3. Swapping performance

A single QR run cannot guarantee that the matrix C will be obtained with one or several of its columns having the maximum number of zero entries if the proper basis is not selected. To find the minimum form partition, we have to swap one parameter of the basis with one parameter of the co-basis in the ambiguity cluster in order to increase number of nonzero entries in C. Note that swapping parameters of the basis and the co-basis can be performed independently in different ambiguity clusters, since different clusters have mutually disjoint sets of parameters. There are simply two conditions to consider in swapping performance:

1. The necessary condition for swapping to increase the number of zero entries in C is that the columns of basis and co-basis to be swapped have a singular 2×2 sub-matrix of nonzero entries.

Let us consider a linear combination matrix C with a 2×2 singular sub-matrix

$$R_1=\left[\begin{array}{cc}\begin{array}{cc}10.5475& -2.9444\\ 0& 3.5435\end{array}& \begin{array}{cc}0.0028& 2.3965\\ -0.0014& -2.8011\end{array}\\ \begin{array}{cc}0& 0\\ 0& 0\end{array}& \begin{array}{cc}2.4161& -0.0005\\ 0& 1.7202\end{array}\end{array}\right]$$E53

with all nonzero entries. If we swap the j^th element of the basis with k^th element of the co-basis, then after swapping, the k^th column of C changes to

$${\mathit{C}}_{\mathit{k}}=-\frac{1}{c_{jk}}{\left[\begin{array}{cc}\begin{array}{ccc}{c}_{1k}& c_{2k}& \cdots \end{array}& \begin{array}{ccc}1& \cdots & c_{rk}\end{array}\end{array}\right]}^t$$E54

In addition, all other columns of matrix C will be equal to

$${\mathit{C}}_{\mathit{n}}={\left[\begin{array}{cc}\begin{array}{ccc}{c}_{1n}-\frac{c_{jn}{c}_{1k}}{c_{ik}}& c_{2n}-\frac{c_{jn}{c}_{2k}}{c_{ik}}& \cdots \end{array}& \begin{array}{ccc}\frac{c_{jn}}{c_{ik}}& \cdots & c_{rn}-\frac{c_{jn}{c}_{rk}}{c_{ik}}\end{array}\end{array}\right]}^t$$E55

Such that all zero locations in the k^th column of C will be zero as they were in the original C. However, as can be deducted from (53), a nonzero location c_im in row i and column m will become zero. It is understood that if one element in the current basis has been swapped into the basis by the previous swapping performance, then this element will not be considered during the later swapping.

Any columns of C with zero entries form an ambiguity group F and has to be considered for further processing. Since ambiguities may exist in the original matrix Xb^MP then F contains all faults in the CUT only if the corresponding columns in Xb^MP are independent. Hence we must consider the following condition

1. The necessary condition for an ambiguity group F of the linear combination matrix C to contain the set of all faults in the tested circuit is that the rank of the corresponding columns in matrix X_b^MP is equal to the cardinality of F

$$rank\left({{\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{m}\mathrm{n}\mathrm{s}\mathrm{ }\mathrm{i}\mathrm{n}\mathrm{ }\mathit{X}}_{\mathit{b}}}^{MP}\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{p}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{ }\mathrm{t}\mathrm{o}\mathrm{ }F\right)=card\left(F\right)$$E56

Thus according to this condition any ambiguity group of the verification matrix which do satisfy (55) needs to be further analyzed. The stopping criterion for the above procedure can simply be τ the testability measure found from the symbolic analysis.

As an example for our circuit of Figure 1, careful study of the generated C matrix reveals multiple zero entry at columns 5,12, 32, 33, and 34 (corresponding to nodes {9}, {16}, {36}, {37}, and {38} from the co-basis). The non-zero row entries will either be on rows 1, 2, 4 (corresponding to nodes {39}, {15} and {35} from the basis) or on rows 2, 3, and 4 (corresponding to nodes {15}, {2} and {35}). Thus the corresponding ambiguity clusters include {39, 15, 9, 35}, {16, 15, 2, 35}, {39, 15, 36, 35}, {39, 15, 37, 35}, and {39, 15, 38, 35}. Yet none of these ambiguity clusters satisfies condition (b) except for the first one. Accordingly only one suspicious faulty group F={39, 15, 35, 9} is qualified with parameter {9} from the co-basis and parameters {39, 15, 35} from the basis. The current minimum size of qualified F is 4.

Searching for the 2×2 singular matrix with non-zero entries in C reveals that parameter {9} from the co-basis should be swapped with the parameter {39} from the basis according to the swapping procedure in condition (a), and a new matrix C results. Re-applying condition (b) to the new matrix C, 5 qualified suspicious faulty groups are obtained: F={9, 2, 35, 5}, F={9, 15, 35, 39}, F={9, 15, 35, 36}, F={9, 15, 38} and F={9, 37}. Obviously, F={9, 37} is the unique solution with the minimum size equal to 2. Since no smaller size of faulty set F can be found by swapping, thus F={9, 37} is the only solution located by the procedure of fault diagnosis which is the exact solution for the given CUT.

Once the fault locations are determined the fault values must be evaluated and compared with the element tolerances before giving a final judgment on the circuit whether being faulty or not.

3.3.4. Parameter evaluation

After locating the faulty parameters, the matrix Xb^MF can be found from the matrix Xb^MP by taking only the columns corresponding to the fault locations. Then the invariant vector α_i can be uniquely solved from equation (37)

$${\mathit{\alpha }}_{\mathit{i}}={\left({\left({{\mathit{X}}_{\mathit{b}}}^{MF}\right)}^{\mathit{t}}{{\mathit{X}}_{\mathit{b}}}^{MF}\right)}^{-1}{\left({{\mathit{X}}_{\mathit{b}}}^{MF}\right)}^{\mathit{t}}{∆{\mathit{X}}_{\mathit{i}}}^M$$E57

where this form is used since the system is over-determined with Xb^MF being non-square. Finally the deviation vector d can be exactly computed by

$$\mathit{d}={\mathit{\alpha }}_{\mathit{i}}\mathrm{ }./\mathrm{ }\left(\mathit{\beta }-{\mathit{\alpha }}_{\mathit{i}}\mathit{\gamma }\right)$$E58

where. / is an element-by-element division of two vectors. What remains after evaluating the deviations is to compare them to the element allowable tolerances to decide finally whether the measured CUT performance is still considered acceptable or deemed faulty. Basically, when the fault locations and parameter deviations are found, all the circuit can be re-solved to get all the node voltages and element currents of the CUT.

3.4. Mixed symbolic numerical algorithm for fault diagnosis

A computer program which implements the fault diagnosis discussed above can be easily advised. In Phase 1, a topological description of the circuit is obtained and the circuit is solved numerically. Since nominal values of circuit parameters are known, all nodal voltages in fault-free circuit can be solved by (18). In phase 2, an upper limit for the testability τ needs to be determined for the provided set of accessible nodes. It is not generally required to obtain a fully symbolic solution of the circuit and only a partial symbolic solution would be sufficient. In phase 3 we need to measure the nodal voltages of the i^th node in the CUT under multiple excitation method to obtain measurement deviation vector ΔX_i^M. In phase 4 we need to generate the fault locator matrix Xb^MP from equations (38) and (39) then use it to find the linear combination matrix C after the Gaussian elimination step and the QR factorization. In Phase 5, analysis of the combination matrix is done where F denotes one suspicious fault set and min(size(F)) represents a scalar which is equal to the minimum size of all suspicious fault sets. In Phase 6, if several suspicious fault sets have the same minimum size, min(size(F)), select one of them arbitrarily for analysis. Only one parameter in the selected F is from the co-basis and the remaining parameters are from the basis. Swap that co-basis parameter which corresponds to column k in matrix C with one of basis parameters which corresponds to row j in the matrix C. By (53) and (54), all zero entries in the column k of matrix C will be held after swapping while new zero-entry will appear in another column of new matrix C, thus the new value of min(size(F)) will be equal to, or less than the old value before swapping.

There are two rules for swapping. One is that row j is selected with nonzero c_jk on the intersection of row j and column k of matrix C. Another rule is that if one parameter in the current basis has been swapped into the basis by the previous swapping operation, then this element will not be considered during the later swapping operation. Usually m-1 is far less than p, and the rank of r×(p-r) matrix C, r is not greater than m-1, thus there are far less basis parameters than co-basis parameters. The comprehensive swapping between the co-basis parameter k and the basis parameters are very limited, as a result of the two swapping principles.

In Phase 7 equivalent adjoint suspicious fault sets are recorded. In Phase 8 the corresponding fault diagnosis matrices Xb^MF are found from the fault locator matrix. In Phase 9 the invariant vector α_i is evaluated. Phase 10 is used for verification. One or several suspicious fault sets with minimum size are used to compute the deviation vector ΔX. If a computed vector matches the real measured vector ΔX_i^M, the corresponding fault set F is our final solution to faulty parameters. Otherwise, we discard this set, and turn to the adjoint suspicious fault sets recorded in Phase 7. Verification in this phase continues until at least one qualified solution to faulty parameters is found. Otherwise, the CUT is concluded as un-solvable because the restriction f ≤ m - 1 is not satisfied. In the final Phase the parameter variations are compared to the element tolerances to decide if the circuit response is indeed faulty or just shifted within the accepted tolerance.

4. Conclusion

In this chapter, a generalized fault diagnosis and verification approach for linear analog circuits was discussed. Fault verification methods intend to obtain the information about the faulty circuit based on the limited measured responses of the faulty circuit. There are two easily implemented prerequisites: one is that the circuit topology and nominal values of circuit parameters should be known, another is that the number of measurements minus one is not less than the number of faulty parameters. A symbolic method is proposed to solve the testability problem during the detection, and location of the multiple faults in a linear analog circuit in frequency domain, then to exactly evaluate the faulty parameter deviations.

Applying the Woodbury formula in the matrix theory to the modified nodal analysis, fault diagnosis equation is constructed to establish the relationship between the measured responses and the faulty parameter deviations in a linear way. A numerically robust approach has been modified to fit the condition stated in this chapter in order to implement fault location, i.e., location of the minimum size ambiguity group in the fault diagnosis equation based on QR factorization. Parameter evaluation is then performed from results of the analysis of fault diagnosis equation.

One node for voltage measurement is sufficient for the proposed method although multiple excitations are required for fault location. Although the faulty parameter deviation cannot be infinity, open or short condition can be dealt with well by switches in modified nodal analysis.

Therefore, the faults can be parametric or catastrophic. The proposed method is extremely effective for large parameter deviations and a very limited number of accessible nodes used for excitations and measurements. The computation cost for the fault location is on the order of O(p³), and compares favorably with the combinatorial search traditionally used in fault verification methods which requires the number of operations $O\left(\sum _{i=1}^f\left(\begin{array}{c}p\\ i\end{array}\right)\right)$.