# Entropy Based Test Point Evaluation and Selection Method for Analog Circuit Fault Diagnosis

Authors: Yuan Gao; Chenglin Yang; Shulin Tian; Fang Chen
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

By simplifying tolerance problem and treating faulty voltages on different test points as independent variables, integer-coded table technique is proposed to simplify the test point selection process. Usually, simplifying tolerance problem may induce a wrong solution while the independence assumption will result in over conservative result. To address these problems, the tolerance problem is thoroughly considered in this paper, and dependency relationship between different test points is considered at the same time. A heuristic graph search method is proposed to facilitate the test point selection process. First, the information theoretic concept of entropy is used to evaluate the optimality of test point. The entropy is calculated by using the ambiguous sets and faulty voltage distribution, determined by component tolerance. Second, the selected optimal test point is used to expand current graph node by using dependence relationship between the test point and graph node. Simulated results indicate that the proposed method more accurately finds the optimal set of test points than other methods; therefore, it is a good solution to minimize the size of the test point set. To simplify and clarify the proposed method, only catastrophic and some specific parametric faults are discussed in this paper.


---

## Body

## 1. Introduction

Among various fault diagnosis methods, fault dictionary method is still the most widely used SBT method [1–5]. The fault dictionary approach consists of three important phases [5], that is, fault dictionary construction, test points selection, and fault isolation. In the first phase, the adopted fault model, such as catastrophic fault, parametric fault, or slope based model [6], should be determined. In the second phase, the optimum test point, test stimuli, and/or measurement set is required to achieve the desired degree of fault diagnosis. Modern densely loaded circuit boards have posed problems for fault diagnosis with in-circuit testers because only limited physical access to the boards is allowed. Minimum set of test points selection method is, therefore, badly needed to reduce the number of test point. This paper focus on the test points selection method, which, applicable to catastrophic fault, discretized parametric fault and slope based model (continuous parametric fault model). To simplify the problem and clarify the proposed method, only catastrophic and some specific parametric faults are discussed in this paper.The problem of test points, test stimulus, and/or measurements selection for the analog fault dictionary technique has been studied extensively [4, 5, 7–21]. An entropy-based approach was proposed by Starzyk et al. [4]. Two broad test points selection categories, that is, inclusion and exclusion methods, are summarized by Prasad and Babu [5]. Varghese et al. [7] proposed a heuristic method for test points selection based on the concept of confidence levels determined by distance concepts. Stenbakken and Souders proposed a method of QR factorization of circuit sensitivity matrix [8]. Abderrahman et al. [9] used sequential quadratic programming and constraint logic programming to generate the test set. van Spaandonk and Kevenaar [10] proposed to look for a set of test points by combining the decomposition method of system sensitivity matrix and an iterative algorithm. Prasad and Babu [5] proposed four algorithms for inclusive approaches and three strategies for exclusive approaches. Based on fault detection table and computing the information content of every node, Pinjala and Kim [11] proposed an approach to get the near-minimum test sets. Golonek and Rutkowski [14] proposed a Genetic-Algorithm-Based test points selection method. Yang et al. [15, 16] transformed the test point selection problem into a graph search problem and made use of information theoretic entropy to guide graph search. Lei and Qin [18] use the quantum-inspired evolutionary algorithm to solve the test point selection problem. Different from the traditional integer-coded table technique, faulty voltage distribution is considered in literature [19]. Under the expert system control, heuristic test points selection algorithm proposed by Pulka [20]. The application of discrete particle swarm optimization algorithm to test point selection is discussed in [21].Most of the mentioned test points selection methods [4, 5, 11, 12, 14–16, 18–21] use the concept of ambiguous set defined by Hochwald and Bastian [1]. At any given node, numerous faulty conditions may give rise to voltage values close to each other and hence it may not be possible to clearly identify the specific faulty condition that has caused a particular voltage value. In such situation, the faulty conditions fall into the same ambiguous set. If tolerances are also taken into account, the voltage value of a node for a given faulty condition can be anywhere within a range depending upon the exact values of the components.In many literatures [4, 5, 11, 12, 14–16, 18–21], the ambiguous range is predefined as 0.7 volts. In the present era of low voltage analog circuits, the 0.7-volt criterion seems to be excessive. In some literatures, 0.2-volt gap is supposedly enough to distinguish two faults [22, 23]. V
th is used to represent the volts gap. Assume that Figure 1 shows faulty (including fault free) voltage values of a network. On test point t
1, the voltage gap |
V
1
b
-
V
1
a
| produced by faults s
0 and s
1 is smaller than V
th. Hence, they belong to one ambiguous set {
s
0
,
s
1
}. Similarly, s
2, s
3, and s
4 fall into another ambiguous set {
s
2
,
s
3
,
s
4
}. The voltage gap produced by any two faults from different ambiguous sets must be larger than V
th. In this example, |
V
1
c
-
V
1
b
|
>
V
th. There are two ambiguity sets, that is, {
s
0
,
s
2
} and {
s
1
,
s
3
,
s
4
} on test point t
2. Hence, faults are grouped into four ambiguity sets {
s
0
}, {
s
1
}, {
s
2
}, and {
s
3
,
s
4
} by t
1 and t
2 together.Figure 1
Ambiguous set partitioned by unifiedV
th.In actual analog circuit, a parameter of a circuit element may vary within a range around its nominal value without treating it as a fault. This is termed as “tolerance.” On any test point, theV
th is used as a unified criterion to handle the tolerance problem. It is not feasible. Different test points may have different sensitivities to a given component’s parameter deviation [24]. Even on the identical test point, the faulty voltage with respect to different fault source may vary within different range. Another misconception about the integer-coded technique is that the faulty voltages on different test points are independent from each other [12]. In fact, the strong dependence of faulty voltages on different test points is a robust solution to fault diagnosis [6]. Making use of (
1
) the faulty voltage distribution relationship of different faults on one test point and  (
2
) the voltage relationship between different test points with respect to one fault, this paper propose a new test point selection method.The paper is organized as follows. Section2 formulates the basic problems (i.e., tolerance affected faulty voltage distribution and faulty voltage dependence relationship). Simulation based solution to these problems is illustrated in Section 3. Section 4 proposes heuristic graph search method to facilitate the test points selection process. Section 5 presents several simulated results and Section 6 concludes this work.


## 2. Problem Formulation

In order to formulate the test selection problem, we assume that the following information is available.s
i: the ith fault case of the circuit under test (CUT).
S: set of potential fault cases, S
=
{
s
0
,
s
1
,
…
,
s
|
S
|
}, where |
S
| is the cardinality of set S.
t
i: the ith test point.
T: set of candidate test points, T
=
{
t
1
,
t
2
,
…
,
t
|
T
|
}.
α: predefined tolerance limit.
x
i: nominal parameter value of the ith component.
p
i: fault free parameter of the ith component, (
1
-
a
)
x
i
≤
p
i
≤
(
1
+
a
)
x
i.
P: parameter space, P
=
{
(
1
-
a
)
x
i
≤
p
i
≤
(
1
+
a
)
x
i
,
1
≤
i
≤
N
}, where N is passive component number of the CUT.
f
i
(
u
): fault voltage probability density function (PDF) of fault s
i obtained on a given test point.
A: ambiguous set array. The ith ambiguous set is A
i
=
{
a
1
,
a
2
,
…
,
a
|
A
i
|
}. a
j is the index of jth fault of this ambiguous set.
C
=
[
v
1
,
v
2
,
…
,
v
|
A
|
+
1
]: scale array. It indicates ambiguous areas of voltage space. If there is any faulty voltage incurred by s
i which falls into the kth ambiguous interval (v
k
,
v
k
+
1), the fault s
i belongs to A
k.
Pr: cumulative distribution function array. P
r
i represents the probability of the ith ambiguous set occurrence.
V: Monte-Carlo simulated two-dimensional voltages array V
(
i
,
j
), where i represents the ith fault case and j is the jth simulation.
MC: number of Monte-Carlo simulations.
D: two-dimensional matrix. Each element d
i
j is a bit array. The length of array is equal to MC. If the mth simulated faulty voltage of the jth fault fall into the ith ambiguous interval (
v
i
,
v
i
+
1
), d
i
j
m is set to 1, 0 otherwise.
I
(
t
): information content for a given test point t.


### 2.1. Tolerance Affected Faulty Voltage Distribution and Entropy

If the tolerance is taken into consideration, faulty voltage of any fault varies in a range around its nominal value. The faulty voltage distributions induced by theith fault case s
i are represented by PDFs f
i
(
u
). Because the components’ parameter vary within the tolerance limit, the variable u varies within a limited range (v
i
l, v
i
u). Suppose that there are |
S
| fault cases; there are 2
×
|
S
| extrema, that is, v
1
l
,
v
1
u
,
v
2
l
,
v
2
u
,
…
,
v
|
S
|
l
,
v
|
S
|
u. All the extrema are arranged in ascending order and rewritten as v
1, v
2, v
3
,
…
,
v
2
|
S
|. They partition the whole faulty voltage space into 2
×
|
S
|
-
1 distinct intervals, referred to as ambiguous intervals in this paper. If any fault voltage of the ith fault case fall into the jth interval (v
j, v
j
+
1), this fault case is added to the jth ambiguous set A
j. Any fault case might fall into more than one ambiguous sets, and any ambiguous set might contain more than one fault cases. If the cardinality of set A
j is 1, only one fault case s
i is involved in this ambiguous set. In the fault diagnosis phase, if the measured fault voltage falls into the interval (v
j, v
j
+
1), which determine the set A
j, the fault case must be s
i. Without loss of any generality, the jth ambiguous set containing l fault cases is denoted by A
j
l. In the fault diagnosis phase, if the measured fault voltage falls into voltage interval which determine any ambiguous set A
j
1, the fault source must be pinpointed. Therefore, for a given CUT, the probability of faults can be pinpointed and is calculated as follows:
(1)
F
R
1
=
Pr
[
u
∈
(
v
1
1
,
v
2
1
)
∪
(
v
2
1
,
v
3
1
)
∪
⋯
∪
(
v
|
A
1
|
-
1
1
,
v
|
A
1
|
1
)
]
=
∫
v
1
1
v
2
1
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
+
∫
v
2
1
v
3
1
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
⋯
∫
v
|
A
1
|
-
1
1
v
|
A
1
|
1
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
.
Similarly, F
R
2 and F
R
l are calculated by the following formulas:
(2)
F
R
2
=
Pr
[
u
∈
(
v
1
2
,
v
2
2
)
∪
(
v
2
2
,
v
3
2
)
∪
⋯
∪
(
v
|
A
2
|
-
1
2
,
v
|
A
2
|
2
)
]
=
∫
v
1
2
v
2
2
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
+
∫
v
2
2
v
3
2
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
…
∫
v
|
A
2
|
-
1
2
v
|
A
2
|
2
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
,
F
R
l
=
Pr
[
u
∈
(
v
1
l
,
v
2
l
)
∪
(
v
2
l
,
v
3
l
)
∪
⋯
∪
(
v
|
A
l
|
-
1
l
,
v
|
A
l
|
l
)
]
=
∫
v
1
l
v
2
l
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
+
∫
v
2
l
v
3
l
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
⋯
∫
v
|
A
l
|
-
1
L
v
|
A
l
|
l
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
,
where FR
l is fault resolution to l fault cases.The information theoretic concept of entropy is used to evaluate the probability of faults being diagnosed. Assume that there are|
A
| ambiguity sets; the equation |
A
|
=
∑
l
=
1
L
|
A
l
| holds, where A
l
=
{
A
1
l
,
A
2
l
,…,
A
|
A
l
|
l
}. The probability of a fault being isolated from ambiguity set A
j
l is approximated by 1
/
l. Obviously, if l
=
1, 1
/
l
=
1. It means that the sole fault in A
j
l is definitely diagnosed. Along with the increasing of fault number, faults being isolated are getting difficult. The entropy-based measurement or information content for a given test point is expressed by
(3)
I
(
t
)
=
-
(
F
R
1
log
⁡
1
1
+
F
R
2
log
⁡
1
2
+
⋯
+
F
R
L
log
⁡
1
L
)
=
F
R
2
log
⁡
2
+
F
R
3
log
⁡
3
+
⋯
+
FR
L
log
⁡
L
.The physical explanation ofI
(
t
) is the information needed to isolate the faults in ambiguous sets, which are derived from test point t. Obviously, the smaller I
(
t
) is, the better the test point t is. In particular, if all faults are isolated, that is, |
A
i
|
≡
1 for all possible i, I
(
t
) is equal to zero.


