# Test Generation for Crosstalk-Induced Delay Faults in VLSI Circuits Using Modified FAN Algorithm

Authors: S. Jayanthy; M. C. Bhuvaneswari; Keesarapalli Sujitha
Journal: VLSI Design
 (2012)

---

## Abstract

As design trends move toward nanometer technology, new problems due to noise effects lead to a decrease in reliability and performance of VLSI circuits. Crosstalk is one such noise effect which affects the timing behaviour of circuits. In this paper, an efficient Automatic Test Pattern Generation (ATPG) method based on a modified Fanout Oriented (FAN) to detect crosstalk-induced delay faults in VLSI circuits is presented. Tests are generated for ISCAS_85 and enhanced scan version of ISCAS_89 benchmark circuits. Experimental results demonstrate that the test program gives better fault coverage, less number of backtracks, and hence reduced test generation time for most of the benchmark circuits when compared to modified Path-Oriented Decision Making (PODEM) based ATPG. The number of transitions is also reduced thus reducing the power dissipation of the circuit.


---

## Body

## 1. Introduction

As a consequence of technological advances which have resulted in an increase of VLSI chip density, increased number of interconnect layers and in an improvement of timing performances, the test for static stuck-at faults only has turned out to be insufficient, and it is now also required to deal with physical defects which affect the timing behavior of a given circuit. Various noise sources such as crosstalk and power supply noise have a significant impact on the timing performance of Deep Submicron (DSM) designs. The increasing number of transistors in the chip leads to more devices switching simultaneously resulting in power supply noise which reduces device voltage levels and increases signal delay.  Interconnection lines which were assumed to be electrically isolated can now interfere with each other leading to functional problems. One such interaction caused by parasitic coupling between wires is known as crosstalk. These noise effects can cause completely validated chip to malfunction and lead to performance degradation of deep submicron design.There are two main types of crosstalk effects: crosstalk-induced pulses and crosstalk-induced delay. The type of crosstalk effect dealt in this paper is crosstalk-induced delay. Crosstalk delay is induced when two lines, an aggressor line (A-line) and victim line (V-line) have simultaneous or near simultaneous transitions, which may cause undesirable effects including glitches, increase, or decrease in the signal delay [1]. If both the lines transit in the same direction, the effective delay is reduced leading to crosstalk speedup. If aggressor and victim transit in the opposite direction, then there will be an increase in delay leading to crosstalk slowdown.The designer has two options   to eliminate errors caused by crosstalk by resizing drivers, rerouting signals, shielding interconnect lines and other such redesign techniques, or by developing techniques to generate tests for crosstalk.The latter option is often taken by designers as redesign may be very expensive. Moreover, test generation for crosstalk also enables more aggressive design and enables more comprehensive postmanufacturing testing.Energy dissipation has become a major concern in today VLSI technology with increasing use of wireless communication and portable computers. The acceptance of this area of communication and products depends on their power of consumption. Further periodic testing of  VLSI circuits can cause generation of excessive heat which can damage the chips under test. During testing the low correlation between test vectors increases the switching activity in the circuit leading to higher power dissipation than during its normal operation.In CMOS, combinational circuits power dissipation is due the following sources: static power dissipation due to leakage currents and other currents drawn continuously from the power supply, dynamic power dissipation due to switching transient current, and charging and discharging of load capacitances [2]. Unlike bipolar technologies, where a majority of power dissipation is static, the bulk of power dissipation in properly designed existing CMOS digital circuits is due to dynamic power dissipation caused by charging and discharging of capacitances. Thus, a majority of the low power design methodology is dedicated to reducing this predominant factor of power dissipation.However, there are also other components of power dissipation in CMOS circuits like short circuit current power, leakage current power, and static-biasing power. These are negligible when compared with the dynamic power dissipation.The consumed energy directly corresponds to the switching activity generated in the circuit during test application.In this paper, a test generation algorithm using a modified version of FAN (fanout-oriented test generation) algorithm for crosstalk delay faults is presented. The test generator detects crosstalk faults that produce delay affect at the primary output. This algorithm also reduces the number of transitions when compared to PODEM algorithm and thus reduces the power dissipation in CMOS circuits.The remainder of the paper is organized as follows.Section2 discusses prior work. Section 3 describes the algorithm to find the paths in the circuit. Section 4 describes the signal values used in test generation test generation. Section 5 describes the test generation algorithm using a modified version of FAN algorithm, and Section 6 presents the experimental results for ISCAS’85 and enhanced scan version of ISCAS’89 Benchmark circuits. The paper is concluded in Section 7.


