# Antirandom Testing: A Distance-Based Approach

Authors: ShenHui Wu; Sridhar Jandhyala; Yashwant K. Malaiya; Anura P. Jayasumana
Journal: VLSI Design
 (2008)

---

## Abstract

Random testing requires each test to be selected randomly regardless of the tests previously
applied. This paper introduces the concept of antirandom testing where each test applied is
chosen such that its total distance from all previous tests is maximum. This spans the test
vector space to the maximum extent possible for a given number of vectors. An algorithm
for generating antirandom tests is presented. Compared with traditional pseudorandom testing,
antirandom testing is found to be very effective when a high-fault coverage needs to be
achieved with a limited number of test vectors. The superiority of the new approach is even
more significant for testing bridging faults.


---

## Body

## 1. Introduction

Random  testing is a form of black-box testing which
does not  require knowledge of the circuit under
test. It avoids the problem of deterministic test generation using
structural information about the circuit under test. Available
evidence suggests that pseudorandom testing may be a reasonable
choice for obtaining a moderate degree of confidence, however it
becomes inefficient when only hard-to-test faults remain [1]. Generally in BIST environment,
pseudorandom test vectors are used for testing digital circuits. In
pseudorandom testing, each test vector is chosen with equal
probability out of a pool that initially contains M different
vectors without replacement [2]. A
common approach is to generate them using an autonomous linear
feedback shift register (ALFSR) based on a primitive polynomial
[3]. An alternative approach is to
use a cellular automata-based generator [4, 5]. The use of Galois
LFSRs (GLFSRs) as test pattern generators for BIST schemes employing
multiple scan chains is investigated in [6, 7]. The effectiveness of
such techniques can be enhanced by using some information about the
circuit under test and tailoring the generator hardware to achieve
higher coverage faster [8]. Weighted
random pattern techniques adjust the probability generating 1's and
0's at each input, rather than using equal probabilities. Such an
approach has been shown to increase efficiency of testing,
especially for modules such as PLAs [9]. In some cases test generation for self-testing may be
implemented in software [10].Pseudorandom testing does not exploit some information
that is available in black-box testing environment. This information
consists of the previous tests applied. If an experienced test
engineer is generating tests by hand, he would select each new test
such that it covers some part of the functionality not yet covered
by tests already generated. The objective of this paper is to
formally define a black-box approach that uses this information, and
to propose schemes that may allow such test generation to be done
automatically. We term this approachantirandom
testing, since selection of each test explicitly depends on the
tests already obtained. This technique can potentially be used in
place of the traditional pseudorandom testing.In Section2 we define and
characterize the antirandom test patterns. A procedure for
generating antirandom tests is described. Then we compare
pseudorandom and antirandom strategies by
evaluating their effectiveness for ISCAS benchmark circuits. Both
stuck-at and bridging faults are considered.


## 2. Binary Antirandom Sequences