### 2.2. Voltage Dependence Based Test Point Adding

Additional test points are needed to further partition the fault cases involved in set{
A
j
∣
|
A
j
|
>
1
}. Suppose that the faulty voltage range determining the set {
A
j
∣
|
A
j
|
>
1
} is (
v
j
,
v
j
+
1
). First, we need to find the parameter subspace P
′ which induce the faulty voltage range (
v
j
,
v
j
+
1
) on test point t
1. Then, with the same parameter subspace P
′, the faulty voltage on the newly selected test point t
2 is measured. After all fault cases in set {
A
j
∣
|
A
j
|
>
1
} are examined, the faulty voltage distribution of ith fault is represented by PDFs f
i
(
u
t
2
). By using the same ambiguous set partition method illustrated in the first paragraph of Section 2.1, the fault cases are further partitioned into several ambiguous sets and fault voltage intervals. A
j denote the jth ambiguous set determined by the formerly selected test points. If a new test point is used to further partition the faults in A
j, the fault resolution to l fault casesof the newly selected test point is denoted by F
R
l
j. The fault resolution determined by t
1 and t
2 together is calculated by conditional probability formula:
(4)
F
R
1
=
F
R
1
+
∑
j
=
1
|
A
|
(
F
R
1
j
×
Pr
(
A
j
)
)
|
A
j
|
>
1
,
F
R
2
=
F
R
2
+
∑
j
=
1
|
A
|
(
F
R
2
j
×
Pr
(
A
j
)
)
|
A
j
|
>
2
,
F
R
l
=
F
R
l
+
∑
j
=
1
|
A
|
(
F
R
l
j
×
Pr
(
A
j
)
)
|
A
j
|
>
l
.


### 2.3. Example Illustration

An example is used to further clarify the proposed method. Take test pointt
1 in Figure 1 for example. The faulty voltage distributions induced by s
0, s
1, s
2, s
3, and s
4 are shown in Figure 2.Figure 2
Faulty voltage distribution on test pointt
1.These curves are represented by PDFsf
1
(
u
), f
2
(
u
), f
3
(
u
), and f
4
(
u
), respectively. Take s
0, for example. The measured faulty voltage varies within (v
a, v
c). Similarly, the upper and lower faulty voltage bounds (or extrema) of s
1 are v
b and v
d, respectively. Totally, there are five fault cases; hence, there are ten extrema, that is, v
a
,
v
b
,
…
,
v
j. They partition the whole faulty voltage space into nine distinct intervals. It can be seen clearly from Figure 2 that if measured faulty voltage falls into the interval (v
a
,
v
b), the fault case must be s
0. If the faulty voltage is larger than v
f and smaller than v
g, either s
2 or s
3 occurred. Ambiguous sets determined by ambiguous intervals are shown in Table 1.Table 1
Ambiguous set information.
Ambiguous setA
A
1
A
2
A
3
A
4
A
5
A
6
A
7
A
8
A
9
Ambiguous interval
(
v
a
,
v
b
)
(
v
b
,
v
c
)
(
v
c
,
v
d
)
(
v
d
,
v
e
)
(
v
e
,
v
f
)
(
v
f
,
v
g
)
(
v
g
,
v
h
)
(
v
h
,
v
i
)
(
v
i
,
v
j
)
Fault case
s
0
s
0
,
s
1
s
1
—
s
3
s
3
,
s
2
s
2
,
s
3
,
s
4
s
2
,
s
4
s
4
Fault number
1
2
1
0
1
2
3
2
1It can be seen from this table that some faults can be pinpointed. For example, the faults must bes
0, s
1, s
3, and s
4 if the measured voltages fall into the range of (v
a, v
b), (v
c, v
d), (v
e, v
f), and (v
i, v
j), respectively. The probability of these faults being diagnosed is as follows:
(5)
F
R
1
=
Pr
[
u
∈
(
v
a
,
v
b
)
∪
(
v
c
,
v
d
)
∪
(
v
e
,
v
f
)
∪
(
v
i
,
v
j
)
]
=
∫
v
a
v
b
f
0
(
u
)
d
u
+
∫
v
c
v
d
f
1
(
u
)
d
u
+
∫
v
e
v
f
f
3
(
u
)
d
u
+
∫
v
i
v
j
f
4
(
u
)
d
u
.
Similarly, F
R
2 and F
R
3 are calculated:
(6)
F
R
2
=
Pr
[
u
∈
(
v
b
,
v
c
)
∪
(
v
f
,
v
g
)
∪
(
v
h
,
v
i
)
]
=
∫
v
b
v
c
[
f
0
(
u
)
+
f
1
(
u
)
]
d
u
+
∫
v
f
v
g
[
f
2
(
u
)
+
f
3
(
u
)
]
d
u
+
∫
v
h
v
i
[
f
2
(
u
)
+
f
4
(
u
)
]
d
u
,
F
R
3
=
Pr
[
u
∈
(
v
g
,
v
h
)
]
=
∫
v
g
v
h
[
f
2
(
u
)
+
f
3
(
u
)
+
f
4
(
u
)
]
d
u
.The entropy-based measurement oft
1 is calculated by formula (3):
(7)
I
(
t
1
)
=
-
(
F
R
1
log
⁡
1
1
+
F
R
2
log
⁡
1
2
+
⋯
+
F
R
3
log
⁡
1
3
)
=
F
R
2
log
⁡
2
+
F
R
3
log
⁡
3
.On test pointt
1, faulty voltages induced by three faults {
s
2
,
s
3
,
s
4
} fall into the identical range (
v
g
,
v
h
). To diagnose these faults, another test point t
2 is needed. Figure 3 is used to illustrate how to use selected test point to further partition current ambiguous set.Figure 3
Faulty voltage dependence.First, we need to find the parameter subspaceP
′ which induces the faulty voltages range (
v
g
,
v
h
) on test point t
1. Then, with the parameter varying within the same subspace P
′, the faulty voltages on the newly selected test point t
2 are measured. The faulty voltage distribution curves represented by f
2
′
(
u
t
2
), f
3
′
(
u
t
2
), and f
4
′
(
u
t
2
) are shown in Figure 3. The fault resolution F
R
l
′ on test point t
2 can be calculated as follows:
(8)
F
R
1
′
=
Pr
⁡
[
u
2
∈
(
v
a
′
,
v
b
′
)
∪
(
v
c
′
,
v
d
′
)
∪
(
v
e
′
,
v
f
′
)
∣
u
t
1
∈
(
v
g
,
v
h
)
(
v
a
′
,
v
b
′
)
]
=
∫
v
a
′
v
b
′
f
3
′
(
u
t
2
)
d
u
t
2
+
∫
v
c
’
v
d
′
f
3
′
(
u
t
2
)
d
u
t
2
+
∫
v
e
′
v
f
′
f
4
′
(
u
t
2
)
d
u
t
2
,
F
R
2
′
=
Pr
[
u
t
2
∈
(
v
b
′
,
v
c
′
)
∣
u
t
1
∈
(
v
g
,
v
h
)
]
=
∫
v
b
′
v
c
′
[
f
2
′
(
u
t
2
)
+
f
3
′
(
u
t
2
)
]
d
u
t
2
.The fault resolution determined byt
1 and t
2 together is
(9)
F
R
1
=
F
R
1
+
F
R
1
′
×
Pr
[
u
t
1
∈
(
v
g
,
v
h
)
]
=
F
R
1
+
F
R
1
′
×
F
R
3
,
F
R
2
=
F
R
2
+
F
R
2
′
×
Pr
[
u
t
1
∈
(
v
g
,
v
h
)
]
=
F
R
2
+
F
R
2
′
×
F
R
3
.Only the 6th ambiguous set in Table1 is considered so far. After all ambiguous sets were further partitioned by test point t
2, the fault resolution and entropy determined by t
1 and t
2 together are obtained. If the entropy is equal to zero, the test points selection process is complete; otherwise, additional test points are needed. However, there are two difficulties in the test points selection process. First, the explicit expression of faulty voltage PDF is hard to obtain. Second, finding the parameter subspace P
′ which induces a specific faulty voltage range is prohibitive. Solutions to these problems are proposed in the following section.


## 2.1. Tolerance Affected Faulty Voltage Distribution and Entropy