## 2. Prior Work

Rubio et al. [3] propose a methodology which is based on a search for a two-vector input pattern that forces a determinate value to the affected nodes and provokes a transition of the affecting lines allowing the propagation of the possible noise effect to the primary output nodes. The relationship of transition propagation in logic circuits has been used to generate the test patterns. Their paper deals with crosstalk pulses.Chen et al. [4–6] have given a mixed signal test generator XGEN for crosstalk-induced delay faults. They proposed a mixed signal test generation process where characteristics of crosstalk-induced noise are accurately modeled. By using Laplace transformations, they have obtained an expression for crosstalk in the s-domain, which they have transformed back to the time domain. These expressions are used to quantify the dependence of the pulse attributes on the lumped circuit parameters and the rise time of the input transition. Static timing analysis provides timing windows at gate inputs and outputs. The target-timing window is the intersection of the aggressor and victim timing window. For a specific target coupling fault, a pair of vectors create a crosstalk effect at the target and either a logic error or delay at the primary output. Their ATPG algorithm uses 11 valued algebra, analog delays modified PODEM for back-trace procedure. Their algorithm is not complete because of restricted propagation conditions of fault effects, and a constrained logic value system is used.Krstic et al. [7] developed a constrained path delay model as a combination of a critical path and a set of crosstalk noise sources interacting with the path. It uses a conventional path delay ATPG process without justification to sensitize the fault. Then a genetic algorithm is used to deal with timing information and justification of effecting transitions to primary inputs. Their technique was time consuming since it was based on the genetic algorithm and did not deal with the timing information efficiently.Li et al. [8] and Shen et al. [9] have proposed a test generation technique based on a single precise crosstalk-induced path delay fault model. However, this approach only generates patterns for a single aggressor affecting a target path. So it cannot propagate a maximal crosstalk-induced effect on a critical path. Further, their algorithm is computationally complex.In [10], Bai et al. have proposed a solution for multiple aggressor crosstalk problems. In their work, an implication graph is constructed that consists of logic variables and structural information to check for logic conflicts. A modified version of PODEM algorithm is used to search for test vectors.Aniket and Arunachalam [11] proposed an algorithm for testing crosstalk-induced delay faults. Their algorithm generates a list of critical paths by static timing analysis of the circuits. A robust testability criterion is applied to check for sensibility of the paths. For a sensitizable path the associated aggressors—victim pairs—are activated in a manner that will maximize the aggressor influence on the path to induce maximum crosstalk slowdown along a path. But their technique resulted in greater CPU time.Sinha et al. [12] have proposed a test generator by deriving a new 57-valued algebra and modified the key ATPG procedures to obtain a test generation methodology that increases the fault coverage, prove more faults as being untestable, and search much larger fraction of the space of all vectors. Their proposed algebra considers single element values called basis values, as well as many composite values made of multiple basis values. The assignment of a composite value to a circuit node indicates that any of the basis values comprising the composite value is possible. The use of composite values allows their ATPG method to postpone making a decision until one is absolutely necessary. This makes the search for a test more efficient as it reduces backtracking by reducing the number of assignments that causes conflicts. But the disadvantage is the test generation time is increased. Further, their algorithms considered only a single pair of a victim line and an aggressor line and hence cannot propagate a maximal crosstalk-induced effect along a critical victim path, on which the effect is more likely to cause delay test failure.Chun et al. [13] have proposed a test-generation method for crosstalk-induced delay effects, where they have considered multiple-aggressor crosstalk faults to maximize the noise of the victim line. The proposed algorithm uses parasitic information, such as coupling capacitance between a node of the victim and an aggressor, and timing information, such as static timing window and the crosstalk-induced noise delay model. Using the parasitic and timing information, the ATPG can reduce many false aggressors and handle multiple possible aggressors coupled to a victim lying along a path. Spatial pruning is used to remove false aggressors. Static timing analysis is performed then to remove false crosstalk faults. Their ATPG uses the do not care values in the test patterns obtained from the conventional path-delay ATPG to find the worst-possible-case test patterns for the generated crosstalk, and hence their ATPG can reduce the search space of the backward implication of the aggressor’s constraints, thus reducing time.In this paper we have used a modified version of FAN [14] algorithm for generating tests for crosstalk delay faults. FAN is more efficient than PODEM [15], which has been used in the previous papers because there are two extensions to the backtracking concept, namely, backtracking stops at internal fanout lines and FAN satisfies multiple objectives. Hence test generation will be relatively faster compared to PODEM-based test generation.  Further, in this paper we have increased the propagations conditions which can increase the fault coverage. To propagate a to-controlling delay effect at the input of a gate, any of three values are allowed on the side input, namely a static noncontrolling, a to-controlling transition and hazardous noncontrolling transition.