Antirandom testing [11] is a
black-box strategy like pseudorandom testing, meaning that it
assumes no information about the internal implementation of the
circuit. However, it explicitly uses information about the past
vectors applied for generating a new vector. Here we start with
formal definitions of the terms used and then examine construction
of antirandom sequences.Deffinition 1.
Antirandom test sequence (ATS) is a test
sequence in which a testti is chosen such
that it satisfies some criterion with respect to all tests
t0,t1,…,ti−1 applied before.
In this paper we use two specific criteria based on the
distance concept introduced below.Deffinition 2.
Distance is a measure of how different two
vectorsti and tj are. Here we
use two measures of distance defined below.Deffinition 3.
Hamming distance (HD) [12] is the number of bits in
which two binary vectors differ. It is not defined for vectors
containing continuous values.Deffinition 4.
Cartesian distance (CD) between two
vectors,A={aN,aN−1,…,a1,a0} and B={bN,bN−1,…,b1,a0}, is given by(1)CD(A,B)=(aN−bN)2+(aN−1−bN−1)2+…+(a0−b0)2.
Since the two test vectors are binary, then (1)
can be written as(2)CD(A,B)=|aN−bN|+|aN−1−bN−1|+…+|a0−b0|=HD(A,B).Deffinition 5.
Total Cartesian distance (TCD) for any
vector is the sum of its Cartesian distances with respect to all
previous vectors. We refer to the total distance when Hamming and
Cartesian distances are used by THD(ti) and TCD(ti),
respectively.Deffinition 6.
Maximal distance antirandom test sequence (MDATS) is a test sequence such that each testti is chosen to
make the total distance between ti and each of t0,t1,…,ti−1 maximum, that
is,(3)TD(ti)=∑j=0i−1D(ti,tj)is maximum for all possible
choices of ti.Deffinition 7.
Maximal Hamming distance antirandom test sequence (MHDATS) a MDATS
that uses Hamming distance as the distance measure.Deffinition 8.
Maximal Cartesian distance antirandom test sequence (MCDATS)  a
MDATS that uses Hamming distance as the distance measure.For functional testing, we have no structural
information available about the actual circuit implementation. Using
maximal distance criterion, every time we attempt to find a test
vector as different as possible from all previously applied vectors.
The antirandom testing scheme thus attempts to keep testing as
efficient as possible. In this approach, we are using the hypothesis
that if two input vectors have only a small distance between them,
then the sets of faults encountered by the two are likely to have a
number of faults in common. Conversely, if the distance between two
vectors is large, then the set of faults detected by one is likely
to contain only a few of the faults detected by the other. Extensive
evaluation of Torino benchmarks for fault coverage in [13] has confirmed this hypothesis to be
valid for all the benchmarks tested.If testing is less than exhaustive, then maximum
distance antirandom testing (MDAT) is likely to be more efficient
than either random or pseudorandom testing. Even when exhaustive
testing is feasible, MDAT is likely to detect the presence of faults
earlier.Procedure 1. Construction of a MHDATS (MCDATS)
Step 1.
For each ofN input variables, assign an arbitrarily chosen value to obtain the
first test vector. This does not result in any loss of
generality.Step 2.
To obtain
each new vector, evaluate the THD (TCD) for each of the remaining
combinations with respect to the combinations already chosen and
choose one that gives maximal distance. Add it to the set of
selected vectors.Step 3.
Repeat Step2 until all 2N combinations
have been used, or until the desired number of vectors have been
generated.This procedure uses exhaustive search. As we will see
later, the computational complexity can be greatly reduced. Note
that the procedure ensures that a vector will not be repeated.To illustrate the process of generating MDATS, we
consider in detail the generation of a complete sequence for three
binary variables.Example 9.
Consider a system with three
inputs{x,y,z}. We will illustrate the generation of MHDATS using a
cube with each node representing one input combination.Let us start with the input{0,0,0}. This does not
result in any loss of generality as the procedure can easily be used
for sequences starting with any vector. As we will see later, the
polarity of any variable can be inverted. The next vector t1 of the MHDTS is
obviously {1,1,1} with THD(t1)=3. At this
point, the situation is shown in Figure 1(a), where the input
combinations already chosen are marked.Construction of 3-bit MHDATS.
(a)(b)(c)As can be visually seen, a symmetrical situation
exists now. Any vector chosen would have HD = 1 from one of the past
chosen vectors and HD = 2 from the others. If we allow the variables
to be reordered, then without any loss of generality we have the
following choices:(4)t0={0,0,0};t1={1,1,1};THD=3;t2={0,1,0};THD=3ort2={1,0,1};THD=3.Let us consider the first choice. Aftert2={1,0,1}, the
clear choice for t3 is {1,0,1} at the
opposite corner of the cube. The situation now is shown in Figure 1(b).Again a symmetrical situation exists. Any one of the
remaining vectors have the same relationship with the set of vectors
already chosen. Let us pick{1,0,0} as t4. The next vector t5 then has to be
{0,1,1} at the opposite corner of the cube. We can again choose any
one of two remaining vectors as shown in Figure 1(c). Let us choose
t6={1,1,0} which
leaves t7={0,0,1}. The
complete MHDTS obtained here is given as sequence 1 in Table 1.Table 1
3-bit MHDTS.
TestxyzTHDTCDt00 0 0——t11 1 131.7320t20 1 032.4142t31 0 164.146t41 0 064.8284t50 1 196.5604t61 1 097.2426t70 0 1128.9746In this example, it is easy to see that with our
chosen vectors fort0,t1 and the two
choices for t2, we could have constructed 16 distinct MHDATSs using
all of the later choices available. We can verify that all of these
are also MCDATSs.A MCDATS needs to satisfy a more strict requirement
than a MHDATS, for example,t0={0,0,0,0},t1={1,1,1,1},t2={0,0,0,1}, is a MHDATS but not a MCDATS. If we replace t2 by {0,1,0,1} with
equal number of 1's and 0's, it would be a MCDATS.A large number of experiments with construction of
MHDATSs and MCDATSs have been done. Based on these, the following
results can be stated [11].Deffinition 9.
If a sequence B is obtained by
reordering the variables of sequence A, then B is avariable-order-variant (VOV) of A.Deffinition 10.
If a sequence B is obtained by
complementing some of the variables of sequence A, then B is apolarity-variant (PV) of A.Theorem 1.
If a sequence B is a
variable-order variant of a MHDATS (MCDATS) A, then B is also a
MHDATS (MCDATS).Proof.
Note that Hamming or Cartesian distance is
independent of how the variables are ordered. Thus, a variable-order
variant of a sequence will exhibit the same distance
properties. Hence,
if a sequence B is variable-order variant of a MHDATS (MCDATS) A,
then B is also a  MHDATS (MCDATS) .Theorem 2.
If a sequence B is a polarity
variant of a MHDATS (MCDATS) A, then B is also MHDATS (MCDATS).Proof.
For a pair of vectors, the distance remains the
same if the same set of variables in both vectors is
complemented. Thus, a polarity variant of a sequence will exhibit
the same distance properties. Hence, if a sequence B is polarity
variant of a MHDATS (MCDATS) A, then B is also a MHDATS
(MCDATS) .Theorem 3 (See [11]).
A MHDATS (MCDATS) will always contain
complementary pairs of vectors, that is,t2k will always be
followed by t2k+1 which is
complementary for all bits in t2k where k=1,2,….Proof.
The first two vectorst0 and t1 will always be
a complementary pair. Below we will show that if the vectors
t0, t1,…,t2k−1 are
complementary pairs, then the vectors t2k and t2k+1 will also be a
complementary pair. Thus t2 and t3, hence t4 and t5, and so on, will all be complementary paris.
Let us assume a MHDATS contains an even number of
vectors,t0,t1,…,t2k−2,t2k−1, such that a vector with an odd subscript is a
complement of the preceding vector. Let us now assume that a vector
t2k is found such
that its total Hamming (Cartesian) distance from all of t0,…,t2k−1 is maximal.
If we change the polarity of all the variables, we get
the sequencet0¯,t1¯,…,t2k−2¯,t2k−1¯,t2k¯, where ti¯ indicates
complement of ti. By Theorem 2, this is also a MHDATS (MCDATS). Now
since t1¯=t0, t0¯=t1, and so on, the partial sequence t0¯,t1¯,…,t2k−2¯,t2k−1¯ contains the
same vectors as t0,t1,…,t2k−2,t2k−1 but in a
different order. Thus, t2k¯ has the same
total Hamming (Cartesian) distance as t2k with respect to t0,t1,…,t2k−2,t2k−1.
Now after having constructed the MHDATS (MCDATS)t0,t1,…,t2k−2,t2k−1,t2k, the addition of t2k+1¯=t2k will keep it a
MHDATS (MCDATS) because
(1)
t2k¯ provides the
maximal total HD (CD) with respect to {t0,t1,…,t2k−2,t2k−1};(2)
t2k¯ also provides
the maximal HD (CD) with respect to t2k.The following procedures can be used to construct
MHDATS (MCDATS) for a larger number of variables starting with
MHDATS (MCDATS) for a smaller number of variables.Procedure 2. Expansion of MCDATS (MCDATS)
Step 1.
Start
with a complete MHDATS ofN variables, XN−1,XN−2,…,X1,X0.Step 2.
For
each vectorti, i=0,1,…,(2N−1), add an
additional bit corresponding to an added variable XN, such that ti has the maximum
total HD (CD) with respect to all the previous vectors.Procedure 3. Expansion and Unfolding of a MHDATS (MCDATS)
Step 1.
Start with a complete(N−1) variable MHDATS
(MCDATS) with 2N−1 vectors.Step 2.
Expand by adding a variable using Procedure 2. We now have the first (2N/2) vectors
needed.Step 3.
Complement one of the columns and append the
resulting vectors to the first set of vectors obtained in Step2.
Here, it would be convenient to complement the variable added in
Step 2.The above procedures have been implemented in a
program called ATG [14]. It generates
MCDATSs which are also MHDATSs. The application of antirandom
testing for software has been reported in [15]. Three related approaches termed fast
antirandom [16],
random-like [17] and
maximum distance [18] testing have recently been proposed that attempt to
incorporate some of the features of antirandom sequences.A psuedorandom test sequence attmpts to achieve
randomness. However, Pradhan and Chatterjee [19] have shown that LFSR-based sequences fail many of the
tests used to measure randomness. An antirandom test sequence
attempts to span the input space by applying inputs that are as
different as possible [16, 20]. It does it by being deliberately
nonrandom. Let us compare the first 30 test patterns for 14-input
sequences generated using antirandom property and conventional
pseudorandom tests, as given in Table 2. Pseudo0 and Pseudo2 represent the pseudorandom
sequences starting with the seeds 00000000000000 and 01010101010101,
respectively. The successive vectors in the time sequence are listed
sequentially. A more visual representation is given in Figure 2. A black pixel indicates value 0, while
the white pixel indicate value 1. The time progresses from top to
bottom for each bitmap.Table 2
Comparison of randomness: antirandom versus Pseudorandom.
AntirandomPseudo0Pseudo20000000000000000000000000000010101010101011111111111111110000000000000001010101010100101010101010111000000000000100101010101011010101010101011100000000000110010101010100011001101100011110000000000011001010101011100110010011111111000000000001100101010100110011000110111111100000000100110010101011001100111001011111110000000110011001010100001111001001111111111000000011001100101011110000110110011111111100000001100110010100100101100011011111111110000100110011001011011010011100111111111111000110011001100100010110101111001111111111100111001100110011101001010000100111111111110111100110011000011110000010110001111111111111111001100110100001111101001000111111111101111100110011000011111010010100011111111110111110011001111100000101101010001111111111011111001100010110101111000101000111111111101111100110101001010000111010100011111101110111110011001111001001000101010001111110111011111001110000110110111010101000111111011101111100011010011100010101010100011111101110111110100101100011100010101010001111110111011111000100011011111001010101000101111011101111111011100100000100101010100010111101110111010001001110101010010101010011011110111011101110110001010101001010101011101111011101001000101101111010100101010101110111101110110111010010001101010010101010111011111001Figure 2
State-time diagrams of antirandom, pseudorandom pattern generator.