If the tolerance is taken into consideration, faulty voltage of any fault varies in a range around its nominal value. The faulty voltage distributions induced by theith fault case s
i are represented by PDFs f
i
(
u
). Because the components’ parameter vary within the tolerance limit, the variable u varies within a limited range (v
i
l, v
i
u). Suppose that there are |
S
| fault cases; there are 2
×
|
S
| extrema, that is, v
1
l
,
v
1
u
,
v
2
l
,
v
2
u
,
…
,
v
|
S
|
l
,
v
|
S
|
u. All the extrema are arranged in ascending order and rewritten as v
1, v
2, v
3
,
…
,
v
2
|
S
|. They partition the whole faulty voltage space into 2
×
|
S
|
-
1 distinct intervals, referred to as ambiguous intervals in this paper. If any fault voltage of the ith fault case fall into the jth interval (v
j, v
j
+
1), this fault case is added to the jth ambiguous set A
j. Any fault case might fall into more than one ambiguous sets, and any ambiguous set might contain more than one fault cases. If the cardinality of set A
j is 1, only one fault case s
i is involved in this ambiguous set. In the fault diagnosis phase, if the measured fault voltage falls into the interval (v
j, v
j
+
1), which determine the set A
j, the fault case must be s
i. Without loss of any generality, the jth ambiguous set containing l fault cases is denoted by A
j
l. In the fault diagnosis phase, if the measured fault voltage falls into voltage interval which determine any ambiguous set A
j
1, the fault source must be pinpointed. Therefore, for a given CUT, the probability of faults can be pinpointed and is calculated as follows:
(1)
F
R
1
=
Pr
[
u
∈
(
v
1
1
,
v
2
1
)
∪
(
v
2
1
,
v
3
1
)
∪
⋯
∪
(
v
|
A
1
|
-
1
1
,
v
|
A
1
|
1
)
]
=
∫
v
1
1
v
2
1
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
+
∫
v
2
1
v
3
1
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
⋯
∫
v
|
A
1
|
-
1
1
v
|
A
1
|
1
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
.
Similarly, F
R
2 and F
R
l are calculated by the following formulas:
(2)
F
R
2
=
Pr
[
u
∈
(
v
1
2
,
v
2
2
)
∪
(
v
2
2
,
v
3
2
)
∪
⋯
∪
(
v
|
A
2
|
-
1
2
,
v
|
A
2
|
2
)
]
=
∫
v
1
2
v
2
2
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
+
∫
v
2
2
v
3
2
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
…
∫
v
|
A
2
|
-
1
2
v
|
A
2
|
2
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
,
F
R
l
=
Pr
[
u
∈
(
v
1
l
,
v
2
l
)
∪
(
v
2
l
,
v
3
l
)
∪
⋯
∪
(
v
|
A
l
|
-
1
l
,
v
|
A
l
|
l
)
]
=
∫
v
1
l
v
2
l
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
+
∫
v
2
l
v
3
l
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
⋯
∫
v
|
A
l
|
-
1
L
v
|
A
l
|
l
[
f
1
(
u
)
+
f
2
(
u
)
+
⋯
+
f
|
S
|
(
u
)
]
d
u
,
where FR
l is fault resolution to l fault cases.The information theoretic concept of entropy is used to evaluate the probability of faults being diagnosed. Assume that there are|
A
| ambiguity sets; the equation |
A
|
=
∑
l
=
1
L
|
A
l
| holds, where A
l
=
{
A
1
l
,
A
2
l
,…,
A
|
A
l
|
l
}. The probability of a fault being isolated from ambiguity set A
j
l is approximated by 1
/
l. Obviously, if l
=
1, 1
/
l
=
1. It means that the sole fault in A
j
l is definitely diagnosed. Along with the increasing of fault number, faults being isolated are getting difficult. The entropy-based measurement or information content for a given test point is expressed by
(3)
I
(
t
)
=
-
(
F
R
1
log
⁡
1
1
+
F
R
2
log
⁡
1
2
+
⋯
+
F
R
L
log
⁡
1
L
)
=
F
R
2
log
⁡
2
+
F
R
3
log
⁡
3
+
⋯
+
FR
L
log
⁡
L
.The physical explanation ofI
(
t
) is the information needed to isolate the faults in ambiguous sets, which are derived from test point t. Obviously, the smaller I
(
t
) is, the better the test point t is. In particular, if all faults are isolated, that is, |
A
i
|
≡
1 for all possible i, I
(
t
) is equal to zero.


## 2.2. Voltage Dependence Based Test Point Adding

Additional test points are needed to further partition the fault cases involved in set{
A
j
∣
|
A
j
|
>
1
}. Suppose that the faulty voltage range determining the set {
A
j
∣
|
A
j
|
>
1
} is (
v
j
,
v
j
+
1
). First, we need to find the parameter subspace P
′ which induce the faulty voltage range (
v
j
,
v
j
+
1
) on test point t
1. Then, with the same parameter subspace P
′, the faulty voltage on the newly selected test point t
2 is measured. After all fault cases in set {
A
j
∣
|
A
j
|
>
1
} are examined, the faulty voltage distribution of ith fault is represented by PDFs f
i
(
u
t
2
). By using the same ambiguous set partition method illustrated in the first paragraph of Section 2.1, the fault cases are further partitioned into several ambiguous sets and fault voltage intervals. A
j denote the jth ambiguous set determined by the formerly selected test points. If a new test point is used to further partition the faults in A
j, the fault resolution to l fault casesof the newly selected test point is denoted by F
R
l
j. The fault resolution determined by t
1 and t
2 together is calculated by conditional probability formula:
(4)
F
R
1
=
F
R
1
+
∑
j
=
1
|
A
|
(
F
R
1
j
×
Pr
(
A
j
)
)
|
A
j
|
>
1
,
F
R
2
=
F
R
2
+
∑
j
=
1
|
A
|
(
F
R
2
j
×
Pr
(
A
j
)
)
|
A
j
|
>
2
,
F
R
l
=
F
R
l
+
∑
j
=
1
|
A
|
(
F
R
l
j
×
Pr
(
A
j
)
)
|
A
j
|
>
l
.


## 2.3. Example Illustration

An example is used to further clarify the proposed method. Take test pointt
1 in Figure 1 for example. The faulty voltage distributions induced by s
0, s
1, s
2, s
3, and s
4 are shown in Figure 2.Figure 2
Faulty voltage distribution on test pointt
1.These curves are represented by PDFsf
1
(
u
), f
2
(
u
), f
3
(
u
), and f
4
(
u
), respectively. Take s
0, for example. The measured faulty voltage varies within (v
a, v
c). Similarly, the upper and lower faulty voltage bounds (or extrema) of s
1 are v
b and v
d, respectively. Totally, there are five fault cases; hence, there are ten extrema, that is, v
a
,
v
b
,
…
,
v
j. They partition the whole faulty voltage space into nine distinct intervals. It can be seen clearly from Figure 2 that if measured faulty voltage falls into the interval (v
a
,
v
b), the fault case must be s
0. If the faulty voltage is larger than v
f and smaller than v
g, either s
2 or s
3 occurred. Ambiguous sets determined by ambiguous intervals are shown in Table 1.Table 1
Ambiguous set information.
Ambiguous setA
A
1
A
2
A
3
A
4
A
5
A
6
A
7
A
8
A
9
Ambiguous interval
(
v
a
,
v
b
)
(
v
b
,
v
c
)
(
v
c
,
v
d
)
(
v
d
,
v
e
)
(
v
e
,
v
f
)
(
v
f
,
v
g
)
(
v
g
,
v
h
)
(
v
h
,
v
i
)
(
v
i
,
v
j
)
Fault case
s
0
s
0
,
s
1
s
1
—
s
3
s
3
,
s
2
s
2
,
s
3
,
s
4
s
2
,
s
4
s
4
Fault number
1
2
1
0
1
2
3
2
1It can be seen from this table that some faults can be pinpointed. For example, the faults must bes
0, s
1, s
3, and s
4 if the measured voltages fall into the range of (v
a, v
b), (v
c, v
d), (v
e, v
f), and (v
i, v
j), respectively. The probability of these faults being diagnosed is as follows:
(5)
F
R
1
=
Pr
[
u
∈
(
v
a
,
v
b
)
∪
(
v
c
,
v
d
)
∪
(
v
e
,
v
f
)
∪
(
v
i
,
v
j
)
]
=
∫
v
a
v
b
f
0
(
u
)
d
u
+
∫
v
c
v
d
f
1
(
u
)
d
u
+
∫
v
e
v
f
f
3
(
u
)
d
u
+
∫
v
i
v
j
f
4
(
u
)
d
u
.
Similarly, F
R
2 and F
R
3 are calculated:
(6)
F
R
2
=
Pr
[
u
∈
(
v
b
,
v
c
)
∪
(
v
f
,
v
g
)
∪
(
v
h
,
v
i
)
]
=
∫
v
b
v
c
[
f
0
(
u
)
+
f
1
(
u
)
]
d
u
+
∫
v
f
v
g
[
f
2
(
u
)
+
f
3
(
u
)
]
d
u
+
∫
v
h
v
i
[
f
2
(
u
)
+
f
4
(
u
)
]
d
u
,
F
R
3
=
Pr
[
u
∈
(
v
g
,
v
h
)
]
=
∫
v
g
v
h
[
f
2
(
u
)
+
f
3
(
u
)
+
f
4
(
u
)
]
d
u
.The entropy-based measurement oft
1 is calculated by formula (3):
(7)
I
(
t
1
)
=
-
(
F
R
1
log
⁡
1
1
+
F
R
2
log
⁡
1
2
+
⋯
+
F
R
3
log
⁡
1
3
)
=
F
R
2
log
⁡
2
+
F
R
3
log
⁡
3
.On test pointt
1, faulty voltages induced by three faults {
s
2
,
s
3
,
s
4
} fall into the identical range (
v
g
,
v
h
). To diagnose these faults, another test point t
2 is needed. Figure 3 is used to illustrate how to use selected test point to further partition current ambiguous set.Figure 3
Faulty voltage dependence.First, we need to find the parameter subspaceP
′ which induces the faulty voltages range (
v
g
,
v
h
) on test point t
1. Then, with the parameter varying within the same subspace P
′, the faulty voltages on the newly selected test point t
2 are measured. The faulty voltage distribution curves represented by f
2
′
(
u
t
2
), f
3
′
(
u
t
2
), and f
4
′
(
u
t
2
) are shown in Figure 3. The fault resolution F
R
l
′ on test point t
2 can be calculated as follows:
(8)
F
R
1
′
=
Pr
⁡
[
u
2
∈
(
v
a
′
,
v
b
′
)
∪
(
v
c
′
,
v
d
′
)
∪
(
v
e
′
,
v
f
′
)
∣
u
t
1
∈
(
v
g
,
v
h
)
(
v
a
′
,
v
b
′
)
]
=
∫
v
a
′
v
b
′
f
3
′
(
u
t
2
)
d
u
t
2
+
∫
v
c
’
v
d
′
f
3
′
(
u
t
2
)
d
u
t
2
+
∫
v
e
′
v
f
′
f
4
′
(
u
t
2
)
d
u
t
2
,
F
R
2
′
=
Pr
[
u
t
2
∈
(
v
b
′
,
v
c
′
)
∣
u
t
1
∈
(
v
g
,
v
h
)
]
=
∫
v
b
′
v
c
′
[
f
2
′
(
u
t
2
)
+
f
3
′
(
u
t
2
)
]
d
u
t
2
.The fault resolution determined byt
1 and t
2 together is
(9)
F
R
1
=
F
R
1
+
F
R
1
′
×
Pr
[
u
t
1
∈
(
v
g
,
v
h
)
]
=
F
R
1
+
F
R
1
′
×
F
R
3
,
F
R
2
=
F
R
2
+
F
R
2
′
×
Pr
[
u
t
1
∈
(
v
g
,
v
h
)
]
=
F
R
2
+
F
R
2
′
×
F
R
3
.Only the 6th ambiguous set in Table1 is considered so far. After all ambiguous sets were further partitioned by test point t
2, the fault resolution and entropy determined by t
1 and t
2 together are obtained. If the entropy is equal to zero, the test points selection process is complete; otherwise, additional test points are needed. However, there are two difficulties in the test points selection process. First, the explicit expression of faulty voltage PDF is hard to obtain. Second, finding the parameter subspace P
′ which induces a specific faulty voltage range is prohibitive. Solutions to these problems are proposed in the following section.