## 3. Crosstalk Fault List Generator

The total numbers of crosstalk faults are very large and impractical to test. Moreover, all the crosstalk faults need not be tested and cannot be tested. The target crosstalk faults are identified by using both the topological and timing information. The steps for finding the target crosstalk faults are given below.The method uses logical level implementation of the circuit and does not require layout information [16]. It is more amenable to the time to market need of designs. In order to obtain a reduced list of crosstalk delay faults classes of false crosstalk faults that need not be tested has to be identified and should not be included in the target fault list.The conditions for victim and aggressor to from a crosstalk target fault are:(1)
the victims should lie in the longest path;(2)
the relationship between transition time at the victim line beTvic and transition time at the aggressor line Tagg should satisfy the inequality Tvic-δ≤Tagg≤Tvic+δ, where δ can be 1- or 2-unit delay. The value of δ is taken as 1-unit delay. The transitions are limited to timing window δ to cause slowdown on the V-line.The algorithm to find the longest paths, victim set, and reduced set of target crosstalk delay faults is described.(1) For timing information, the latest transition time and earliest transition time at each line are calculated. Latest transition time at a line is the maximum delay on any path from any primary input. The latest transition time is calculated using the following rules:(i)
if LineL is a primary input or  pseudoprimary input:latest transition time forL=1 unit delay;(ii)
ifL is an output of a gate G having n inputs: I1,I2,I3,…,In:latest transition time forL=MAX{latesttransitiontimeforIj,j=1,2,…,n} + delay of the gate;(iii)
if LineL is a fanout branch:latest transition time forL = latest transition time for the fanout stem.Earliest transition time at a line is the minimum delay on any path from any primary input LineL is a primary input if(i)
lineL is a primary input or pseudoprimary input:earliest transition time forL=1 unit delay;(ii)
L is an output of a gate G having n inputs I1,I2,I3,…,In.Earliest transition time forL=MIN{earliesttransitiontimeforIj,j=1,2,…,n} + delay of the gate;(iii)
lineL is a fanout branch;(iv)
earliest transition time forL = earliest transition time for the fanout stem.The earliest transition time and latest transition time of all lines are calculated. Using the maximum value of the latest transition time, the longest paths in the circuit are identified.(2) Every primary input or pseudoprimary input or gate outputs in the longest path are the victims. The lines in the longest path form the set of victim lines V-lines (set_S).(3) A V-line from set_S is selected. The timing window of victim and aggressor lines is calculated. The aggressor line has a timing window of (earliesta(t), latest ai(t)). Similarly the victim line also has a timing window of ((latest vj)-δ unit delays, (latest vj(t)+δ unit delays)). The value of δ between the ai and vj is assumed to be one unit delay.(4) The timing window of the selectedvj, as well as the earliest and the latest transition times of other gate outputs are compared. If the timing window (earliest ai(t), latest ai(t)) of ai overlaps with  the timing window ((latest vj(t)-δ unit delay), (latest vj+δ unit delay)) of vj, then the crosstalk-induced transition fault caused by the selected c(ai,vj) is added to the target crosstalk fault list.The earliest and latest transition times for each line are shown for c17 circuit in Figure1. From the latest transition time the longest paths for c17  circuit are [3, 11, 16, 22], [6, 11, 16, 22], [3, 11, 16, 23], [3, 11, 19, 23], [6, 11, 16, 23] and [6, 11, 19, 23]. Every primary input or pseudoprimary input or gate outputs in the longest path are the victims. The victims in the longest path are [3, 6, 11, 16, 19, 22, 23]. Select a victim 3. The calculated timing window of the victim line is ([1-1],[1+1])=(0,2). Check the (3, 1) pair. The timing window of 1(1, 1) overlaps with the timing window of 3(0, 2). Hence (3, 1) forms a target crosstalk fault. Considering the pair (3, 22). The timing window of 3(0, 2) does not overlap with timing window of 23(3, 4). Hence, (3, 22) forms a false crosstalk fault and hence should not be included in the target fault list. The circuit c17 has a total number of target crosstalk faults as 42. The input fault list for the test generator is the reduced target crosstalk fault list.Figure 1
Example circuit c17.