## 3. Effectiveness of Antirandom and Pseudorandom Testing

To compare the effectiveness of antirandom sequences with
pseudorandom tests generated using linear feedback shift registers
(LFSRs), a series of experiments has been performed. We have
measured the effectiveness of a test set using two coverage
measures. Thestuck-at 0/1 coverage is the ratio of
the number of stuck-at faults detecteded to the total number of
faults. Some faults may be undetectable. We have also evaluated the
bridging-fault coverage in the IDDQ test
environment. A bridging fault is assumed to be detected if the two
nodes have opposite logic values, because in such a case a very high
quiescent supply current would indicate the presence of a fault.The basic characteristics of the ISACAS85
combinational circuit used in the study are given in Table3. It lists the detail information such
as the number of inputs and outputs, number of gates, the circuit
function, and the total number of stuck-at faults.Table 3
Characteristic of simulated combinational circuits.
CircuitNumber of inputsNumber of outputsNumber of gatesTotal linesFanout stemCircuit functionTotal stuck-at faultsTotal bridging faultsc8806026383880125ALU and control9423254c3540502216693540579ALU and control342816459c135541325461355259ECAT15744422c499413220249959ECAT7582781


### 3.1. Testing Combinational Circuits for Stuck-at Fault

A pseudorandom test generator will generate different sequences
depending on the seed used, and thus different seeds will yield
different results. To see the variation in coverage due to the
choice of the seed value, three different seed values were used for
the pseudorandom test generator.We have simulated several ISCAS85 combinational
benchmark circuits using Nemesis, a software tool developed at
University of California, Santa Cruz [21].Figures3 and 4 show the stuck-at fault coverage
obtained by the test sequence generators for the circuits C880 and
C3540. In these plots, the x-axis represents the number of the test
patterns, and the y-axis fault coverage. Tables 4, 5, 6, 7 show the
fault coverage for different number of test patterns for c880,
c3540, c1355, and c499, respectively, with two digits after the
decimal point. Note that the Pseudo0, Pseudo1, and Pseudo2 in the
figures and plots represent the different initial seeds for
pseudorandom generator which are all zeros (000000…), all ones
(111111…), and alternating bits (101010…).Table 4
Stuck-at fault coverage for c880.
Test no.1510205075100200Antirandom8.9142.9967.4676.8685.5688.6490.8795.01Pseudo08.919.8712.6322.2937.1540.1344.9081.95Pseudo110.9313.5915.3916.2442.1258.4966.4582.27Pseudo229.9440.5544.5946.3965.8171.6673.4688.21Table 5
Stuck-at fault coverage for c3540.
Test no.1510205075100200Antirandom14.2134.9847.7863.8575.3280.0683.5087.51Pseudo014.2117.2120.2126.2251.7860.1866.2483.43Pseudo18.6628.5630.6632.7053.2560.7966.7183.51Pseudo211.8433.1136.9841.3656.7467.0070.8584.48Table 6
Stuck-at fault coverage for c1355.
Test no.1510205075100200Antirandom8.1334.1853.6272.2380.6287.0388.4392.56Pseudo08.1332.9137.0444.6674.1481.8985.1391.48Pseudo114.7436.5945.4359.0875.4783.7988.6292.12Pseudo29.1446.9548.8660.4878.9083.5486.5991.42Table 7
Stuck-at fault coverage for c499.
Test no.1510205075100200Antirandom12.6649.3469.9284.0388.1292.3593.4097.22Pseudo012.6647.8953.3060.8184.9689.7192.6196.30Pseudo122.1648.4257.2668.3384.8289.8493.0096.17Pseudo212.6664.5167.2876.9186.9388.1891.5596.59Figure 3
C880 stuck-at fault coverage simulation.Figure 4
C3540 stuck-at fault coverage simulation.For c880 (Figure3), we observe that antirandom tests
perform well, obtaining 90.87% coverage for 100 vectors. The fault coverage
curve rises sharply and exhibits a smooth behavior. In case of
pseudorandom tests, there is a significant difference depending on
the initial seed, the
coverage obtained with 100 vectors ranges from 44.90% to 73.76%. For all three
seeds, pseudorandom tests significantly lag in performance compared
with antirandom tests. We also observe that the plots for
pseudorandom tests show somewhat irregular growth. The plot for
c3540 (Figure 4) shows that antirandom testing is again the best,
the difference between it and pseudorandom testing
is most pronounced at about 70% coverage. Similar observations can be made for
c1355 and c499 (Tables 6 and 7).The results show that(1)
the antirandom
sequences generally provide higher coverage than pseudorandom
testing;(2)
the new test
pattern generation scheme can obtain a high-fault coverage with
significantly fewer test patterns compared to pseudorandom
testing;(3)
for
pseudorandom testing, the effectiveness can depend on the initial
seed chosen.These results show that the proposed scheme exercises
the circuits under test better because it spans the test vector
space better than pseudorandom testing.


