Kazantzidis Manthos
Abstract
The design, validation and verification of VLSI circuits are all increasing in difficulty as the size of these circuits increases. When these circuits are manufactured, it is important to have simple methods of testing them to ensure that they are performing properly. There are two sides to the issue of testability: test generation and design for testability. In this paper I am mostly concerned with automatic test pattern generation. I touch design for testability when I present for introduction and presentation purposes the terms linear and C-testability and categorize the testability of a DFT adder[6].
Automatic test pattern generation (ATPG) is the process of determining a sequence of input vectors for a circuit that will allow the detection of faults that might be present. The first section of this paper provides the foundation for the subsequent discussion on current research accomplishments. In doing that I try to identify not yet investigated combinations of the presented techniques.
In the next section, I try to give the essentials of test pattern generation background. Examples with mostly tutorial value are given in a subsection of [Fundamentals]. The terms C and Linear Testability are also introduced, together with an example circuit which is proved to be linear testable by the author. Section 3 contains the research proposals studied and explained here.
2. Fundamentals
Automatic Test Pattern Generation (ATPG) is the process of generating inputs for a design that will allow detection of faults in a circuit. A fault is said to be detected if it can be read as an error on the output of the circuit. The fault model that is mostly used models single stuck-at-value faults. For these algorithms, the input is a gate-level description of the design in a high level hardware description language like VHDL.
The stack-at-fault (stuck-at-value) model assumes that only one signal in the design is faulty at a time and this fault is causing the signal to have a constant value, either 1 or 0. Other elaborated on fault models are multiple stuck-at faults, functional transformation faults, intermittent faults, and delay faults. They have the advantage that they are more realistic but the serious disadvantage that they are impractical to use because of the large number of fault combinations. Remember that even single stuck-at-faults have an exponential time optimal solution for combinational circuits. The deal gets much worse on Meally circuits when we have to account for state also.
The basic steps of the algorithms are:
1. Inject a fault into the circuit (stuck a line to one value for stuck-at faults)
2. Attempt to find an input vector or sequence of vectors that will
When we are interested in full coverage each line on the circuit must be tested for all the faults we are considering. The end result of ATPG is a sequence of test vectors, the test set. Faults are then detected by comparing the output of the circuit under test to the output of a known good circuit or a ROM of the expected output according to the specifications.
In general, it is not known which faults are present since each input vector might detect multiple faults, nor are we interesting in that. VLSI technology does not justify any attempt for correction. Instead, the identified by this process faulty circuits are considered useless as far as off-line is concerned.
Metrics that the research community uses to compare algorithms and results of test generation schemes are typically:
2.1.1 Understanding heuristics
In this section, some examples are provided in order to gain insight to the problem. Consider that given one fault all the test vectors can be identified. This can be done by using one of the standard approaches: sensitized path, D or PODEM. I will try to devise an efficient algorithm to produce test sets as close to minimum size as possible.
To concentrate on the heuristics themselves let us assume that we have exhaustively taken all the information needed to fill up a table with all the single stuck-at-value faults and have connect them with pointers to lists containing the test vectors that detect them. We can also have the inverse of these tables matching all input test vectors to the faults they can detect. All this takes exponential to the size of the circuit time and represents part of the exhaustive solution. The exhaustive solution would go on identifying all minimal sets and finally keeping the smallest.
To avoid that we may apply some heuristics very much like the ones proposed in the papers. We expect the solution to be as close to optimal as possible. Consider for example the following approach which a combination of a fault-oriented selection of test vector and an input vector oriented one.
2.1.2 C-Testability and Linear Testability
If A(n) is the size of a minimal test set for a circuit with n-inputs then if A(n+1)=A(n)+C the circuit is called
C-testable.
If A[n+1]=A[n]+O[n] then the circuit is said to be
linear testable
.
The process to prove C or linear testability is to find a test set that covers all the modeled errors in the circuit and calculate its size. Since the test vectors can be expressed only as a function of the n-inputs using some notation, the size of the test set is also expressed in terms of n.
Here is (Fig. 1) a schematic for a 3-input double representation of zero adder as proposed in [5]. This circuit can be proved to be linear testable.
Let us start by the following observations:
# of stuck faults = 2 * # of lines
# of lines = #inputs + # gates + fan-out of junctions
# inputs = 2*n
| Input Vector | #vectors | #faults covered |
| 11 1 | 1 | 12n |
| 00 0 | 1 | 11n |
| {0 0} n {1 1} n | 1 | 9n+2n(n-1) |
| {1 1} n {0 0} n | 1 | 7n |
| (x x} k 1{x x} n-k-1 {~x ~x} k 1{~x ~x} n-k-1 | n | n(n-1)(n+4)/2 |
| {x x} k 1<x x} l 0{x x} m {~x ~x} k 1{~x ~x} l 0{~x ~x} m (or ones where zeros and the reverse) | n(n-1) | n*n*(n-1)/2 |
| {1 1} k 0{1 1} n-k-1 {1 1} n | n | 3n |
The test set comprises of n(n-1)+2n+4 and so A(n+1)=A(n)+2(n+1). Consequently with this test set the circuit is shown to be linear testable.
3. Advanced Techniques
The problem of generating minimum size minimal test sets is NP-Hard. Proposals aim to develop techniques that are close to optimal solutions but provide much better than the prohibitive exponential time, usually polynomial to the size of the circuit.
A common approach is to use compaction techniques to produce as close to minimum size minimal test sets for a target coverage, usually full coverage. The proposals use static or dynamic techniques or explore on ways to most efficiently combine them.
Static techniques are applied to already generated test sets in some other way, often by a dynamic technique to further reduce them. Dynamic techniques attempt to generate test vectors such that each one detects a larger number of errors. The current test set is incremented in size by a collection (or one) test vectors to increase its coverage using dynamic techniques. The static techniques aim at reducing the test set size without compromizing coverage.
An efficient intergrated approach like [1],[4] would consist of a collection of dynamic and static techniques combined to produce minimal test sets. Dynamic techniques are typically targeted at providing a minimal test set that can be efficiently reduced by static compaction. For example double error detection is proposed in [4]. There, input values (lines, bits in the test vector) that remain unspecified after targeting some yet undetected faults are used to detect faults which have already been detected (by other test vectors in the current set). Effectively we are providing a larger test set. This allows included test vectors to be pruned off the test set by a compaction technique, when all the faults they detect are detected by other vectors (in the new current test). Double error detection is actually a member in a class of such techniques that may be called N-error detection. An example for a static technique is the two by one algorithm proposed initially in [3]. Two test vectors are selected and replaced by one provided that the coverage does not decrease. This approach decrements the test set size by one each time it is succesfully applied. This technique can be also though of as a member of a class of techniques called M by N, where we select and replace M test vectors in the test vectors with N new without adversely affecting the coverage. An M by N technique decrements the size of the test set by M-N each time it is succesfully applied. As both numbers get larger the complexity is exponentially increased but we gain in efficiency from examining more options or from the possibility of increasing the size of the decremental step.
3.1 Dynamic Compaction
In [3] the term independent fault set is defined. The term was introduced by [Akers, Krishnamurthy]. Two single stuck-at faults such that no test vector exists that detects both faults, are said to be independent. If every pair of faults in a fault set F is independent then F is called an independent fault set. A sufficient (not necessary), easy to check condition such that two faults are independent is the following: if there is at least one line where the necessary assignments conflict (one fault requires 0 while the other a 1) then the two faults are independent. If any vector that detects the fault requires the same value to be set on a line then this assignment is necessary. When F does not contain any redundant faults then every fault in F needs a different test vector to be included in the test set. This is a lower bound on the test set size for the circuit.
In COMPACTEST ([1]), to come up with a test set, an ordered fault list is created. Each time the fault from the top of list is the fault to be covered. When a test vector for that fault is found this fault along with all others that are detected by the vector are deleted from the list. The faults are ordered such that faults included in a larger independent fault set appear higher in the fault list (processed later). In this way it is guaranteed that the test sets generated for these independent faults are necessary and cannot be replaced by a smaller number of tests. The fault list order in COMPACTEST is fixed.
[4] is based on optimizations and observations on existing techniques. The process is similar to COMPACTEST in all other respects apart from the optimizations mentioned here.
3.1.1 Dynamic Fault Ordering
Dynamic fault ordering is used in [4], based on the observation that the order in which faults are targeted (tried to be covered by a test vector) impacts the size of the test sets produced.
The number of yet undetected faults in the independent fault sets changes as we include new test vectors. So, the largest independent fault set over the remaining faults may not be the first one in the list after some faults are detected. By using dynamic fault ordering, i.e. reordering the list each time we include a new test vector the fault list is ordered according to the yet undetected faults in each independent fault set.
Conceptually, the guaranty that the test vector generated for these independent faults are necessary and cannot be replaced by a smaller number of test vectors holds at a finer granularity than the whole test set, yielding smaller test sizes (most of the times). This holds because between each step of the process we need to add the maximum number of test vectors if these are necessary anyway. By doing that we know that on each step we are covering more faults and thus optimizing the process. With fault reordering we are maximizing this effect.
3.1.2 Maximal compaction [1]
This technique aims to increase the number of unspecified inputs after generating a test vector for a given fault.In this way, test generation has more room to detect additional faults with this vector by specifying the still unspecified inputs.
A process using maximal compaction can be described in step by step fashion:
3.1.3 Rotating Backtrace: [1]
Aims to maximize the number of new faults detected by each vector. Runs when a controlled value on the output of a gate has to be justified. When we need a 0 output for an AND and NOR, 1 for OR and NAND we need set only one input value to 0 for AND and NAND, 1 for OR and NOR. A typical test generation algorithm would use the input with the highest controllability to increase efficiency. (Controllability is a metric for measuring how easy it is to access the desired line from the inputs. For example inputs would have the highest controllability -1 and outputs are expected to have low controllabilities.)
With rotating backtrace we are choosing a different input line each time. In fact, inputs are seen as rotating (i(0) then i(n) then i(n-1) and so on) in a wrap-around list and we are chosing always the top of the list. In this way we are likely to cover also faults that propagate to the outputs along different paths, by potentially sinsitizing different paths each time.
It is found in [4] though that rotating backtrace sometimes conflicts with maximal compaction. Consider a line that is set to a value during test generation for a primary or secondary fault detection, then unspecified by maximal compaction and then set again to a controlling value during a test generation for a secondary fault. A different input would be used to justify the controlling value in the two cases.
We need the same input to be used (chosen) to justify the controlling value in both cases so that we cover both faults by specifying only one line. Put another way, values that were unspecified by maximal compaction are likely to be specified back to the same value, thus minimizing the risk of losing a detected fault. By using rotating backtrace, the routine that chooses the input of the gate to be controlled would return the other input for a two-input gate. The maximal compaction routine would then need to specify that one too to propagate the fault to the output.
It is thus proposed to switch off rotaring backtrace in these cases. This can be effected by rotating the fan-in list of the gate to be set to the controlled value, both before and after selecting a fan-in line that is to be set to a controlling value.
In the results that follow rotating backtrace is turned off only for two-input gates because it was found experimentally that this works better.
Results from experiments are shown on Table I. The terms used in the table are explained here:
In parenthesis is the number of faults that their tests have been invalidated by maximal compaction. (These faults are left uncovered; at most one vector per fault should be added for complete coverage).
An approach for interleaving dynamic compaction techniques is introduced in [2]. After a test generation T(i) instead of selecting the next fault, try to COMPACT T(i) with the existing test set. If it is COMPACTable with any set Tj then Tj is replaced by Ti ^ Tj. COMPACT stands for a compaction technique. The ones used here are not new and are described later (e.g maximal compaction introduced in [1]). The difference is that static compaction is applied after the addition of each single test vector and not after a test set (to be compacted) is determined by the dynamic algorithm. Compaction is obtained by repetitive application of the basic compaction
From my search on Melvyl (INS database) I have not seen an intergration ofthis technique (with N-error detection for example) except from the one proposed here that uses PODEM -a standard test vector generation algorithm.
3.1.4 Double detection [4]
A definition of a redundant test vector is in order. For a given test set, a test vector is called redundant if every fault it detects is also detected by some other test vector already included in the test set.
Double detection uses input values that remain unspecified during the test generation process to increase the potential for obtaining and then dropping redundant test vectors. This is achieved by detecting faults twice before they are dropped from the fault list. What is really done is allowing already covered faults to be used once more as secondary targets. Conseptually we hold a large test set mid-way through the process which is selected in a way that is easily minimizable.
When all the faults are covered at least once (or aborted when no test vector can be generated within the backtrack limit) we have a test set. At this point some of the faults will have been used twice to determine a test vector inclusion in the set.
After termination of the above process we focus on identifying as many reduntant vectors as possible, to erase them from the list. To do this we keep information about the errors that the vector covers when we include it in the test set.
In Table II an example is provided that illustrates why and how this works.
Experimental results are given at Table III. The first column is the dy+nb.
3.2 Static Compaction Techniques
3.2.1 Two by One Algorithm [4]
As mentioned before the two by one algorithm is a special case of the N by M class where we are replacing N vectors by M (N>M) which are to cover a number of faults.
Here is an example, where two by one is applied:
t1 detects f1,f2,f3
t2 detects f3,f4
t3 detects f5
The set is minimal as produced by the dynamic compaction.
However if we add t4 detecting f4,f5 then both t2 and t3 can be removed from the set resulting in a smaller minimal set.
To illustrate how this can be explained algorithmically let us define the term essential faults. An essential fault is one that is detected by only one vector in the test set. In general, a vector whose essential faults are detected by an added vector can be removed. By ensuring that an added vector detects the essential faults of at least two vectors in the test, the test size can be reduced at least by one. Extending the definition of essential faults for a given test set T, fault f is an essential fault of {t1, t2} belonging to T [3],[4]
iff t1 or t2 detects f AND
T-{t1,t2} does not detect f (generally t1,...,tn)
Then when we add t3 that covers the essential(t1,t2) both t1 and t3 can be dropped.
Essential faults of two test vectors can be identified by using triple detection. We need N-detection to identify faults of N-1 test vectors but this statement has no practical value since time complexity would grow exponentially.
The necessary condition for a test vector t3 to be included in the set, i.e. allows two vectors t1 and t2 to be removed, is that ess(t1) and ess(t2) must not contain a pair of independent faults. Independent fault set is a set of faults such that no two faults in the set are detectable by the same test vector. If a pair was independent we would not be able to find a t3.
Results for the whole test compaction are given at Table IV.
Issues of automatic test pattern generation have been studied. A number of heuristics is examined. The introduction of a technique in an ATPG algorithm is not always without side effects. There are combinations of proposed techniques that have not been yet studied.
References:
[1] COMPACTEST: A Method to Generate Compact Test Sets for Combinational Circuits - Pomeranz, L. Reddy, M. Reddy -IEEE Trans. On CAD, IC and Systems vol.12 Jul 1993
& original paper 1991
[2] A New Dynamic Test Vector Compaction for ATPG - Ayari, Kaminska- IEEE vol.13 March 1994
[3] On Compacting Test Sets by Addition and Removal of Test Vectors - Kajihara, Pomeranz, Kinoshita, M. Reddy - 1994 IEEE
[4] Cost-Effective Generation of Minimal Test Sets for Stuck-at Faults in Combinational Logic Circuits - Kajihara, Kinoshita, M. Reddy 1995
[5] Area-Time Efficient Modulo 2^n-1 Adder- Efstathiou, Nikolos, Kalamatianos- IEEE Trans. On Circuits and Systems: Analog & Digital Signal Processing, Vol. 41 No.7 July 1994
[6] My project on VLSI Testing at University of Patras, Greece.
Sources :
1. VLSI Testing and Design for Testability - Lectures - D. Nikolos - Computer Engineering and Informatics Department, University of Patras 1995.
2.Scott Scrutchfeld Thesis 1995
| 1 | (*) A significant percentage of the presentation slides is the outcome of putting together a comprehensive introduction to the subject. This work is not presented in this paper. |