## 4. Signal Values Used in Test Generation

The fault model used is logic gate level model. All the gates are assumed to have zero delay. The test generator uses a seven valued logic as shown in Table1. S0 and S1 are signal values which represent 0 in the first and second test patterns and logic 1 represents 1 in both test patterns, respectively. T0 represents 1 in the first pattern and 0 in the second pattern. T1 represents 0 in the first pattern and 1 in the second pattern. P0 represents glitch on a 0 signal. P1 is glitch on a 1 signal [11].Table 1
7 valued logic.
SignalDescriptionS0Steady 0S1Steady 1T0Falling transitionT1Rising transitionP0Positive glitchP1Negative glitchXUnknown valueThe operation of the AND gate and OR gate using the signal values mentioned above is shown in the Table2. Other operations for other gates can be handled in the same way.Table 2
Truth table for (a) two input AND gate and (b) two input  OR gate.
(a)ANDS0S1T0T1P0P1XS0S0S0S0S0S0S0S0S1S0S1T0T1P0P1XT0S0T0T0P0P0T0XT1S0T1P0T1P0T1XP0S0P0P0P0P0P0XP1S0P1T0T1P0P1XXS0XXXXXX(b)ORS0S1T0T1P0P1XS0S0S1T0T1P0P1XS1S1S1S1S1S1S1S1T0T0S1T0P1T0P1XT1T1S1P1T1T1P1XP0P0S1T0T1P0P1XP1P1S1P1P1P1P1XXXS1XXXXX


## 5. Test Generation Algorithm

