compactor (k) st comparator FIGURE 85.5 Data compaction testing. The best-known algorithms are the D-algorithm(precursor to all), POdEM, and FAn [Abramovici, 1992] Three steps can be identified in most automatic test pattern generation(ATPG)programs: (1)listing the signals on the inputs of a gate controlling the line on which a fault should be detected, (2)determining the primary input conditions necessary to obtain these signals( back propagation)and sensitizing the path to the primary outputs such that the signals and fault can be observed, and(3)repeating this procedure until all detectable faults in a given fault set have been covered PODEM and FAN introduce powerful heuristics to speed the three teps by aiding in the sequential selection of faults to be examined and by cutting the amount of back and forward propagation necessary. Notwithstanding heuristics, algorithmic test pattern generation is very computationally expensive and can encounter numerous difficulties, especially in certain types of networks. Newer alternatives are based on pseudo- random pattern generation[ Bardell et al., 1987] and fault simulation. In this strategy, a large set of patterns is generated pseudo-randomly with the aid of an inexpensive(hardware or software) generator. Typical choices for these are linear feedback shift registers and linear cellular automata registers(see below). The pseudo-random set is used to stimulate a circuit, and, using a fault simulator, one can evaluate the number of faults that are covered by this set. An algorithmic test pattern generator is then applied to find coverage for the remaining faults (hopefully, a small number), and the pseudo-random set is thus augmented. The disadvantages are that the resulting set is very large and fault simulation is also computationally expensive. However, this method presents n alternative for circuits where the application of deterministic algorithms for all faults is infeasible. Output Response analysis Especially when designing a circuit including some BIST, one must decide how to check the correctness of the circuits responses [Bardell et al., 1987 ]. It is infeasible to store on-chip all expected responses, and thus a common solution is to reduce the circuit responses to relatively short sequences: this process is called data compaction and the short, compacted resulting sequence is called a signature. The normal configuration for data compaction testing is shown in Fig. 85.5. The n-input circuit is stimulated by an input pattern generator (pseudo-random or exhaustive if n< 20); the resulting output vector(s), of length up to 2, is compacted to a very short signature of length k < 2(usually k is around 16 to 32 bits). The signature is then compared to a known good value. The main advantages of this method are that(1)the testing can be done at circuit speed, (2)there is no need to generate test patterns, and(3)the testing circuitry involves a very small area, especially if the circuit has been designed using scan techniques(see Section 85.2). The issues revolve around designing very efficient input generators and compactors The main disadvantage of this method is the possibility of aliasing. When the short signature is formed,a loss of information occurs, and it can be the case that a faulty circuit produces the same signature of a fault- free circuit, thus remaining undetected. The design method for data compaction aims at minimizing the probability of aliasing. Using the compactors explained below, the probability of aliasing has been theoretically proven to be 2-f, where k is the length of the compactor(and thus the length of the signature). It is important to note that(1)the result is asymptotically independent of the size and complexity of the circuit under test ) for k= 16, the probability of aliasing is only about 10- and thus quite acceptable; and(3)the empirical results show that in practice this method is even more effective. Most of all, this is the chosen methodology when BIST is required for its effectiveness, speed, and small area overhead A secondary issue in data compaction is in the determination of the expected"good"signature. The best way is to use fault-free simulation for both the circuit and the compactor, and then the appropriate comparator can be built as part of the testing circuitry [Bardell et al., 1987; Abramovici, 1992] e 2000 by CRC Press LLC© 2000 by CRC Press LLC The best-known algorithms are the D-algorithm (precursor to all), PODEM, and FAN [Abramovici, 1992]. Three steps can be identified in most automatic test pattern generation (ATPG) programs: (1) listing the signals on the inputs of a gate controlling the line on which a fault should be detected, (2) determining the primary input conditions necessary to obtain these signals (back propagation) and sensitizing the path to the primary outputs such that the signals and fault can be observed, and (3) repeating this procedure until all detectable faults in a given fault set have been covered. PODEM and FAN introduce powerful heuristics to speed the three steps by aiding in the sequential selection of faults to be examined and by cutting the amount of back and forward propagation necessary. Notwithstanding heuristics, algorithmic test pattern generation is very computationally expensive and can encounter numerous difficulties, especially in certain types of networks. Newer alternatives are based on pseudo￾random pattern generation [Bardell et al., 1987] and fault simulation. In this strategy, a large set of patterns is generated pseudo-randomly with the aid of an inexpensive (hardware or software) generator. Typical choices for these are linear feedback shift registers and linear cellular automata registers (see below). The pseudo-random set is used to stimulate a circuit, and, using a fault simulator, one can evaluate the number of faults that are covered by this set. An algorithmic test pattern generator is then applied to find coverage for the remaining faults (hopefully, a small number), and the pseudo-random set is thus augmented. The disadvantages are that the resulting set is very large and fault simulation is also computationally expensive. However, this method presents an alternative for circuits where the application of deterministic algorithms for all faults is infeasible. Output Response Analysis Especially when designing a circuit including some BIST, one must decide how to check the correctness of the circuit’s responses [Bardell et al., 1987]. It is infeasible to store on-chip all expected responses, and thus a common solution is to reduce the circuit responses to relatively short sequences: this process is called data compaction and the short, compacted resulting sequence is called a signature. The normal configuration for data compaction testing is shown in Fig. 85.5. The n-input circuit is stimulated by an input pattern generator (pseudo-random or exhaustive if n < 20); the resulting output vector(s), of length up to 2², is compacted to a very short signature of length k << 2² (usually k is around 16 to 32 bits). The signature is then compared to a known good value. The main advantages of this method are that (1) the testing can be done at circuit speed, (2) there is no need to generate test patterns, and (3) the testing circuitry involves a very small area, especially if the circuit has been designed using scan techniques (see Section 85.2). The issues revolve around designing very efficient input generators and compactors. The main disadvantage of this method is the possibility of aliasing. When the short signature is formed, a loss of information occurs, and it can be the case that a faulty circuit produces the same signature of a fault￾free circuit, thus remaining undetected. The design method for data compaction aims at minimizing the probability of aliasing. Using the compactors explained below, the probability of aliasing has been theoretically proven to be 2–k, where k is the length of the compactor (and thus the length of the signature). It is important to note that (1) the result is asymptotically independent of the size and complexity of the circuit under test; (2) for k = 16, the probability of aliasing is only about 10–6 and thus quite acceptable; and (3) the empirical results show that in practice this method is even more effective. Most of all, this is the chosen methodology when BIST is required for its effectiveness, speed, and small area overhead. A secondary issue in data compaction is in the determination of the expected “good” signature. The best way is to use fault-free simulation for both the circuit and the compactor, and then the appropriate comparator can be built as part of the testing circuitry [Bardell et al., 1987; Abramovici, 1992]. FIGURE 85.5 Data compaction testing