### 3.2. Testing Combinational Circuit for Bridging Faults

A bridging fault is a short between two nodes in a
circuit. We have applied the new test pattern generation scheme to
test bridging faults in the four ISCAS benchmark circuits. The
bridging faults are identified by Carafe [22] by considering the layout information. Nemesis assumes
that a bridging fault is being tested in the IDDQ test environment.
If the two bridged nodes have opposite logic values, then the
bridging fault will cause a high value of IDDQ thus detecting the
fault.Figures5 and 6 give the fault coverages obtained for
the circuits c880 and c3540 for different schemes. Tables 8, 9, 10,
11 list the fault-coverage values for specific number of test
patterns for the four circuits.Table 8
Bridging fault coverage for c880.
Test no.1510205075100200Antirandom10.2662.5585.6993.297.3798.2498.9598.95Pseudo010.2617.4626.8439.465.9769.2772.1695.29Pseudo115.6025.0529.6933.9158.7876.1685.1995.10Pseudo225.8453.460.1464.1285.590.7291.3797.71Table 9
Bridging fault coverage for c3540.
Test no.1510205075100200Antirandom16.5760.4678.1888.5595.1796.2297.4798.67Pseudo016.5728.0529.0942.4171.3885.4689.3497.68Pseudo118.5224.9631.9341.6981.4890.7494.8897.94Pseudo222.3444.5557.2565.5586.3790.5793.3896.75Table 10
Bridging fault coverage for c1355.
Test no.1510205075100200Antirandom10.8359.6682.5592.5996.8497.3197.7698.10Pseudo010.8345.2359.0178.8693.2395.9796.9298.05Pseudo118.2931.2757.2779.9395.2496.9797.7398.48Pseudo224.8851.384.8688.7196.0596.0397.4698.42Table 11
Bridging fault
coverage for c499.
Test no.1510205075100200Antirandom4.5271.0984.6291.3797.1598.5599.5299.76Pseudo04.5237.9863.0477.4896.6298.2198.9199.52Pseudo118.7745.6268.8685.5298.4599.2199.7299.81Pseudo231.3454.5063.4087.0797.8898.3599.4299.68Figure 5
C880 bridging fault coverage.Figure 6
C3540 bridging fault coverage.Figure5 for c880 shows that the difference between
the proposed approach and the traditional pseudorandom testing is
quite remarkable. Furthermore with antirandom sequences, the
coverage of bridging faults rises much faster than that for stuck-at
faults. The gap between the curves for the new approaches and
pseudorandom testing is wider for bridging faults. The same behavior
is observed for other three circuits [23]. For example, we can consider the number of vectors
needed to obtain a stuck-at coverage of about
90% using the new approach. For c880 for the same number of vectors (about
100), pseudorandom vectors obtain coverage values of 44.90 for
Pseudo0 to 73.46
for Pseudo2, that is, about 19–50% less. For bridging faults, for about the
same level of coverage, this difference between antirandom and
pseudorandom
coverage for c880 widens to 31–63%. The similar gaps for c3540 widens from 3-4%
to 25–52%, for c1355 from about 0–3 to 4–14%, and for c499 from 0–5% to 4–15%.
This makes the proposed schemes suitable for generating tests for
bridging faults in the IDDQ test environment. Using a very few
vectors, very high coverage for bridging faults can be achieved.An explanation for this improvement can be found by
observing the fact that different inputs are toggled relatively
independently with the proposed schemes, making it more likely that
any two nodes will have opposite logic values.