In generating tests for crosstalk delay faults, the following objectives are to be satisfied.Objective 1: a rising transition or falling transition in the victim line.Objective 2: a transition in the aggressor lines opposite to that of the victim line.Objective 3: setting the off-path inputs along the target path to suitable logic values in order to propagate the transition in the victim line to the primary output. The target path is the path with the longest path delay from current site to the primary output [5].In the first step, the objectives are checked for contradiction since objectives have local conflict with other objectives and they are the fanout branches of the same stem.If any contradiction then the aggressors are removed. If all aggressors are removed then test is not possible. Then the final objectives are assigned to the lines and the remaining lines are set to a value X.The objectives are propagated and again checked for contradiction. Final list of objectives are obtained and a modified version of FAN algorithm is run as the core to obtain a two vector test for a crosstalk delay fault.The multiple back-trace procedure which is the most important aspect of the algorithm is applied to back trace from primary outputs toward primary inputs in a breadth first manner to satisfy the multiple primary objectives. The highest level objective generates the previous level objectives and so on. During the back-trace operation, if we create a new objective on an input of a gate, and this input happens to be a fanout branch, then we check first whether or not it has been tried by previous objectives. If so intersect the already assigned value on the stem with the required logic value on the fanout branches. If there is no conflict, the objective is moved to the primary stack. If conflict occurs in the intersection then the fanout branch with the required logic value is pushed to the secondary stack. After all the objectives in the primary stack are tried then the objectives in the secondary stack are tried and hence all possible choices are considered.In this work, two stacks are used for test generation which has greater advantage over the single   stack, and it reduces the number of backtracks. Further since decision is made only at the fanout points rather than at primary inputs back traces are further reduced. The primary inputs are assigned only the signal values   S0, S1, T0 and T1. All gates are assumed to have zero delay.The pseudocode for the test generation algorithm is shown in Algorithm1 with the multiple back-trace procedure.Algorithm 1:Pseudocode for the test generation algorithm.
Testgen (Faultlist)beginSet primary objectives ( );/*find all the primaryobjectives to be justified*/Set all other lines to Xif (there is conflict between two or more objectives on the fan-out branches ofthe same stem) thenbeginDrop the aggressor objectives;If (all aggressors objectives dropped)beginthen test not possible;ExitEndendImply ( ) /*with respect to the victim and remaining aggressors and other inputs*/Propagate ( ) /*Propagate the victim along the chosen target path*/if (there is conflict between the objectives) thenbeginDrop the aggressor objectives;If (all aggressor objectives dropped) thenbegintest not possibleExit( )endendMultiple back trace ( )Unassigned primary inputs are assignedImply ()/*with respect to primary inputs*/Propagate ( );/*Propagate the delay in the victim along the target path*/if (delay effect at PO)test is found;elsebeginno test possibleExit( )endendMultiple back trace ( )beginrepeatbeginremove one entry from the current objective;if(objective follows a fan-out point) thenbeginif(there is a contradiction with a previously assigned value)beginmove the objective to a secondary stackelsemove the objective to a primary stackendelsebeginContinue tracingSelect an input of gate with value xadd to the current objectivereturn multiple backtraceendendenduntil current objectives ≠ nullif (primary stack objective ≠ null) thenbeginremove the highest level objectiveassign most requested value;add to the current objectivereturn multiple back trace ( )endif(secondary stack objective ≠ null)beginremove the highest level objectiverepeatbeginassign value to the fan-out pointImply ( )if (success)beginadd to the current objectivereturn multiple back trace ( )endelseassign next valueenduntil all values assignedif (assignment not possible)beginDrop the aggressor objectives;If(all aggressor objectives dropped) thenbegintest not possibleExit( )endendendendThe proposed ATPG algorithm for crosstalk delay fault is explained by taking ISCAS’85 c17 benchmark circuit shown in Figure1.The following sample faults are taken from the   target fault list for c17 for explanation.(16, 10), (16, 11), (16, 19), (16, 22), (16, 23).Step 1.
Here 16 is victim and 10, 11, 19, 22, 23 are aggressors. The available paths for propagation of victim to the primary output are (10–22), (19–23).Step 2.
Victim 16 is assigned a rising transition, and the aggressors are assigned falling transition. If the transition at the gate input along the path has a to-noncontrolling transition value any of the three values are allowed at the side inputs: a static noncontrolling and   a to-noncontrolling transition and hazardous noncontrolling transition. If the transition at the gate input along the path has a to-controlling transition value any of the three values are allowed at the side inputs: a static controlling and   a to-controlling transition and hazardous controlling transition.Step 3.
The path (10–22) is taken for propagation. After checking for contradictions, the final objectives obtained were (16, T1), (10, S1, T1), (11, T0), (19, T0), (22, T0), (23, T0), where (10, S1, T1) is off path objective.Step 4.
Now the current objectives   are taken and processed.Step 5.
When (16, T1) is back traced, (11, T0, S1) is the next level objective. This being a fanout point will be checked for contradiction. Since there is no contradiction it will be moved to primary stack. Now when (19, T0) is back traced, (11, T1, S1) is next level objective which results in contradiction, and hence 11 with all values, namely, S1, T0, T1 will be moved to secondary stack. Now when secondary stack is processed, (11, S1, T0, T1) will be processed.  The values S1, T0, and T1 are assigned one by one and propagated to check if all objectives are satisfied. (11, S1) will satisfy both objectives (16, T1) and (19, T0).Step 6.
Finally, after backtracking the primary objectives assigned are 1—>S0, 2—>T0, 3—>S0, 6—>S0, 7—>T1. Implications are done and propagated, and delay is observed at the primary output 23. After propagating   the faults finally detected were (16, 19), (16, 22), (16, 23).The next path is taken into consideration and test vectors are arrived for the remaining faults.