## 3. Simulation Based Solutions

### 3.1. Monte-Carlo Simulation Method

The following simulation procedure is automatically executed by using MATLAB calling PSPICE.Step 1.
The Monte-Carlo simulation times is initialized to MC.Step 2.
Within the predefined tolerance limit, the fault free CUT is simulated for MC times. The simulated voltages on test pointt
i are saved in V
(
1
,
m
,
t
i
), 1
≤
m
≤
MC, where 1 represents fault free case and m is the index of simulation.Step 3.
Loop variablen is equal to 2. The following steps are repeated until n
>
|
S
|.Step 4.
For fault cases
n
-
1, the Monte-Carlo simulation is run for MC times. The simulated voltages are saved in array V
(
n
,
m
,
t
i
). 1
≤
m
≤
MC. n
=
n
+
1.


### 3.2. Solution to the Entropy Calculation

For any test pointt
′, there are three steps to calculate its entropy (i.e., ambiguous sets partition, ambiguous set occurrence probability calculation, and entropy calculation). In the first step, the maximum and minimum values (i.e., max
⁡
m
⁡
V
(
n
,
m
,
t
′
) and min
⁡
m
⁡
V
(
n
,
m
,
t
′
)) are calculated; hence, 2
|
S
| extrema (i.e., v
1
,
v
2
,
…
,
v
2
|
S
|) are obtained. They are saved in either ascending or descending order, C
=
{
v
1
,
v
2
,
…
,
v
2
|
S
|
}. These extrema are used to partition the voltage space into 2
|
S
|
-
1 ambiguous intervals (i.e., (v
1,v
2),(v
2,v
3),
…,(v
2
|
S
|
-
1,v
2
|
S
|)). These intervals are used to determine 2
|
S
|
-
1 ambiguous sets A
=
{
A
1
,
A
2
,
…
,
A
2
|
S
|
-
1
}. Take Figure 2, for example. There are five faults and ten extrema, that is, from v
a through v
j. These ten extrema partition the voltage space into nine ambiguous intervals. If there is any faulty voltage of fault s
n falls into the ith ambiguous interval, the fault s
n is added into the corresponding ambiguous sets A
i. After all faults are examined, we obtain the ambiguous set information (i.e., the number of ambiguous set |
A
| and the detailed fault index in each set A
i
=
{
a
1
,
a
2
,
…
,
a
|
A
i
|
}, 1
⩽
i
⩽
2
|
S
|
-
1).The second step is ambiguous set occurrence probability calculation. The fault voltage index of fault cases
a
j fallen into the ith ambiguous interval is saved in an bit array d
i
j:
(10)
d
i
j
m
=
{
1
if
v
i
≤
V
(
a
j
,
m
,
t
′
)
<
v
i
+
1
0
else
,
where 0
<
m
<
MC. Therefore, in the ith ambiguous interval, the number of fault voltages induced by fault case s
a
j is ∑
m
=
1
MC
d
i
j
m, and the sum of fault voltages fallen into the ith ambiguous interval is ∑
j
=
1
|
A
i
|
∑
m
=
1
MC
d
i
j
m. Hence, the probability of the ith ambiguous set occurrence is as follows:
(11)
P
r
i
=
∑
j
=
1
|
A
i
|
∑
m
=
1
MC
d
i
j
m
|
S
|
×
MC
.Thirdly, based on formula (3), the information content of test point t
′ is expressed by the following formula:
(12)
I
(
t
′
)
=
∑
i
=
1
|
A
|
P
r
i
log
⁡
|
A
i
|
.


### 3.3. Solution to Adding Test Point

If there is ambiguous setA
i satisfying |
A
i
|
>
1, additional test point is needed to further distinguish the faults s
a
1
,
s
a
2
,
…
,
s
|
A
i
| in ambiguous set A
i. The basic idea proposed in Section 2.2 is to find the parameter subspace P
′ which induce the ambiguous set A
i on test point t
′. Then, with the parameter varying within the same subspace P
′, the faulty voltages on the newly selected test point t
′
′ are measured and grouped. Obviously, the parameter subspace P
′ is not known. But it can be seen from Figure 3 that if we can directly map the fault voltage from test points t
′ to t
′
′, we do not have to know the parameter subspace P
′. Suppose that the CUT parameter is P
~
m in the mth simulation of fault s
a
j; the voltage on test point t
′ is V
(
a
j
,
m
,
t
′
). With the same parameter, the voltage on test point t
′
′ is V
(
a
j
,
m
,
t
′
′
). Hence, the second subscript m shows the voltage relationship between the two test points.On test pointt
′, whether the mth simulation of s
a
j falls into the ith ambiguous interval (
v
i
,
v
i
+
1
) is indicated by d
i
j
m. If d
i
j
m
=
1, the answer is positive, negative otherwise. Therefore, we use m
·
d
i
j
m to indicate whether the mth faulty voltage of s
a
j on test point t
′
′ is considered or not. For each fault s
a
j in set A
i, the maximum and minimum values of V
(
a
j
,
m
·
d
i
j
m
,
t
′
′
) are calculated. Hence, 2|
A
i
| extrema (i.e., v
1,v
2
,
…
,
v
2
|
A
i
|) are obtained. They are saved in array and arranged in either ascending or descending order. These extrema are used to partition the voltage space into 2
|
A
i
|
-
1 ambiguous intervals. These intervals are used to determine 2
|
A
i
|
-
1 ambiguous sets. It means that the ith ambiguous set A
i of test point t
′ is further partitioned by test point t
′
′ into 2
|
A
i
|
-
1 ambiguous sets.For the2
|
A
i
|
-
1 ambiguous sets, the conditional probability Pr
(
A
q
∣
A
i
) is calculated by using formula (11), where 1
⩽
q
⩽
2
|
A
i
|
-
1. Therefore, the probability P
r
q
=
Pr
(
A
q
∣
A
i
)
×
P
r
i. Only the A
i ambiguous set on test point t
′ is considered so far. After all ambiguous sets were further partitioned by test point t
′
′, the entropy determined by t
′ and t
′
′ together is calculated by using (11).


## 3.1. Monte-Carlo Simulation Method

The following simulation procedure is automatically executed by using MATLAB calling PSPICE.Step 1.
The Monte-Carlo simulation times is initialized to MC.Step 2.
Within the predefined tolerance limit, the fault free CUT is simulated for MC times. The simulated voltages on test pointt
i are saved in V
(
1
,
m
,
t
i
), 1
≤
m
≤
MC, where 1 represents fault free case and m is the index of simulation.Step 3.
Loop variablen is equal to 2. The following steps are repeated until n
>
|
S
|.Step 4.
For fault cases
n
-
1, the Monte-Carlo simulation is run for MC times. The simulated voltages are saved in array V
(
n
,
m
,
t
i
). 1
≤
m
≤
MC. n
=
n
+
1.


## 3.2. Solution to the Entropy Calculation

For any test pointt
′, there are three steps to calculate its entropy (i.e., ambiguous sets partition, ambiguous set occurrence probability calculation, and entropy calculation). In the first step, the maximum and minimum values (i.e., max
⁡
m
⁡
V
(
n
,
m
,
t
′
) and min
⁡
m
⁡
V
(
n
,
m
,
t
′
)) are calculated; hence, 2
|
S
| extrema (i.e., v
1
,
v
2
,
…
,
v
2
|
S
|) are obtained. They are saved in either ascending or descending order, C
=
{
v
1
,
v
2
,
…
,
v
2
|
S
|
}. These extrema are used to partition the voltage space into 2
|
S
|
-
1 ambiguous intervals (i.e., (v
1,v
2),(v
2,v
3),
…,(v
2
|
S
|
-
1,v
2
|
S
|)). These intervals are used to determine 2
|
S
|
-
1 ambiguous sets A
=
{
A
1
,
A
2
,
…
,
A
2
|
S
|
-
1
}. Take Figure 2, for example. There are five faults and ten extrema, that is, from v
a through v
j. These ten extrema partition the voltage space into nine ambiguous intervals. If there is any faulty voltage of fault s
n falls into the ith ambiguous interval, the fault s
n is added into the corresponding ambiguous sets A
i. After all faults are examined, we obtain the ambiguous set information (i.e., the number of ambiguous set |
A
| and the detailed fault index in each set A
i
=
{
a
1
,
a
2
,
…
,
a
|
A
i
|
}, 1
⩽
i
⩽
2
|
S
|
-
1).The second step is ambiguous set occurrence probability calculation. The fault voltage index of fault cases
a
j fallen into the ith ambiguous interval is saved in an bit array d
i
j:
(10)
d
i
j
m
=
{
1
if
v
i
≤
V
(
a
j
,
m
,
t
′
)
<
v
i
+
1
0
else
,
where 0
<
m
<
MC. Therefore, in the ith ambiguous interval, the number of fault voltages induced by fault case s
a
j is ∑
m
=
1
MC
d
i
j
m, and the sum of fault voltages fallen into the ith ambiguous interval is ∑
j
=
1
|
A
i
|
∑
m
=
1
MC
d
i
j
m. Hence, the probability of the ith ambiguous set occurrence is as follows:
(11)
P
r
i
=
∑
j
=
1
|
A
i
|
∑
m
=
1
MC
d
i
j
m
|
S
|
×
MC
.Thirdly, based on formula (3), the information content of test point t
′ is expressed by the following formula:
(12)
I
(
t
′
)
=
∑
i
=
1
|
A
|
P
r
i
log
⁡
|
A
i
|
.


## 3.3. Solution to Adding Test Point

If there is ambiguous setA
i satisfying |
A
i
|
>
1, additional test point is needed to further distinguish the faults s
a
1
,
s
a
2
,
…
,
s
|
A
i
| in ambiguous set A
i. The basic idea proposed in Section 2.2 is to find the parameter subspace P
′ which induce the ambiguous set A
i on test point t
′. Then, with the parameter varying within the same subspace P
′, the faulty voltages on the newly selected test point t
′
′ are measured and grouped. Obviously, the parameter subspace P
′ is not known. But it can be seen from Figure 3 that if we can directly map the fault voltage from test points t
′ to t
′
′, we do not have to know the parameter subspace P
′. Suppose that the CUT parameter is P
~
m in the mth simulation of fault s
a
j; the voltage on test point t
′ is V
(
a
j
,
m
,
t
′
). With the same parameter, the voltage on test point t
′
′ is V
(
a
j
,
m
,
t
′
′
). Hence, the second subscript m shows the voltage relationship between the two test points.On test pointt
′, whether the mth simulation of s
a
j falls into the ith ambiguous interval (
v
i
,
v
i
+
1
) is indicated by d
i
j
m. If d
i
j
m
=
1, the answer is positive, negative otherwise. Therefore, we use m
·
d
i
j
m to indicate whether the mth faulty voltage of s
a
j on test point t
′
′ is considered or not. For each fault s
a
j in set A
i, the maximum and minimum values of V
(
a
j
,
m
·
d
i
j
m
,
t
′
′
) are calculated. Hence, 2|
A
i
| extrema (i.e., v
1,v
2
,
…
,
v
2
|
A
i
|) are obtained. They are saved in array and arranged in either ascending or descending order. These extrema are used to partition the voltage space into 2
|
A
i
|
-
1 ambiguous intervals. These intervals are used to determine 2
|
A
i
|
-
1 ambiguous sets. It means that the ith ambiguous set A
i of test point t
′ is further partitioned by test point t
′
′ into 2
|
A
i
|
-
1 ambiguous sets.For the2
|
A
i
|
-
1 ambiguous sets, the conditional probability Pr
(
A
q
∣
A
i
) is calculated by using formula (11), where 1
⩽
q
⩽
2
|
A
i
|
-
1. Therefore, the probability P
r
q
=
Pr
(
A
q
∣
A
i
)
×
P
r
i. Only the A
i ambiguous set on test point t
′ is considered so far. After all ambiguous sets were further partitioned by test point t
′
′, the entropy determined by t
′ and t
′
′ together is calculated by using (11).


## 4. Heuristic Graph Search Algorithm

Breadth-first and depth-first searches are two commonly used graph search algorithms. Breadth-first search algorithm can find a global minimum set [25], but it is NP-complete [26] and, therefore, is computationally expensive. In this paper, a heuristic depth-first graph search algorithm is developed to solve the test point selection problem. Root node S contain all fault cases. In Sections 2 and 3, the symbol S represents fault set and S
=
{
s
1
,
s
2
,
…
,
s
|
S
|
}. Because the root node represents all faults too, the root node and potential fault set can be represented by the same symbol S without confusion. First, every candidate test point is used to expand S and the new generated graph node belongs to Level 1. The main task is to calculate the ambiguous set information (i.e., the number of ambiguous sets, detailed fault cases in each set and bit array d
i
j) of every graph node. The calculation method is illustrated in Section 3.2. Node n in graph G saves the ambiguous set information. Second, on Level 1, a graph node n with minimal entropy I
(
n
) is selected to be expanded for the second iteration. The entropy I
(
n
) is calculated by using formula (12). Finally, the selected graph node is expanded with each test point except those used on the path from current node to root node, and the new generated graph nodes belong to Level 2. The basic node expanding method is the same as the test point adding procedure proposed in Section 3.3. These steps are executed iteratively until all faults are isolated. The detailed algorithm is given as follows.Step 1.
The graph G is initialized to the root nodeS. All potential faults are contained in node S and belong to one ambiguity set; that is, A
=
{
A
1
} and A
1
=
{
1
,
2
,
…
,
|
S
|
}. The length of bit array d
1
j
(
1
⩽
j
⩽
|
S
|
) is initialized to MC. Every bit of d
1
j is initialized to one. The ambiguity set A, probability Pr, and D are contained in root node S of graph G. Graph level label l is set to zero. All available test points are contained in set T. Current selected node n is S (viz. n
=
S). The entropy I
(
n
) is set to one.Step 2.
Repeat the following steps untilI
(
n
)
=
0 or |
T
|
=
0. Tracing the pointer from n to S, solution is derived (pointer is set in Step 3).Step 3.
Selected noden is expanded with each test point in T, respectively. By setting pointer from each newly generated node to n, these expanded nodes are added to graph G as successor nodes of n
·
l
=
l
+
1. Information I
(
n
) of every newly generated node on graph level l is calculated.Step 4.
On current level, noden with minimum I
(
n
) value is chosen. The test point used on the path from n to its direct parent node is removed from T.In Step3, the node expanding method is illustrated in Section 3.3 and the entropy calculation method is given in Section 3.2.


## 5. Simulation Results

All the simulations are executed by MATLAB calling PSPICE in an Intel 2.7 GHz processor, 2G RAM, and the Microsoft Windows XP operating system. The following parameters are used in all simulations:(i)
resistance tolerance limitα
R
=
±
5
%;
(ii)
capacitance tolerance limitα
C
=
±
5
%;Example 1 (bandpass voltage-controlled voltage source (VCVS) filter).
This example is mainly used to further clarify the proposed test selection method. The filter circuit shown in Figure4 is stimulated by a 300 Hz, 1 V sinusoidal wave. Totally, three candidate test points t
1, t
2, and t
3 and ten possible fault components are examined. This example is mainly used to further illustrate the proposed algorithm. By using the method proposed in Section 3.1, the CUT is simulated, and the voltages on all test points are saved. Totally, eleven catastrophic faults (
s
0
,
s
1
,
…
,
s
10
) shown in Table 2 are considered. Due to the page limitation, only ten Monte-Carlo simulations are run for each fault case. In each simulation, all the fault free components vary within the predefined parameter limitation, that is, α
R
=
±
5
% and α
C
=
±
5
%. It is necessary to point out that in each simulation the voltages on every test point are induced by identical parameter space P
~. The simulated voltages on test points t
1 and t
3 are shown in Table 2 and Table 6, respectively. For each fault case, the ten Monte-Carlo simulated voltages represent the faulty voltage PDF. Taking Table 2 for example, the ten voltages corresponding to s
1 are derived on test point t
1. They represent the faulty voltage distribution of R1_short on test point t
1.Table 2
Faulty voltages on test pointt
1 (Unit: V).
Fault case
Monte-Carlo simulation index
Extremum
1
2
3
4
5
6
7
8
9
10
s
0 (fault free)
0.58
0.59
0.58
0.58
0.57
0.58
0.59
0.58
0.57
0.59
(0.57, 0.59)
s
1 (R
1 short)
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
(1.00, 1.00)
s
2 (R
2 open)
0.75
0.75
0.75
0.76
0.75
0.75
0.75
0.75
0.75
0.75
(0.75, 0.76)
s
3 (R
2 short)
0
0
0
0
0
0
0
0
0
0
(0, 0)
s
4 (R
3 open)
1.19
1.20
1.17
1.13
1.24
1.19
1.18
1.18
1.16
1.22
(1.13, 1.24)
s
5 (R
3 short)
0.47
0.48
0.47
0.47
0.46
0.47
0.47
0.47
0.46
0.47
(0.46, 0.48)
s
6 (R
4 short)
0.49
0.50
0.49
0.50
0.48
0.49
0.50
0.49
0.49
0.50
(0.48, 0.50)
s
7 (R
5 short)
0
0
0
0
0
0
0
0
0
0
(0, 0)
s
8 (C
1 open)
0.50
0.51
0.50
0.51
0.49
0.50
0.51
0.50
0.49
0.51
(0.49, 0.51)
s
9 (C
1 short)
0.60
0.60
0.60
0.59
0.59
0.61
0.60
0.60
0.57
0.61
(0.57, 0.61)
s
1
0 (C
2 open)
0.51
0.53
0.52
0.52
0.51
0.52
0.52
0.52
0.51
0.52
(0.51, 0.53)Figure 4
VCVS bandpass filter.In Step1 of the proposed algorithm, all faults belong to one ambiguity set; that is, A
=
{
A
1
} and A
1
=
{
0,1
,
2,3
,
4,5
,
6,7
,
8,9
,
10
}. The probability of ambiguous set A
1 is initialized to one, Pr
1
=
1. The length of bit array d
1
j
(
1
⩽
j
⩽
11
) is initialized to MC
=
10. Every bit of d
1
j is initialized to one. The ambiguity information A, probability Pr, and D are contained in root node S of graph G. Graph level label l is set to zero, as shown in Figure 5. All available test points are listed in set T
=
{
t
1
,
t
2
,
t
3
}. Current selected node n is S. The entropy I
(
n
) is set to one. Since the condition to stop in Step 2 is not satisfied, the selected node n is expanded by using Steps 3 and 4.Figure 5
Expanded graph G.In Step3, every test point in T is used to expand node n. Take t
1 for example.First, the new ambiguous set information is calculated. For each fault cases
j, its maximum and minimum faulty voltages are calculated and listed in the last column of Table 2. For the first iteration, every bit of d
1
j is one; hence, all ten simulated voltages of s
j are considered. It can be seen from the last column of Table 2 that some of the scale values are identical. Fifteen distinct voltages (i.e., v
1
,
v
2
,
…
,
v
15) are arranged in descending order and saved in Table 3. Any two adjacent voltages determine an ambiguous interval; therefore, the voltage space on test point t
1 is partitioned into 14 ambiguous intervals (i.e., (
v
1
,
v
2
)
,
(
v
2
,
v
3
)
,
…
,
(
v
14
,
v
15
)). Fourteen ambiguous sets are determined by these intervals. Take the 6th ambiguous interval (v
6 = 0.51, v
7 = 0.53), for example. In Table 2, there are some faulty voltages of faults s
8 and s
10 falling into this interval. Hence the index of these faults are save in the 6th ambiguous set A
6
=
{
8
,
10
}. After all ambiguous intervals were examined; the detailed ambiguous sets are obtained and saved in Table 4.Table 3
Scale voltage values (Unit: V).
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
11
v
12
v
13
v
14
v
15
0
0.46
0.48
0.49
0.50
0.51
0.53
0.57
0.59
0.61
0.75
0.76
1.00
1.13
1.24Table 4
Ambiguous set information.
Ambiguous setA
A
1
A
2
A
3
A
4
A
5
A
6
A
7
A
8
A
9
A
10
A
11
A
12
A
13
A
14
Fault case index
3, 7
5
5, 6
6, 8
6, 8
8, 10
10
0, 9
0, 9
9
2
2
1
4
Probability Pr (%)
18.18
8.18
1.82
6.36
7.27
11.82
0.91
7.27
9.09
1.82
8.18
0.91
9.09
9.09Second, ambiguous set occurrence probability is calculated. Take the 6th ambiguous setA
6
=
{
8
,
10
}, for example. Fault voltages of the first fault s
8 fallen into this ambiguous interval are indexed by bit array d
61. It can be seen from Table 2 that the 2nd, 4th, 7th, and 10th simulated faulty voltages of fault s
8 fall into the interval (v
6 = 0.51, v
7 = 0.53); hence d
61 = 0101001001, as shown in Table 5.Table 5
Faulty voltage involved in ambiguous setA
6.
Simulation index
1
2
3
4
5
6
7
8
9
10
d
61
0
1
0
1
0
0
1
0
0
1
d
62
1
0
1
1
1
1
1
1
1
1Table 6
Faulty voltages on test pointt
3 (Unit: V).
Faultcase
Monte-Carlo simulation index
1
2
3
4
5
6
7
8
9
10
s
0
0.44
0.46
0.44
0.43
0.43
0.45
0.45
0.45
0.41
0.46
s
1
0.75
0.77
0.76
0.73
0.75
0.76
0.76
0.77
0.73
0.78
s
2
0.56
0.58
0.57
0.56
0.56
0.57
0.57
0.57
0.54
0.58
s
3
0
0
0
0
0
0
0
0
0
0
s
4
1.49
1.52
1.44
1.36
1.58
1.49
1.47
1.47
1.41
1.57
s
5
0
0
0
0
0
0
0
0
0
0
s
6
0.15
0.15
0.15
0.15
0.14
0.15
0.15
0.15
0.15
0.15
s
7
1.00
1.05
1.00
1.03
0.98
1.01
1.03
1.00
0.98
1.03
s
8
0
0
0
0
0
0
0
0
0
0
s
9
1.49
1.52
1.48
1.42
1.50
1.53
1.49
1.51
1.40
1.56
s
10
0.45
0.48
0.47
0.45
0.44
0.46
0.47
0.47
0.43
0.48Similarly, the fault voltages of faults
10 fallen into this ambiguous interval are indexed by bit array d
62 = 1011111111. The probability of the 6th ambiguous set occurrence is calculated by formula (11):
(13)
P
r
6
=
∑
j
=
1
|
A
6
|
∑
m
=
1
MC
d
6
j
m
|
S
|
×
MC
=
∑
j
=
1
2
∑
m
=
1
10
d
6
j
m
11
×
10
=
13
110
≈
11.82
%
.After all ambiguous sets listed in Table4 were examined, the detailed probability of each ambiguous sets are obtained and saved in the last row of Table 4. There are some sets that have only one fault, due to the fact that log
⁡
(
1
)
=
0 and the diagnosed fault do not need any further consideration; these sets can be removed from the table and not considered in the following graph node expanding.Thirdly, the information content of graph noden
1, which is expanded by test point t
1 from root node S, is calculated by formula (12). Consider I
(
n
1
)
=
∑
i
=
1
14
P
r
i
log
⁡
|
A
i
|
≈
0.43. In Figure 5, value in parentheses is the information content of graph node. The ambiguous sets information A, probability Pr listed in Table 4, and Monte-Carlo simulation index matrix D are all saved in the new generated graph node n
1 on Level 1 of graph G.Only the first test pointt
1 in T is considered so far. After the other two test points were examined, three graph nodes n
1, n
2, and n
3 of Level 1 are obtained and added into the graph G as successor nodes of root node S. The results are shown in Figure 5. According to Step 4 of the proposed algorithm, node n
1 has the minimum information value on Level 1; hence, it is chosen for further expanding. The test point t
1used on the path from n
1 to its direct parent node S is removed from T. Therefore, T
=
{
t
2
,
t
3
}. Obviously, the condition to stop in Step 2 is not satisfied, the proposed algorithm is executed for the second iteration. The selected node n
1 is expanded by using Steps 3 and 4. Node n
1 is referred to as n in the following context.In Step3, every test point in T is used to expand node n. Take t
3, for example.First, every ambiguous set in noden is repartitioned by t
3. Take the 6th ambiguous set A
6
=
{
8
,
10
} shown in Table 4, for example. It can be seen from Table 5 that the 2nd, 4th, 7th, and 10th simulated faulty voltages of fault s
8 are involved in this ambiguous set. The involved faulty voltages are denoted in italics in Table 6. The maximum and minimum value of the involved faulty voltages on test point t
3 are (0, 0). By using the index array d
62 shown in Table 5 and the faulty voltages listed in Table 6, the involved maximum and minimum faulty value of s
10 on test point t
3 is 0.48 V and 0.43 V, respectively. Therefore, two ambiguous intervals (i.e., (0, 0.43), (0.43, 0.48)) are achieved. In Table 6, the faulty voltages of s
8 fall into (0, 0.43), and all the faulty voltages of s
10 fall into (0.43, 0.48); hence, two newly generated ambiguous sets are A
1
=
{
s
8
} and A
2
=
{
s
10
}. It means that the faults in ambiguous set A
6 are all diagnosed. Besides the faults in the 6th ambiguous set, all other faults involved in node n can be diagnosed by adding test point t
3. The graph node generated by t
3 from node n
1 on Level 1 is drawn on Level 2 of graph G, as shown in Figure 5. The generated node is denoted by n
2 on Level 2. Due to the fact that information I
(
n
2
) = 0, the condition to stop in Step 2 is satisfied. Test points {
t
1
,
t
3
} used on the path from node n
2 on Level 2 to root node S are the final solution. The computation time of this example is about 0.011 second.If the ambiguous set concept defined by Hochwald and Bastian [1] and the integer-coded fault table technique adopted in literatures [4, 5, 11, 12, 14–21] are used, Table 7 is derived based on the simulated faulty voltages. We can conclude from Table 7 that even if all test points are used, faults s
5 and s
8 have the same integer-code “211”; hence they are not distinguishable. Apparently, the traditional integer-coded technique induces a wrong conclusion in this example.Table 7
Integer-coded table.
1
2
3
4
5
6
7
8
9
t
1
t
1
t
2
t
3
s
0
3
3
3
s
1
5
5
5
s
2
4
4
4
s
3
1
1
1
s
4
5
6
7
s
5
2
1
1
s
6
2
2
2
s
7
1
1
6
s
8
2
1
1
s
9
3
6
7
s
10
2
3
3Example 2 (leapfrog filter).
The benchmark circuit is shown in Figure6. All 6 test points are assumed to be accessible for the purpose of demonstration, T
=
{
t
1
,
t
2
,
…
,
t
6
}. Totally, 24 potential faults, including hard, soft, and multiple faults, listed in Table 8 are examined, S
=
{
s
0
,
s
1
,
s
2
,
…
,
s
23
}. For each fault, the Monte-Carlo simulation is run for 1000 times, MC = 1000. Because ambiguous sets/test points can be reduced by changing the test stimuli, two frequencies (i.e., 500 Hz and 1 kHz) of 5 V sinusoidal waves are adopted in this example. The voltages on all test points are saved. Totally, |
S
|
×
MC
×
|
T
|
×
2
=
288000 simulated data are stored.Table 8
Faulty voltage extremum (Unit: V).
t
1
t
2
t
3
t
4
t
5
t
6
m
1
1
m
12
m
21
m
22
m
31
m
32
m
41
m
42
m
51
m
52
m
61
m
62
s
0
Fault free
2.30, 2.77
2.30, 3.18
1.39, 1.85
3.30, 4.65
2.30, 2.82
2.82, 3.65
2.22, 2.99
2.54, 3.39
2.29, 2.99
2.55, 3.38
2.19, 2.85
2.23, 2.85
s
1
R
2 open
4.52, 5.76
4.03, 7.89
2.76, 3.85
6.54, 10.78
4.70, 5.71
5.60, 8.17
4.65, 5.90
5.09, 7.29
4.66, 6.27
4.94, 7.53
4.43, 6.23
4.23, 6.38
s
2
R
3 short
0, 0
0, 0
0, 0
0, 0
0, 0
0, 0
0, 0
0, 0
0, 0
0, 0
0, 0
0, 0
s
3
R
4 short
0, 0
0, 0
2.65, 3.60
5.57, 7.13
4.58, 5.43
4.54, 5.41
4.33, 5.92
4.07, 5.35
4.41, 5.96
3.94, 5.68
4.23, 5.93
3.38, 5.06
s
4
R
4 open
4.36, 5.17
3.99, 4.63
0, 0
0, 0
0, 0
0, 0
0, 0
0, 0
0, 0
0, 0
0, 0
0, 0
s
5
R
5 open
2.20, 2.80
2.01, 2.53
1.27, 1.83
2.66, 3.40
2.17, 2.69
2.14, 2.71
2.17, 2.72
1.98, 2.51
2.22, 2.88
1.95, 2.54
2.01, 2.86
1.70, 2.23
s
6
R
6 short
2.20, 2.80
2.01, 2.53
0, 0
0, 0
2.17, 2.69
2.14, 2.71
2.17, 2.72
1.98, 2.51
2.22, 2.88
1.95, 2.54
2.01, 2.86
1.70, 2.23
s
7
R
6 open
4.36, 5.17
3.99, 4.63
4.08, 5.33
3.71, 4.94
0, 0
0, 0
0, 0
0, 0
0, 0
0, 0
0, 0
0, 0
s
8
R
7 short
4.36, 5.17
3.98, 4.63
0, 0
0, 0
0, 0
0, 0
4.22, 5.54
3.70, 4.94
4.07, 5.78
3.56, 5.19
3.61, 5.53
3.15, 4.31
s
9
R
7 open
2.67, 3.62
4.54, 5.41
2.59, 3.53
4.36, 5.80
4.49, 5.37
3.34, 4.68
0, 0
0, 0
0, 0
0, 0
0, 0
0, 0
s
10
R
8 short
2.67, 3.62
4.54, 5.41
2.59, 3.53
4.36, 5.80
4.49, 5.37
3.34, 4.68
0, 0
0, 0
4.34, 5.93
3.65, 5.55
4.23, 5.80
3.35, 4.71
s
1
1
R
8 open
2.53, 3.39
1.42, 3.75
1.55, 2.50
6.38, 8.46
2.68, 3.65
5.27, 6.41
4.39, 5.64
4.12, 5.46
0, 0
0, 0
0, 0
0, 0
s
12
R
10 short
2.67, 3.62
4.54, 5.41
2.59, 3.53
4.36, 5.80
4.49, 5.37
3.34, 4.68
0, 0
0, 0
0, 0
0, 0
4.23, 5.80
3.35, 4.71
s
13
R
11 open
3.75, 4.57
4.19, 5.17
2.17, 3.04
0.48, 2.20
3.65, 4.48
0.38, 1.83
1.35, 1.87
2.56, 4.12
1.37, 1.88
2.69, 3.99
4.45, 5.95
4.47, 6.29
s
14
R
12 open
2.53, 3.39
1.42, 3.75
1.55, 2.50
6.38, 8.46
2.68, 3.65
5.27, 6.41
4.39, 5.64
4.12, 5.46
4.28, 5.88
3.99, 5.77
3.92, 5.69
3.42, 5.14
s
15
C
3 open
2.93, 3.55
3.80, 4.42
1.25, 1.80
2.05, 2.78
2.09, 2.67
1.63, 2.21
2.13, 2.79
1.93, 2.61
2.19, 2.85
1.87, 2.63
2.02, 2.83
1.69, 2.24
s
16
C
4 open
1.92, 2.39
2.58, 3.78
1.56, 2.19
4.21, 5.18
2.64, 3.23
3.24, 4.08
2.14, 2.76
1.97, 2.62
2.21, 2.84
1.95, 2.63
2.16, 2.97
2.08, 2.62
s
17
C
4 short
2.53, 3.39
1.42, 3.75
1.55, 2.49
6.38, 8.46
2.68, 3.65
5.27, 6.41
4.39, 5.64
4.12, 5.47
4.28, 5.88
3.99, 5.77
0, 0
0, 0
s
18
C
3
=
10 n
2.72, 3.19
2.90, 3.54
1.27, 1.74
2.21, 2.91
2.11, 2.61
1.85, 2.34
2.25, 3.02
2.42, 3.11
2.32, 2.96
2.42, 3.19
2.20, 2.85
2.09, 2.67
s
19
C
3
=
40 n
1.51, 1.97
3.03, 4.39
1.79, 2.43
4.98, 6.21
3.04, 3.67
4.06, 5.04
2.22, 2.88
1.80, 2.39
2.19, 2.81
1.81, 2.57
2.10, 2.78
1.45, 2.16
s
20
C
4
=
5 n
2.12, 2.59
2.34, 3.44
1.48, 1.98
3.75, 4.82
2.48, 3.00
2.95, 3.75
2.22, 2.94
2.25, 2.82
2.25, 2.87
2.19, 2.91
2.24, 2.90
2.11, 2.79
s
21
C
4
=
20 n
2.62, 3.17
1.58, 2.37
1.17, 1.59
3.47, 5.39
1.93, 2.37
2.72, 4.03
2.57, 3.36
3.52, 4.42
2.62, 3.31
3.48, 4.49
2.21, 2.86
2.13, 2.79
s
22
R
7
=
5 k, R
12
=
5 k
2.59, 3.17
1.24, 1.73
2.03, 2.64
2.17, 2.96
2.31, 2.90
2.14, 2.72
2.93, 3.65
2.21, 3.03
1.80, 2.28
2.37, 3.11
2.32, 3.10
2.01, 2.80
s
23
R
4
=
5 k, C
4
=
20 n
1.81, 2.33
1.60, 2.28
2.74, 3.38
3.67, 4.53
3.55, 4.61
2.97, 4.04
0.93, 1.53
4.51, 6.01
3.64, 4.57
4.23, 5.28
4.02, 5.33
2.53, 3.42Figure 6
Leapfrog filter.In Table8, m
i
1 and m
i
2 represent measurements on the ith test point under the 500 Hz and 1 kHz sinusoidal wave excitations, respectively. Due to the page limitation, only the maximum and minimum voltage values of each fault are shown in Table 8. Take R2open, for example. With the 500 Hz sinusoidal wave excitation, the voltage on test point t
1 varies within the interval (4.52, 5.76). It varies within (4.03, 7.89) if the frequency is adjusted to 1 kHz. In this example, the proposed algorithm is used to select the optimum measurements m
i
j.By using the proposed test points selection algorithm, the expanded graph is obtained and shown in Figure7. The algorithm is executed for five iterations. In the 5th iteration, the information of newly generated graph node n
1 is I
(
n
1
) = 0. It is the target node. Measurements {
m
11
,
m
62
,
m
21
,
m
52
,
m
32
} used on the path from the target node to root node S are the final solution. The computation time of this example is 0.40 second.Figure 7
Expanded graph.If the integer-coded fault table technique adopted in literatures [4, 5, 11, 12, 14–21] is used, Table 9 is derived from Table 8. It can be seen from Table 9 that even if all test points are used, faults s
0, s
5, s
15, s
16, s
18, s
19, s
20, s
21, and s
22 have the same code “222222422222”; hence, no matter which algorithm proposed in [4, 5, 11, 12, 14–21] is used, the integer-coded technique will induce a wrong conclusion in this example.Table 9
Integer-coded table.
m
1
1
m
1
1
m
12
m
21
m
22
m
31
m
32
m
41
m
42
m
51
m
52
m
61
m
62
s
0
2
2
2
2
2
2
4
2
2
2
2
2
s
1
3
2
2
2
2
2
5
2
3
2
3
2
s
2
1
1
1
1
1
1
1
1
1
1
1
1
s
3
1
1
2
2
2
2
5
2
3
2
3
2
s
4
3
2
1
1
1
1
1
1
1
1
1
1
s
5
2
2
2
2
2
2
4
2
2
2
2
2
s
6
2
2
1
1
2
2
4
2
2
2
2
2
s
7
3
2
3
2
1
1
1
1
1
1
1
1
s
8
3
2
1
1
1
1
5
2
3
2
3
2
s
9
2
2
2
2
2
2
1
1
1
1
1
1
s
10
2
2
2
2
2
2
1
1
3
2
3
2
s
1
1
2
2
2
2
2
2
5
2
1
1
1
1
s
12
2
2
2
2
2
2
1
1
1
1
3
2
s
13
3
2
2
2
2
2
2
2
2
2
3
2
s
14
2
2
2
2
2
2
5
2
3
2
3
2
s
15
2
2
2
2
2
2
4
2
2
2
2
2
s
16
2
2
2
2
2
2
4
2
2
2
2
2
s
17
2
2
2
2
2
2
5
2
3
2
1
1
s
18
2
2
2
2
2
2
4
2
2
2
2
2
s
19
2
2
2
2
2
2
4
2
2
2
2
2
s
20
2
2
2
2
2
2
4
2
2
2
2
2
s
21
2
2
2
2
2
2
4
2
2
2
2
2
s
22
2
2
2
2
2
2
4
2
2
2
2
2
s
23
2
2
2
2
2
2
2
2
3
2
3
2Example 3 (negative feedback amplifier).
The circuit is shown in Figure8. The excitation (input) signal is a 1 kHz 10 mV sinusoidal wave, and V
c
=
5V. All 9 test points are assumed to be accessible. Totally, 19 potential faults, including hard and soft faults, listed in Table 10 are examined, S
=
{
s
0
,
s
1
,
s
2
,
…
,
s
19
}. In particular, the CUT is operated in saturation region when R
1 is short. For each fault, the Monte-Carlo simulation is run for 1000 times. The voltages on all test points are saved. Due to the page limitation, only the maximum and minimum voltage values of each fault are shown in Table 10.Table 10
Faulty voltage extremum (Unit: V).
t
1
t
2
t
3
t
4
t
5
t
6
t
7
t
8
t
9
s
0
Fault free
0.010, 0.010
0.007, 0.010
0.010, 0.010
0.010, 0.010
0.007, 0.010
0.795, 1.058
0.001, 0.001
0.795, 1.058
0.795, 1.058
s
1
R
1 short
0.002, 0.003
0.001, 0.002
0.002, 0.002
0.002, 0.002
0.001, 0.002
0.161, 0.260
0.000, 0.000
0.161, 0.260
0.161, 0.260
s
2
R
1
=
10 k
0.010, 0.010
0.000, 0.002
0.007, 0.007
0.007, 0.007
0.000, 0.002
0.015, 0.245
0.000, 0.000
0.015, 0.245
0.015, 0.245
s
3
R
2 short
0.002, 0.003
0.000, 0.000
0.000, 0.000
0.000, 0.000
0.000, 0.000
0.000, 0.000
0.000, 0.000
0.000, 0.000
0.000, 0.000
s
4
R
2 open
0.010, 0.010
0.005, 0.007
0.009, 0.009
0.009, 0.009
0.005, 0.007
0.533, 0.746
0.001, 0.001
0.533, 0.746
0.533, 0.746
s
5
R
3 open
0.010, 0.010
0.000, 0.000
0.003, 0.003
0.003, 0.003
0.000, 0.000
0.005, 0.039
0.000, 0.000
0.005, 0.039
0.005, 0.039
s
6
R
5 short
0.010, 0.010
0.209, 0.305
0.003, 0.004
0.003, 0.003
0.208, 0.304
5.000, 5.000
0.030, 0.043
5.000, 5.000
5.000, 5.000
s
7
R
5
=
10 k
0.010, 0.010
0.000, 0.000
0.010, 0.010
0.010, 0.010
0.000, 0.000
0.017, 0.020
0.000, 0.000
0.017, 0.020
0.017, 0.020
s
8
R
7 open
0.010, 0.010
0.002, 0.002
0.007, 0.008
0.007, 0.008
0.002, 0.002
0.027, 0.045
0.000, 0.000
0.027, 0.045
0.027, 0.045
s
9
R
8 open
0.010, 0.010
0.071, 0.096
0.007, 0.008
0.007, 0.008
0.071, 0.096
5.000, 5.000
0.011, 0.015
5.000, 5.000
5.000, 5.000
s
10
R
9 short
0.010, 0.010
0.076, 0.101
0.007, 0.008
0.007, 0.008
0.076, 0.101
0.003, 0.004
0.011, 0.016
0.003, 0.004
0.003, 0.004
s
1
1
R
9 open
0.010, 0.010
0.014, 0.019
0.007, 0.008
0.007, 0.008
0.014, 0.019
0.005, 0.008
0.000, 0.000
0.005, 0.008
0.005, 0.008
s
12
R
11 short
0.010, 0.010
0.073, 0.098
0.007, 0.008
0.007, 0.008
0.073, 0.098
0.011, 0.015
0.011, 0.015
0.003, 0.004
0.011, 0.015
s
13
C
1 open
0.001, 0.001
0.001, 0.001
0.001, 0.001
0.001, 0.001
0.001, 0.001
0.086, 0.124
0.000, 0.000
0.086, 0.124
0.086, 0.124
s
14
C
2 open
0.010, 0.010
0.364, 0.466
0.008, 0.008
0.008, 0.008
0.003, 0.004
0.332, 0.462
0.000, 0.001
0.332, 0.462
0.332, 0.462
s
15
C
3 open
0.010, 0.010
0.002, 0.002
0.010, 0.010
0.002, 0.003
0.002, 0.002
0.196, 0.254
0.000, 0.000
0.196, 0.254
0.196, 0.254
s
16
C
4 open
0.010, 0.010
0.006, 0.009
0.010, 0.010
0.010, 0.010
0.006, 0.009
0.806, 1.074
0.001, 0.001
0.085, 0.147
0.806, 1.074
s
17
C
5 open
0.010, 0.010
0.216, 0.272
0.008, 0.008
0.008, 0.008
0.216, 0.272
0.242, 0.330
0.214, 0.269
0.242, 0.330
0.242, 0.330
s
18
C
6 open
0.010, 0.010
0.051, 0.071
0.008, 0.009
0.008, 0.009
0.051, 0.071
5.000, 5.000
0.007, 0.011
5.000, 5.000
0.518, 0.759Figure 8
Negative feedback amplifier.By using the proposed test points selection algorithm, the expanded graph is obtained and shown in Figure9. The algorithm was executed for three iterations. Test points {
t
6
,
t
3
,
t
8
} used on the path from the target node to root node S are the final solution. The computation time of this example is 0.08 second.Figure 9
Expanded graph.The integer-coded results of this example are show in Table11. It can be seen that faults in set {
s
1
,
s
5
,
s
13
} have the same code “111112122”, and the code for faults {
s
2
,
s
7
,
s
8
} is “212212122”. Hence, the integer-coded technique will induce a wrong conclusion that faults s
1, s
5, s
13, s
2, s
7, and s
8 are not distinguishable.Table 11
Integer-coded table.
t
1
t
2
t
3
t
4
t
5
t
6
t
7
t
8
t
9
s
0
2
2
2
2
2
4
1
4
4
s
1
1
1
1
1
1
2
1
2
2
s
2
2
1
2
2
1
2
1
2
2
s
3
1
1
1
1
1
1
1
1
1
s
4
2
2
2
2
2
3
1
3
3
s
5
2
1
1
1
1
2
1
2
2
s
6
2
4
1
1
4
7
3
7
6
s
7
2
1
2
2
1
2
1
2
2
s
8
2
1
2
2
1
2
1
2
2
s
9
2
3
2
2
3
6
2
6
5
s
10
2
3
2
2
3
1
2
1
1
s
1
1
2
2
2
2
2
2
1
2
2
s
12
2
3
2
2
3
2
2
1
2
s
13
1
1
1
1
1
2
1
2
2
s
14
2
5
2
2
1
2
1
2
2
s
15
2
1
2
1
1
2
1
2
2
s
16
2
2
2
2
2
4
1
2
4
s
17
2
4
2
2
4
2
4
2
2
s
18
2
3
2
2
3
5
2
5
3Example 4 (statistical experiment 1).
In the former three examples, the proposed heuristic graph search algorithm can always find the minimum test points set while the integer-coded technique usually induces wrong conclusion. To statistically check the accuracy of the proposed approach, it is examined on randomly computer-generated fault dictionary. Besides, for comparison, integer-coded technique based exhaustive method is examined too on the same dictionary.Totally, there are 100 fault dictionaries and each dictionary has 40 simulated faults. To ensure that the integer-coded technique based method can steadily find the solution, 100 test points are contained in every dictionary. For each faults, there are 1000 fault voltages. The voltages are real numbers which can vary between −10.00 volt and 10.00 volt. These voltages follow normal distribution. First, the proposed algorithm is carried out on the randomly generated fault dictionaries. Then these dictionaries are transformed into integer-coded tables, and the exhaustive algorithm is used to select the optimum solution. Table12 lists the results.Table 12
Statistical experimental results.
Size of the min. set
Integer-coded table basedexhaustive algorithm
Proposed method
3
—
3
4
—
16
5
—
27
6
—
35
7
—
11
8
—
8
9
—
—
10
—
—
11
—
—
12
35
—
13
47
—
14
12
—
15
6
—
Computation timeper dictionary (Unit: s)
0.5
0.9From this table, if the proposed method is adopted, 100 simulated fault dictionaries (100% of the simulated cases) need no more than 8 test points to isolate all faults. Unfortunately, if the integer-coded table technique and the exhaustive algorithm are used, the sizes of final solutions are all larger than 11. It means that these solutions contain at least four redundant test points. Therefore the proposed test points selection algorithm has very high accuracy. Although the execution time of the proposed algorithm is greater than the integer-coded table technique, since we do not execute the algorithm in real-time, but rather do it offline, the proposed algorithm is still a computationally viable algorithm. For example, the executing time for a100
×
1000
×
40 fault dictionary is only about 1 second.Example 5 (statistical experiment 2).
It should be pointed out that the more Monte-Carlo simulations are run, the more accurate the result is. Too few simulations usually lead to a wrong result. However, it can also induce a correct result. Take the first column voltages shown in Table2, for example. If only this Monte-Carlo simulation is executed for each fault, we can conclude that all faults are distinguishable except for s
3 and s
7. It can be seen from the second column of Table 6 that these two faults can be distinguished by test point t
3. Hence, t
1 and t
3 are final solution derived by one Monte-Carlo simulation. This result is the same as that derived from ten simulations (see Example 1).Usually, to ensure the robust of the proposed method, as many Monte-Carlo simulations as possible should be executed. However, the simulation time is another consideration. We need to find a tradeoff between the simulation number and the result accuracy. Whether the selected test points setT
opt is accurate or not can be evaluated by following method.Step 1.
Standard faulty voltages matrixU construction: the tolerance is not considered; the faulty voltage of s
i on the selected test points is simulated and saved in vector u
i
→
=
(
u
i
1
,
u
i
1
,
…
,
u
i
|
T
opt
|
). After all fault are simulated, the faulty voltages are save in
(14)
U
=
[
u
1
→
u
2
→
⋮
u
|
S
|
→
]
.Step 2.
Monte-Carlo simulation: for each fault case, the simulation number is set toN
=
1000. During each simulation, the fault free components vary within the predefined tolerance. Totally, there are |
S
|
×
N simulations. The simulated results are saved in
(15)
U
f
=
[
u
f
1,1
→
u
f
1,2
→
⋯
u
f
1
,
N
→
u
f
2,1
→
u
f
2,2
→
⋯
u
f
2
,
N
→
⋮
⋮
⋮
⋮
u
f
|
S
|
,
1
→
u
f
|
S
|
,
2
→
⋯
u
f
f
|
S
|
,
N
→
]
.Step 3.
Fault diagnosis: variablew is initialized to 0. For any vector u
f
i
,
j
→ in U
f, there must be k, which minimize the distance between the two vectors u
f
i
,
j
→ and u
k
→; that is, k
=
arg
min
⁡
k
(
|
u
k
→
-
u
f
i
,
j
→
|
). If k
=
i, the fault diagnosis result is right and w
=
w
+
1.Step 4.
By using the selected test points setT
opt, the fault diagnosis accuracy is P
w
=
w
/
(
|
S
|
×
N
)
×
100
%.To statistically find the minimum number of Monte-Carlo simulations required to have meaningful results correlated to circuit complexity and when probability and conditioned probability assessment gain a reasonable degree of accuracy, the proposed method is examined on various computer-generated fault dictionary. Five fault dictionaries with 10, 50, 75, 100, 500, 750, and 1000 fault sources are examined separately. Each fault in every dictionary is simulated for 10, 50, 75, 100, 500, 750, and 1000 times separately. Hence, there are 7 × 7 = 49 fault dictionaries. 100 test points are contained in every dictionary. The voltages are real numbers which can vary between −10.00 volt and 10.00 volt. These voltages follow normal distribution. Then, for every fault dictionary, the proposed method is used to find the optimal test point sets. Thirdly, the accuracy of the selected test point sets are evaluated by the method proposed in this section. The results are shown in Figure10. In this figure, the x-axis represents the number of faults contained in the CUT, the y-axis represents the number of Monte-Carlo simulations used to select the test points set, and the z-axis shows the fault diagnosis accuracy P
w by using the selected test points.Figure 10
Test point sets evaluation results.It can be seen from this figure that if the number of Monte-Carlo simulations is fewer than 10, the fault diagnosis accuracy is very low. Take the dictionary with 10 fault sources, for example, the fault diagnosis accuracyP
w
=
50
%. Additionally, the fault diagnosis accuracy decreases to P
w
=
10
% when the fault source number increases to 1000. With the incensement of simulation number, by using the selected test points, the fault diagnosis accuracy increases dramatically. In particular, if the number of Monte-Carlo simulations is not fewer than 500, no matter how many faults are examined (the number of the fault case represents the complexity of the CUT), the fault diagnosis accuracy is greater than 90%. Take the 1000 faults dictionary, for example. P
w
=
91
%. When the number of simulations is 1000, fault diagnosis accuracy is greater than 97% for all the simulated dictionary.The simulated results show that for a moderate CUT (the faults number no more than 1000), 500 Monte-Carlo simulations are enough to achieve meaningful results. 1000 Monte-Carlo simulations can achieve a very high accurate result. Under these conditions, probability and conditioned probability assessment proposed in this paper gain a reasonable degree of accuracy.


## 6. Conclusion

Modern densely loaded circuit boards have posed problems for fault diagnosis with in-circuit testers because only limited physical access to the boards is allowed. Minimum set of test points selection method is, therefore, badly needed to reduce the number of test point. The recently proposed test points selection algorithms are based on the integer-coded faultwise table technique. Unfortunately, according to the illustration presented in Section1 and examples in Section 5, the integer-coded table technique usually leads to a wrong conclusion and is not applicable to moderate table; let alone large dictionary. Based on these considerations, the main contributions of this paper are listed as follows.(i)
The tolerance problem is thoroughly tackled: this contribution ensures that the fault sources can be pinpointed by using the selected points under the tolerance influence.
(ii)
Simulation based method is proposed to find the dependence relationship of faulty voltages on different test points/or different measurements, and the mapping relationship is established in turn. This method can dramatically decrease the number of test points.
(iii)
The test points selection process is transformed into a heuristic graph search problem. Entropy-based method is proposed to evaluate the optimization of graph node. Hence, the test points selection process is optimized.The proposed algorithm is succinct and applied. It is easy to program and execute. Its accuracy is proved by theoretical analysis and statistical experiments. Hence, it is specially fit for engineering application. Additionally, the proposed method can also be used to select optimum measurements and frequencies in analog fault diagnosis.



---

*Source: 259430-2014-02-23.xml*