## 3.1. Testing Combinational Circuits for Stuck-at Fault

A pseudorandom test generator will generate different sequences
depending on the seed used, and thus different seeds will yield
different results. To see the variation in coverage due to the
choice of the seed value, three different seed values were used for
the pseudorandom test generator.We have simulated several ISCAS85 combinational
benchmark circuits using Nemesis, a software tool developed at
University of California, Santa Cruz [21].Figures3 and 4 show the stuck-at fault coverage
obtained by the test sequence generators for the circuits C880 and
C3540. In these plots, the x-axis represents the number of the test
patterns, and the y-axis fault coverage. Tables 4, 5, 6, 7 show the
fault coverage for different number of test patterns for c880,
c3540, c1355, and c499, respectively, with two digits after the
decimal point. Note that the Pseudo0, Pseudo1, and Pseudo2 in the
figures and plots represent the different initial seeds for
pseudorandom generator which are all zeros (000000…), all ones
(111111…), and alternating bits (101010…).Table 4
Stuck-at fault coverage for c880.
Test no.1510205075100200Antirandom8.9142.9967.4676.8685.5688.6490.8795.01Pseudo08.919.8712.6322.2937.1540.1344.9081.95Pseudo110.9313.5915.3916.2442.1258.4966.4582.27Pseudo229.9440.5544.5946.3965.8171.6673.4688.21Table 5
Stuck-at fault coverage for c3540.
Test no.1510205075100200Antirandom14.2134.9847.7863.8575.3280.0683.5087.51Pseudo014.2117.2120.2126.2251.7860.1866.2483.43Pseudo18.6628.5630.6632.7053.2560.7966.7183.51Pseudo211.8433.1136.9841.3656.7467.0070.8584.48Table 6
Stuck-at fault coverage for c1355.
Test no.1510205075100200Antirandom8.1334.1853.6272.2380.6287.0388.4392.56Pseudo08.1332.9137.0444.6674.1481.8985.1391.48Pseudo114.7436.5945.4359.0875.4783.7988.6292.12Pseudo29.1446.9548.8660.4878.9083.5486.5991.42Table 7
Stuck-at fault coverage for c499.
Test no.1510205075100200Antirandom12.6649.3469.9284.0388.1292.3593.4097.22Pseudo012.6647.8953.3060.8184.9689.7192.6196.30Pseudo122.1648.4257.2668.3384.8289.8493.0096.17Pseudo212.6664.5167.2876.9186.9388.1891.5596.59Figure 3
C880 stuck-at fault coverage simulation.Figure 4
C3540 stuck-at fault coverage simulation.For c880 (Figure3), we observe that antirandom tests
perform well, obtaining 90.87% coverage for 100 vectors. The fault coverage
curve rises sharply and exhibits a smooth behavior. In case of
pseudorandom tests, there is a significant difference depending on
the initial seed, the
coverage obtained with 100 vectors ranges from 44.90% to 73.76%. For all three
seeds, pseudorandom tests significantly lag in performance compared
with antirandom tests. We also observe that the plots for
pseudorandom tests show somewhat irregular growth. The plot for
c3540 (Figure 4) shows that antirandom testing is again the best,
the difference between it and pseudorandom testing
is most pronounced at about 70% coverage. Similar observations can be made for
c1355 and c499 (Tables 6 and 7).The results show that(1)
the antirandom
sequences generally provide higher coverage than pseudorandom
testing;(2)
the new test
pattern generation scheme can obtain a high-fault coverage with
significantly fewer test patterns compared to pseudorandom
testing;(3)
for
pseudorandom testing, the effectiveness can depend on the initial
seed chosen.These results show that the proposed scheme exercises
the circuits under test better because it spans the test vector
space better than pseudorandom testing.