## 6. Experimental Results

The test generation algorithm for crosstalk delay faults was run on ISCAS’85 combinational circuits and several enhanced scan version of ISCAS’89 sequential circuits. Table3 gives the characteristics of ISCAS’85 combinational circuits and the scan versions of ISCAS’89 sequential circuits. After the circuit name, the number of inputs, number of outputs, number of gates, number of paths, number of critical paths, number of victims, and total number of target faults are given [17]. The entire circuit paths are analyzed using the tree data structure. The total number of paths in the circuit is calculated using depth first search algorithm which employs recursive search procedure. Critical paths are paths whose delay is longer than a given percentage of the longest propagation delay in the circuit. The selection of critical paths, number of victims in the critical path, and the total number of target faults are done using static timing analysis.Table 3
The ISCAS’85 and scan version of ISCAS’89 circuit characteristics.
CircuitNumber of inputsNumber of outputsNumber of GatesNumber of pathsNumber of critical pathsNumber of victimsTotal target faultsc17526116742c4323671608392621991039327c8806026383864292709279c499413220294401420721879c19083325880729057329325916s2774102861074s208191096145218743s208.1189104142112558s2981720119231110537s5262427193410110891s386131315920710494195s51025132113691131098s420.134172184741141276s11963232529309795510630s12383232508355830455822s13207.170079079511345319565188241743s15850.161168497721647380358238341240814The test generation algorithm using modified FAN was implemented in   3000 lines of C language under the LINUX environment. Results were compared with results of modified PODEM based ATPG which was implemented in   2000 lines of C language.Table4 gives the percentage increase in fault coverage and reduction in average number of back traces for FAN based test generation compared to PODEM based ATPG. Average number of back traces is given by total number of back traces divided by total number of paths. The bold number represents the maximum number of faults detected and minimum number of back traces obtained for each circuit, respectively. With a nominal increase in fault coverage (10.4%) the algorithm achieved a high degree of reduction in average number of back traces (29.66%) due to checking of contradictions at the fanout point instead of back tracing to primary inputs. Hence the CPU execution time is greatly reduced.Table 4
Comparison of results between FAN and PODEM.
Circuit nameNumber  of fanout points% Of average aggressors activatedAverage number of back-traces% Decrease in average number of back tracesCPU time (sec)Fault coverage (%)FANPODEMFANPODEMFANPODEMc173735.158.46139.130.0000.0009290c4328994132.054216.51839.01338.05389.28079c4995998163.789233.41829.83816.353040.17146c88012597314.460436.5627.971268.53145.98030c190838480646.377842.2823.213762.35786.5157s274819.59312.21821.480.0000.0008358s208329189.029101.20812.031.4001.5506842s208.1288689.55103.9313.830.650.9001043s298349476.104161.88652.993.7335.5008559s5265495132.353301.28456.0713.2119.4338684s3862680102.88206.0650.0715.2621.86277s5107388156.615218.4828.3213.1523.056547s420.15893175.67189.697.399.313.582212s119615585508.99558.268.8314042862.46252s123816591424.97658.2835.44704.5710.158786Average29.665541001.364.5354.13Table5 gives the comparison of number of transitions for PODEM- and FAN-based ATPG. For 12 of the 15 benchmark circuits FAN gave less number of transitions. FAN reduces the number of transitions by 28.93% compared to PODEM. Hence the switching activity in the circuit is reduced thus reducing the power dissipation of VLSI circuits. Number of transitions is reduced because during back tracing it was observed in the results that the values assigned to primary inputs by FAN has more number of static 0s and static 1s compared to   PODEM. This is because back tracing in FAN results in more number of unassigned primary inputs with value X. The algorithm assigns static values to unassigned inputs.Table 5
Comparison of number of transitions between FAN and PODEM.
Circuit nameNumber of transitions% Reduction in number of transitions overFANPODEMPODEMc179411719.66c43219958534541342.21c499380926374882−1.58c880130217112465−13.63c19084306344581336.00s27338285−15.68s2082131331735.75s208.1930183749.37s2986388886027.90s52680361310038.65s386153852676042.50s51047471017553.34s420.13435803657.25s119610776522283951.63s12386916411657040.66Average28.93Figure2 gives the comparison between the execution time of FAN- and PODEM-based ATPG. For large circuits such as c880 and c499, CPU time is reduced by 60% for FAN based ATPG.Figure 2
Comparison of CPU Time.Table6 presents the comparison of the proposed ATPG  with the results of [6, 12, 13] for crosstalk delay faults in combinational circuits. In the proposed ATPG, all the target faults are taken into consideration for most of the   benchmark circuits except for c1355, c5315, c7552, s13207.1, and s15850.1 where the number of target faults is limited to 10000. In [6] the number of victim/aggressors pairs taken into consideration is only 100 but the CPU time is much higher. For c432, the proposed   test generator takes the reduced list of faults as 9327, and CPU time taken was only 338 sec with a better fault coverage. In [12] again 100-single aggressors/victims were generated randomly and the fault coverage calculated. The fault coverage achieved was very low, and CPU time also very high. In [13] the number of target paths is limited to 1000 and number of back traces is limited to 10000 and hence CPU time is less. Except for c1355, c5315, c7552, s13207.1, and s15850.1, the proposed approach takes all the target faults into account and does not limit the back trace and has a better fault coverage for most of the benchmarks. Table 7 represents the comparison of the proposed ATPG   with the results of [8, 9, 18] for crosstalk delay faults in sequential circuits. In [8, 9, 18] the calculation of target faults were similar since layout information has not been used and gate delay assumed to be 0. In this paper, gate delay was assumed to be 1. Compared to [8, 9, 18] the proposed approach has higher fault coverage. For larger benchmark circuits s13207.1 and s15850 in [8] only 100 testable randomly selected longest paths are considered for target fault selection. In [18] the waveform sensitization-based algorithm cannot generate tests for the large circuits. Hence   compared to previous works the proposed test generation algorithm has produced comparable or greater fault coverage, and CPU time is also nominal.Table 6
Comparison with previous works.
Circuit namePrevious work [6]Previous work [12]Previous work [13]Proposed ATPG% Fault coverageTime(s)% Fault coverageTime(s)% Fault coverageTime(s)% Fault coverageTime(s)c432351019154 hr 42 min——80338.05c880281553382 hr 27 min54.260.1801268.5c1355163173363 hr 48 min——331865.8c1908332562810 hr 40 min24.34360153762.3c5315317030124 hr 10 min497.85577151.2c7552148424228 hr 26 min521326.6689867.03Table 7
Comparison with previous works.
Circuit namePrevious work [8]Previous work [9]Previous work [18]Proposed ATPG% Fault coverageTime(s)% Fault coverageTime(s)% Fault coverageTime(s)% Fault coverageTime(s)s20831.500.1855.480.2——691.233s29842.660.17————843.317s38634.430.5551.890.3——6215.26s52666.300.1955.240.2——8612.033s420.127.190.50————229.3s119631.320.671.030.48.4119621404s1238——3.830.23.111687704.5s13207.187.141432925.1318287——6432333.5s15850.183.05196273.1583371——5397136.4For sequential circuits even though CPU time is higher the fault coverage increases by an average of 30% for the 6 circuits.


## 7. Conclusion

A new modified FAN-based ATPG algorithm has been proposed that increases the fault coverage with reduced number of transitions and hence permits safe testing of low power circuits.In test generation for crosstalk delay fault, the number of objectives is to be a satisfied is larger compared to stuck at faults. Hence the multiple back trace procedure adopted in FAN algorithm concurrently traces more than one path and is more efficient than the back trace along a single path. Moreover, the assignment is done at the fanout points and hence in case of contradiction, fruitless computation is avoided. Hence the modified version of FAN algorithm used for test generation significantly reduced the average number of back traces compared to PODEM. Hence the CPU time, that is, test time reduces significantly by using modified FAN when compared to modified PODEM. Further, the algorithm handles single-victim/-multiple aggressors in a very efficient manner. The number of transitions can be further   improved for low power testing by minimising the transition controllability and transition observability cost which is considered as future work.



---

*Source: 745861-2012-01-19.xml*