## 3.2. Testing Combinational Circuit for Bridging Faults

A bridging fault is a short between two nodes in a
circuit. We have applied the new test pattern generation scheme to
test bridging faults in the four ISCAS benchmark circuits. The
bridging faults are identified by Carafe [22] by considering the layout information. Nemesis assumes
that a bridging fault is being tested in the IDDQ test environment.
If the two bridged nodes have opposite logic values, then the
bridging fault will cause a high value of IDDQ thus detecting the
fault.Figures5 and 6 give the fault coverages obtained for
the circuits c880 and c3540 for different schemes. Tables 8, 9, 10,
11 list the fault-coverage values for specific number of test
patterns for the four circuits.Table 8
Bridging fault coverage for c880.
Test no.1510205075100200Antirandom10.2662.5585.6993.297.3798.2498.9598.95Pseudo010.2617.4626.8439.465.9769.2772.1695.29Pseudo115.6025.0529.6933.9158.7876.1685.1995.10Pseudo225.8453.460.1464.1285.590.7291.3797.71Table 9
Bridging fault coverage for c3540.
Test no.1510205075100200Antirandom16.5760.4678.1888.5595.1796.2297.4798.67Pseudo016.5728.0529.0942.4171.3885.4689.3497.68Pseudo118.5224.9631.9341.6981.4890.7494.8897.94Pseudo222.3444.5557.2565.5586.3790.5793.3896.75Table 10
Bridging fault coverage for c1355.
Test no.1510205075100200Antirandom10.8359.6682.5592.5996.8497.3197.7698.10Pseudo010.8345.2359.0178.8693.2395.9796.9298.05Pseudo118.2931.2757.2779.9395.2496.9797.7398.48Pseudo224.8851.384.8688.7196.0596.0397.4698.42Table 11
Bridging fault
coverage for c499.
Test no.1510205075100200Antirandom4.5271.0984.6291.3797.1598.5599.5299.76Pseudo04.5237.9863.0477.4896.6298.2198.9199.52Pseudo118.7745.6268.8685.5298.4599.2199.7299.81Pseudo231.3454.5063.4087.0797.8898.3599.4299.68Figure 5
C880 bridging fault coverage.Figure 6
C3540 bridging fault coverage.Figure5 for c880 shows that the difference between
the proposed approach and the traditional pseudorandom testing is
quite remarkable. Furthermore with antirandom sequences, the
coverage of bridging faults rises much faster than that for stuck-at
faults. The gap between the curves for the new approaches and
pseudorandom testing is wider for bridging faults. The same behavior
is observed for other three circuits [23]. For example, we can consider the number of vectors
needed to obtain a stuck-at coverage of about
90% using the new approach. For c880 for the same number of vectors (about
100), pseudorandom vectors obtain coverage values of 44.90 for
Pseudo0 to 73.46
for Pseudo2, that is, about 19–50% less. For bridging faults, for about the
same level of coverage, this difference between antirandom and
pseudorandom
coverage for c880 widens to 31–63%. The similar gaps for c3540 widens from 3-4%
to 25–52%, for c1355 from about 0–3 to 4–14%, and for c499 from 0–5% to 4–15%.
This makes the proposed schemes suitable for generating tests for
bridging faults in the IDDQ test environment. Using a very few
vectors, very high coverage for bridging faults can be achieved.An explanation for this improvement can be found by
observing the fact that different inputs are toggled relatively
independently with the proposed schemes, making it more likely that
any two nodes will have opposite logic values.


## 4. Conclusions

Antirandom testing is a new test generation approach.
Here we have demonstrated that it can achieve high-fault coverage
much faster than the conventional pseudorandom testing. It has also
been successfully applied for software testing [15] and testing of VHDL descriptions [24]. Its effectiveness is specially
remarkable for bridging faults. The scheme is well suited for IDDQ
testing because it provides very good coverage with
only a few vectors when black-box testing is used. One possible way
to exploit the capabilities of antirandom testing is to use it until
a suitable high coverage is obtained, and then to switch to
deterministic testing.This paper considers the testing of combinational
blocks. Testing of sequential circuits presents challanges that need
to be considered separately. In DFT approaches, the problem of
testing sequential circuits is converted to the problem of testing
combinational blocks during the test mode. In such cases, antirandom
testing for combinational blocks is still applicable. However,
testing becomes complex if no such DFT approaches are used. Studies
have shown [25] that holding a vector
for a few clock periods can improve coverage. This suggests that
using antirandom testing for sequential circuits
will require the development of special approaches. Such approaches
are currently being researched. One can also envisage circuits for
which clustering of patterns, as opposed to antirandom, may be
beneficial. For example, a vector that sensitizes a long path in the
circuit can be slightly modified to detect many other faults. A
second example is a single AND gate with a large number of inputs.
Most of good tests are clustered around all-1 vector. However,
exploiting such scenarios usually require the use of structural
information about the circuit.The concept of complementary pairs was one of our
contributions as a part of the antirandom concept. While application
of a pattern and its complement [17]
with pseudorandom testing can provide some benefit, antirandom is
more effective due to the fact that it increases the overall Hamming
distance between new vectors in addition to using the complement of
each vector.In this paper, we have considered onlyblack-box testing which assumes that we do
not have any structural information available. It is possible to
generate antirandom sequences that can exploit some structural
information thus further increasing coverage [8, 26]. Further research is
needed to develop techniques that will allow us to do that.



---

*Source: 165709-2008-03-17.xml*