Scalable scan-path test point insertion technique Number:7,131,081 from the United States Patent and Trademark Office (PTO) owispatent A logic circuit comprising at least one input, one output and a delay fault circuit. The delay fault circuit includes a first standard scan cell, a combinational test point positioned immediately after the first standard scan cell in a scan chain and a second standard scan cell positioned immediately after the combinational test point in the scan chain.<H technique, insertion, Scalable, scan, p, 7131081.html, Patent, pto, 7131081

Title: Scalable scan-path test point insertion technique

Abstract: A logic circuit comprising at least one input, one output and a delay fault circuit. The delay fault circuit includes a first standard scan cell, a combinational test point positioned immediately after the first standard scan cell in a scan chain and a second standard scan cell positioned immediately after the combinational test point in the scan chain.

Patent Number: 7,131,081 Issued on 10/31/2006 to Wang, et al.

Inventors: Wang; Seongmoon (Plainsboro, NJ), Chakradhar; Srimat (Manalapan, NJ)
Assignee: NEC Laboratories America, Inc. (Princeton, NJ)

Appl. No.: 10/736,879

Filed: December 16, 2003

Current U.S. Class: 716/4 ; 716/6

Current International Class: G06F 17/50 (20060101)

Field of Search: 716/1,4,6

References Cited [Referenced By]

U.S. Patent Documents


5642362	June 1997	Savir
6148425	November 2000	Bhawmik et al.

Other References

D Belete, A. Razdan, W. Schwarz, R. Raina, C. Hawkins, and J. Morehead. Use of DFT Techniques in Speed Grading a 1GHz+ Microprocessor. In Proceedings IEEE International Test Conference, pp. 1111-1119, 2002. cite- d by other .
K.-T. Cheng, S. Devadas, and K. Keutzer. A Partial Enhanced-Scan Approach to Robust Delay-Generation for Sequential Circuits}. In Proceedings IEEE International Test Conference, pp. 403-410, 1991. cited by other .
V. Dabholker, S. Chakravarly, I. Pomeranz, and S. Reddy. Techniques for Minimizing Power Dissipation in Scan and Combinational Circuits During Test Application. In IEEE Trans. on Computer-Aided Design of Integrated Circuit and System, vol. 17(12), Dec. 1998. cited by other .
B. Dervisoglu and G. Stong. Design for Testability: Using Scanpath Techniques for Path-Delay Test and Measurement. In Proceedings IEEE International Test Conference, pp. 365-374, 1991. cited by other .
S. Gerslendorfer and H.-J. Wunderlich. Minimized Power Consumption for Scan-Based BIST. In Proceedings IEEE International Test Conference, pp. 77-84, 1999. cited by other .
M. J, Geuzebroek, J. T. van der Linden, and A. J. van de Goor. Test Point Insertion for Compact Test Sets). In Proceedings IEEE International Test Conference, pp. 292-301, 2000. cited by other .
P. Goel. An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits}. In IEEE Trans. on Computers, vol. C-30(3), Mar. 1981. cited by other .
L. H. Goldstein and E. L. Thigpen. SCOAP: Sandia Controllability/Observability Analysis Program. In Proceedings IEEE-ACM Design Automation Conference, pp. 190-196, 1980. cited by other .
W. Mao and M. D. Ciletti. Reducing Correlation to Improve Coverage of Delay Faults in Scan-Path Design}. In IEEE Trans. on Computer-Aided Design of Integrated Circuit and System, vol. 13(5), May. 1994. cited by other .
I. Pomeranz and S. M. Reddy. On Achieving Complete Converage of Delay Faults In Full Scan Circuits using Locally Available Lines. In Proceedings IEEE International Test Conference, pp. 923-931, 1999. cited by other .
J. Savir and R. Berry, At-Speed Test is not Necessarily an AC Test. In Proceedings IEEE International Test Conference, pp. 722-728, 1991. cited by other .
J. Savir and S. Patil. Scan-Based Transition Test. In IEEE Trans. on Computer-Aided Design of Integrated Circuit and System, vol. 12(8), Aug. 1993. cited by other .
J. Savir and S. Patil. Broad-Side Delay Test. In Transactions on Computer-Aided Design of Intergrated Circuit and System, vol. 13(8), Aug. 1994. cited by other .
J. Saxena, K. M. Butler, J. Gatt, R. R. S. P. Kumar, S. Basu, D. J. Campbell, and J. Berech. Scan-Based Transition Fault Testing--Implementation and Low Cost Test Challenges. In Proceedings IEEE International Test Conference, pp. 1120-1129, 2002. cited by other .
G. L. Smith. Model for Delay Faults Based Upon Paths. In Proceedings IEEE International Test Conference, pp. 342-349, 1985. cited by other .
N. Tamarapalli and J. Rajski. Constructive Multi-Phase Test Point Insertion for Scan-Based BIST. In Proceedings IEEE International Test Conference, pp. 649-658, 1996. cited by other .
J. A. Waicukauski, E. Lindbloom, B. K. Rosen, and V. S. Iyengar. Transition Fault Simulation. In IEEE Design & Test of Computers, pp. 32-38, Apr. 1987. cited by other .
S. Wang and S. K. Gupta. DS-LFSR: A BIST TPG for Low Switching Activity. In IEEE Trans. onComputer-Aided Design of Integrated Circuit and System, vol. 21(7), Jul. 2002. cited by other .
IEEE standard 1149.1-2001. IEEE Standard Test Access Port and Boundary-Scan Architecture. IEEEE standard board, New York, N.Y., pp. 1-119, 1990. cited by other.

Primary Examiner: Do; Thuan

Parent Case Text

I.A. RELATED APPLICATIONS

This Application claims priority from U.S. Provisional Application Ser. No. 60/447,272 filed Feb. 14, 2003, now abandoned, the contents of which are incorporated herein by reference.

Claims

What is claimed is:

1. A logic circuit comprising at least one input, one output and a delay fault circuit, said delay fault circuit including: a first standard scan cell; a combinational test point positioned immediately after the first standard scan cell in a scan chain; and a second standard scan cell positioned immediately after the combinational test point in the scan chain.

2. The logic circuit of claim 1, where the combinational test point is positioned to prevent shift dependency between the first standard scan cell and the second standard scan cell.

3. The logic circuit of claim 1, where the first and second standard scan cells are flip-flops.

4. The logic circuit of claim 1, where the combinational test point comprises an AND gate.

5. The logic circuit of claim 1, where the combinational test point comprises an OR gate.

6. The logic circuit of claim 1, where the combinational test point comprises an AND-OR gate.

7. The logic circuit of claim 1, where the logic circuit is testable under a full standard scan environment.

8. The logic circuit of claim 1, where the logic circuit is testable under a partial standard scan environment.

9. The logic circuit of claim 1, where the logic circuit includes at least one enhanced scan cell.

10. The logic circuit of claim 1, where the circuit is structured so that at least one stuck-at fault in the circuit can be tested.

11. The logic circuit of claim 1, where the circuit is structured so that at least one delay fault in the circuit can be tested.

12. A logic circuit comprising at least one input, one output and a delay fault circuit, said delay fault circuit including: a first standard scan cell; a test point positioned immediately after the first standard scan cell in a scan chain; and a second standard cell positioned immediately after the test point in the scan chain, where the test point is positioned to prevent shift dependency identified to occur between the first and second standard scan cells in the delay fault circuit.

13. The logic circuit of claim 12, where the position of the test point is determined based on a functional analysis of the circuit.

14. The logic circuit of claim 12, wherein the test point is a dummy scan flip-flop in a scan chain that does not provide input to any primary inputs in the logic circuit.

15. The logic circuit of claim 12, wherein the test point is a combinational test point.

16. The logic circuit of claim 12, wherein the position of the test point is determined by: identifying dependency untestable transition delay faults; for every such fault, generating a test cube pair for the fault if the fault has a minimum test generation cost, and if there is no conflict with any other test cube pair in a current test cube pair set, adding the test cube pair into the current test cube pair set and updating a current test point vector based on the current test cube pair set; and generating a global test point vector based on the current test point vector, where the global test point vector specifies the position where the test point should be inserted.

17. The logic circuit of claim 16, where the global test vector also specifies what type of test point should be inserted.

18. A method of testing a logic circuit comprising: loading a first test pattern into a first standard scan cell in a scan chain; loading an output of the first standard cell into a combinational test point in the scan chain; and loading an output of the combinational test point into a second standard scan cell in the scan chain.

19. The method of testing a logic circuit as in claim 18, where the combinational test point prevents shift dependency between the first standard scan cell and the second standard scan cell.

20. The method of claim 18, where the logic circuit is testable under a full standard scan environment.

21. The method of claim 18, where the logic circuit is testable under a partial standard scan environment.

22. The method of claim 18, where the logic circuit includes at least one enhanced scan cell.

23. The method of claim 18, where at least one stuck-at fault in the logic circuit is tested.

24. The method of claim 18, where at least one delay fault in the logic circuit is tested.

25. The method of claim 18, where the combinational test point comprises an AND gate.

26. The method of claim 18, where the combinational test point comprises an OR gate.

27. The method of claim 18, where the combinational test point comprises an AND-OR gate.

28. An integrated circuit comprising at least one logic circuit and at least one delay fault circuit, the delay fault circuit including: a first standard scan cell in a scan chain; a combinational test point positioned immediately after the first standard scan cell in the scan chain; and a second standard scan cell positioned immediately after the combinational test point in the scan chain.

29. The integrated circuit of claim 28, where the first and second scan cells are flip-flops.

30. The integrated circuit of claim 28, where the combinational test point is positioned to prevent shift dependency between the first standard scan cell and the second standard scan cell.

31. The integrated circuit of claim 28, where the combinational test point further comprises an AND gate, an OR gate, or an AND-OR gate.

32. A method for designing a circuit that is testable using a scan-based technique comprising: accurately identifying, based on a functional analysis of the circuit, at least one pair of standard scan cells in the circuit where shift dependency occurs; and inserting a test point at the identified point in the circuit.

33. The method of claim 32, where the inserted test points are dummy scan memories.

34. The method of claim 33, where the scan memories are flip-flops.

35. The method of claim 32, where the inserted test points are combinational gates.

36. The method of claim 32, where the points in the circuit where shift dependency occurs are identified using an automatic test program generator (ATPG).

37. The method of claim 36, where the ATPG identifies scan memories between which the test points are inserted.

38. The method of claim 37, where the scan memories are flip-flops.

Description

I.B. FIELD

The present disclosure teaches techniques related to enhancing coverage of delay faults in scan designs for testing of circuits.

I.C. BACKGROUND

1. References

The following papers provide useful background information, for which they are incorporated herein by reference in their entirety, and are selectively referred to in the remainder of this disclosure by their accompanying reference numbers in square brackets (i.e., [3] for the third numbered paper by J. Monteiro and S. Devdas):

[1] D. Belete, A. Razdan, W. Schwarz, R. Raina, C. Hawkins, and J. Morehead. Use of DFT Techniques In Speed Grading a 1 GHz+ Microprocessor. In Proceedings IEEE International Test Conference, pages 1111 1119, 2002.

[2] K.-T. Cheng, S. Devadas, and K. Keutzer. A Partial Enhanced-Scan Approach to Robust Delay-Generation for Sequential Circuits}. In Proceedings IEEE International Test Conference, pages 403 410, 1991.

[3] V. Dabholkar, S. Chakravarty, I. Pomeranz, and S. Reddy. Techniques for Minimizing Power Dissipation in Scan and Combinational Circuits During Test Application. In IEEE Trans. on Computer-Aided Design of Integrated Circuit and System, Vol. 17(12), December 1998.

[4] B. Dervisoglu and G. Stong. Design for Testability: Using Scanpath Techniques for Path-Delay Test and Measurement. In Proceedings IEEE International Test Conference, pages 365 374, 1991.

[5] S. Gerstendorfer and H.-J. Wunderlich. Minimized Power Consumption for Scan-Based BIST. In Proceedings IEEE International Test Conference, pages 77 84, 1999.

[6] M. J. Geuzebroek, J. T. van der Linden, and A. J. van de Goor. Test Point Insertion for Compact Test Sets}. In Proceedings IEEE International Test Conference, pages 292 301, 2000.

[7] P. Goel. An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits}. In IEEE Trans. on Computers, Vol. C-30(3), March 1981.

[8] L. H. Goldstein and E. L. Thigpen. SCOAP: Sandia Controllability/Observability Analysis Program. In Proceedings IEEE-ACM Design Automation Conference, pages 190 196, 1980.

[9] W. Mao and M. D. Ciletti. Reducing Correlation to Improve Coverage of Delay Faults in Scan-Path Design}. In IEEE Trans. on Computer-Aided Design of Integrated Circuit and System, Vol. 13(5), May 1994.

[10] I. Pomeranz and S. M. Reddy. On Achieving Complete Coverage of Delay Faults in Full Scan Circuits using Locally Available Lines. In Proceedings IEEE International Test Conference, pages 923 931, 1999.

[11] J. Savir and R. Berry. At-Speed Test is not Necessarily an AC Test. In Proceedings IEEE International Test Conference, pages 722 728, 1991.

[12] J. Savir and S. Patil. Scan-Based Transition Test. In IEEE Trans. on Computer-Aided Design of Integrated Circuit and System, Vol. 12(8), August 1993.

[13] J. Savir and S. Patil. Broad-Side Delay Test. In Transactions on Computer-Aided Design of Integrated Circuit and System, Vol. 13(8), August 1994.

[14] J. Saxena, K. M. Butler, J. Gatt, R. R, S. P. Kumar, S. Basu, D. J. Campbell, and J. Berech. Scan-Based Transition Fault Testing--Implementation and Low Cost Test Challenges. In Proceedings IEEE International Test Conference, pages 1120 1129, 2002.

[15] G. L. Smith. Model for Delay Faults Based Upon Paths. In Proceedings IEEE International Test Conference, pages 342 349, 1985.

[16] IEEE standard 1149.1-2001. IEEE Standard Test Access Port and Boundary-Scan Architecture. IEEEE standard board, New York, N.Y., 1990.

[17] N. Tamarapalli and J. Rajski. Constructive Multi-Phase Test Point Insertion for Scan-Based BIST. In Proceedings IEEE International Test Conference, pages 649 658, 1996.

[18] J. A. Waicukauski, E. Lindbloom, B. K. Rosen, and V. S. Iyengar. Transition Fault Simulation. In IEEE Design & Test of Computers, pages 32 38, April 1987.

[19] S. Wang and S. K. Gupta. DS-LFSR: A BIST TPG for Low Switching Activity. In IEEE Trans. on Computer-Aided Design of Integrated Circuit and System, Vol. 21(7), July 2002.

2. Related Work

Ascertaining correct operation of digital circuits at desired speed is becoming more important. Conventionally, at-speed testing was typically accomplished with functional test patterns. However, developing functional test patterns that attain satisfactory fault coverage is unacceptable for large scale designs due to the prohibitive development cost. Even if functional test patterns that can achieve high fault coverage are available, applying these test patterns at-speed for high speed chips requires very stringent timing accuracy, which can only be provided by very expensive automatic test equipments (ATEs).

The scan-based delay test approach where test patterns are generated by an automatic test pattern generator (ATPG) on designs that involve scan chains is increasingly used as a cost efficient alternative to the at-speed functional pattern approach to test large scale chips for performance-related failures [1, 14].

The transition delay fault model [18] is widely used in industry for its simplicity. Because of its similarity to the stuck-at fault model, ATPGs and fault simulators that are developed for stuck-at faults can be reused for transition delay faults with minor modifications. Unlike the path delay fault model [15] where the number of target faults is often exponential, the number of transition delay faults is linear to the number of circuit lines. This eliminates the need for critical path analysis and identification procedures, which are necessary for the path delay fault model.

Detection of a delay fault requires application of a two-pattern test; the first pattern that initializes the targeted faulty circuit line to a desired value and the second pattern that launches a transition at the circuit line and propagates the fault effect to one or more primary outputs or scan flip-flops. There are two different approaches to apply two-pattern tests in standard scan environment. In both approaches, the first pattern of a test pattern pair is scanned in through scan chains in the same fashion as a test pattern for a stuck-at fault is scanned in and the second pattern is derived from the first pattern.

In the first approach, referred to as skewed-load [12] or launch-by-shift, the second pattern is obtained by shifting in the first pattern by one more scan flip-flop. Hence, given a first pattern, there are only two possible patterns for the second pattern that differs only at the value for the first scan flip-flop whose scan input is connected to the scan chain input. This shift dependency restricts the number of combinations of test pattern pairs to 2.sup.n.times.2 [11] in standard scan environment, where n is the number of scan flip-flops in the scan chain.

In the second approach, referred to as broadside-load [12, 13] or launch-from-capture, the second pattern is obtained from the circuit response to the first pattern. Hence, the second pattern is given by the circuit response to the first pattern. Due to restriction to apply the second pattern in both approaches, transition delay fault coverage in standard scan environment is sometimes significantly lower than stuck-at fault coverage [12].

Several conventional techniques have been proposed to improve delay fault coverage in standard scan environment. In the techniques described in [6, 10], extra logic is inserted into the functional path to improve delay fault coverage in standard scan environment. A drawback of this method is performance degradation entailed due to additional logic that is inserted into the functional path. Enhanced scan testing [4] is a powerful scan technique that allows applying all possible 2.sup.n.times.(2.sup.n-1) combinations of pattern pairs to the circuit. Such faults that are not testable under standard scan environment but testable under full enhanced scan environment are referred to herein as dependency untestable faults. Since this technique requires to replace all standard scan cells by enhanced scan cells, which can hold two bits, the drawback of enhanced scan testing is high area overhead of enhanced scan cells.

In order to reduce area overhead, partial enhanced scan technique where only selected scan flip-flops are replaced by enhanced scan flip-flops is proposed by [2]. As a similar approach to the partial enhanced scan technique, in [12], dummy flip-flops are inserted to break shift dependency between selected pairs of adjacent scan flip-flops in the scan chain. In [9, 11], scan flip-flops are rearranged to minimize the number of pairs of adjacent scan flip-flops that drive same fanout cones. This reduces the number of transition delay faults that are untestable due to shift dependency between scan flip-flops. However, rearranging scan chains to enhance fault coverage may increase scan path routing overhead. Furthermore, for circuits where most state inputs are topologically correlated, satisfactory transition delay fault coverage may not be achieved in any order of scan flip-flops.

A simple example shows some problems with conventional approaches. FIG. 1 shows a circuit that has three state inputs, s.sub.1, s.sub.2, and s.sub.3, which are respectively driven by scan flip-flops D.sub.1, D.sub.2, and D.sub.3 during test application. Consider generating a test pattern pair V={V.sub.1, V.sub.2} for the slow-to-rise (STR) fault at line l that is to be applied to the circuit by using the conventional skewed-load approach. Initializing line l to a 0 requires assigning either s.sub.1 or s.sub.2 to a 0 at initialization test cycle T.sub.1. On the other hand, activating and propagating the STR fault at line l require assigning all state inputs s.sub.1, s.sub.2, and s.sub.3 to 1's at activation and propagation test cycle T.sub.2. However, if D.sub.1 (D.sub.2) is loaded with a 0 at time T.sub.1 to initialize line l, then the 0 at D.sub.1 (D.sub.2) shifts to D.sub.2 (D.sub.3) at the next cycle T.sub.2 and s.sub.2 (s.sub.3) is assigned a 0. This conflicts with the value 1, which is required at s.sub.2 (s.sub.3) to activate and propagate the fault effect. Hence, the STR fault at line l is untestable by the skewed-load approach in standard scan environment.

3. Definitions and Notations

Several definitions and notations are provided herein for a better understanding of this disclosure. It should be noted that these are only illustrative and should not be construed to limit the scope of the claimed invention. In this disclosure it is assumed that the sequential circuit under test (CUT), which has m primary inputs, p.sub.1, p.sub.2, . . . , p.sub.m, and n state inputs, s.sub.1, s.sub.2, . . . , s.sub.n, employs full scan and state input s.sub.i, where i=1, 2, . . . , n, is driven by a corresponding scan flip-flop D.sub.i during test application. It is also assumed that all scan flip-flops in the CUT, D.sub.1, D.sub.2, . . . , D.sub.n, where n is the number of scan flip-flops in the scan chain (state inputs), are connected to comprise one scan chain without loss of generality. The chain input of the scan chain is connected to the scan input of scan flip-flop D.sub.1 and the scan output of D.sub.1 is connected to the scan input of D.sub.2, and so on, and finally the scan output of D.sub.n is connected to the scan chain output. It is further assumed that the scan path is constructed with only non-inverting outputs of scan flip-flops, which are also used to drive the functional path. Under the assumption, during scan shift cycles, the value loaded into scan flip-flop D.sub.i at time t is always the same as the value at the immediate predecessor of D.sub.i, i.e., D.sub.i-1 at the previous cycle time t-1. The above two assumptions are only for convenience of illustration and the disclosed techniques can be used for CUTs that have multiple scan chains and whose whole or part of scan paths are constructed by inverting outputs of scan flip-flops.

Let V.sup.j={V.sub.1.sup.j, V.sub.2.sup.j} be a two pattern test (or test cube pair), which may be fully or partially specified, where V.sub.1.sup.j is the initialization pattern and V.sub.2.sup.j is the activation and propagation pattern of V.sup.j. Each pattern V.sup.j.sub.f, where f=1 or 2, consists of two parts: primary input part that is applied to primary inputs and scan input part that is applied to scan inputs.

The scan input part of initialization pattern V.sup.j.sub.1 is applied to the CUT at initialization test cycle T.sup.j.sub.1 via the scan chain and corresponding activation and propagation pattern V.sup.j.sub.2 is applied the CUT at activation and propagation test cycle T.sup.j.sub.2 by functional justification (when the broadside-load approach is used) or a shift operation (when the skewed-load approach is used).

If two pattern tests are applied via standard scan chains by using the skewed-load approach, all transition delay faults that require a 1 (0) at state input s.sub.i-1 at the initialization test cycle and a 0 (1) at state input s.sub.i at the activation and propagation test cycle to be detected are untestable even if they are testable in enhanced scan environment. Hence, a pair of values, the value assigned at s.sub.i-1 in V.sup.j.sub.1 and the value assigned at s.sub.i in V.sup.j.sub.2 are important to determine testability of transition delay faults when the skewed-load approach is used. We introduce d.sup.j.sub.i to denote the pair of values, i.e., the value assigned at s.sub.i-1 in V.sup.j.sub.1 and the value assigned at s.sub.i in V.sup.j.sub.2. If two pattern test V.sup.j is applied via a standard scan chain by using the skewed-load approach and V.sup.j is fully specified, then d.sup.j.sub.i is always 00 or 11.

Unlike state inputs, it is assumed that primary inputs are fully controllable, i.e., completely independent patterns can be applied to primary inputs at any two consecutive test cycles.

II. SUMMARY

It will be significantly advantageous to overcome problems noted above and to enhance fault coverage for standard scan designs.

To overcome some of the problems discussed above there is provided a logic circuit comprising at least one input, one output and a delay fault circuit. The delay fault circuit includes a first standard scan cell, a combinational test point positioned immediately after the first standard scan cell in a scan chain and a second standard scan cell positioned immediately after the combinational test point in the scan chain.

In a specific enhancement, the combinational test point is positioned to prevent shift dependency between the first standard scan cell and the second standard scan cell.

In another specific enhancement the first and second standard scan cells are flip-flops.

In another specific enhancement the combinational test point comprises an AND gate.

In another specific enhancement the combinational test point comprises an OR gate.

In another specific enhancement the combinational test point comprises an AND-OR gate.

In another specific enhancement the logic circuit is testable under a full standard scan environment.

In another specific enhancement the logic circuit is testable under a partial standard scan environment.

In another specific enhancement the logic circuit includes at least one enhanced scan cell.

In another specific enhancement the circuit is structured so that at least one stuck-at fault in the circuit can be tested.

In another specific enhancement the circuit is structured so that at least one delay fault in the circuit can be tested.

Another aspect of the disclosed teaching is a logic circuit comprising at least one input, one output and a delay fault circuit. The delay fault circuit including a first standard scan cel, a test point positioned immediately after the first standard scan cell in a scan chain and a second standard cell positioned immediately after the test point in the scan chain. The test point is positioned to prevent shift dependency identified to occur between the first and second standard scan cells in the delay fault circuit.

In a specific enhancement the position of the test point is determined based on a functional analysis of the circuit.

In another specific enhancement the test point is a dummy scan flip-flop in a scan chain that does not provide input to any primary inputs in the logic circuit.

In another specific enhancement the test point is a combinational test point.

In another specific enhancement the position of the test point is determined by identifying dependency untestable transition delay faults. For every such fault, generating a test cube pair for the fault if the fault has a minimum test generation cost, and if there is no conflict with any other test cube pair in a current test cube pair set, adding the test cube pair into the current test cube pair set and updating a current test point vector based on the current test cube pair set; and generating a global test point vector based on the current test point vector, where the global test point vector specifies the position where the test point should be inserted.

In another specific enhancement, the global test vector also specifies what type of test point should be inserted.

Another aspect of the disclosed teachings is a technique for testing a logic circuit comprising loading a first test pattern into a first standard scan cell in a scan chain, loading an output of the first standard cell into a combinational test point in the scan chain; and loading an output of the combinational test point into a second standard scan cell in the scan chain.

In another specific enhancement the combinational test point prevents shift dependency between the first standard scan cell and the second standard scan cell.

In another specific enhancement at least one stuck-at fault in the logic circuit is tested.

In another specific enhancement at least one delay fault in the logic circuit is tested.

Another aspect of the disclosed teachings is an integrated circuit comprising at least one logic circuit and at least one delay fault circuit. The delay fault circuit includes a first standard scan cell in a scan chain, a combinational test point positioned immediately after the first standard scan cell in the scan chain and a second standard scan cell positioned immediately after the combinational test point in the scan chain.

In another specific enhancement the first and second scan cells are flip-flops.

In another specific enhancement the combinational test point is positioned to prevent shift dependency between the first standard scan cell and the second standard scan cell.

In another specific enhancement the combinational test point further comprises an AND gate, an OR gate, or an AND-OR gate.

Yet another aspect of the disclosed teachings is amethod for designing a circuit that is testable using a scan-based technique comprising accurately identifying, based on a functional analysis of the circuit, at least one pair of standard scan cells in the circuit where shift dependency occurs and inserting a test point at the identified point in the circuit.

In a specific enhancement the inserted test points are dummy scan memories.

In another specific enhancement the points in the circuit where shift dependency occurs are identified using an automatic test program generator (ATPG).

More specifically, the ATPG identifies scan memories between which the test points are inserted.

Still another aspect of the disclosed teachings is a method of testing a circuit comprising applying a first set of two pattern tests using a skewed-load approach under standard scan environments. A second set of two pattern tests that target faults that are not detected in step a is applied using a broadside-load approach under standard scan environments. Test efforts required for remaining faults are divided into a plurality of sub-phases and under each sub-phase enabling a different set of test points in every activation and propagation test cycle while the test points other than said different set of test points remain disabled.

In a specific enhancement standard scan environments comprise testing environments where only a subset of all possible combination of test pattern pairs are applied to test the circuit.

In another specific enhancement the circuit includes test points at points in the circuit where shift dependency occurs in a standard scan environment.

In another specific enhancement during the skewed-load approach, a second pattern from the first set of two patterns is obtained by shifting in a first pattern from the two patterns by one scan memory element.

In another specific enhancement during the broadside-load approach, a second pattern from the second set of two patterns is obtained by a response of the circuit to the first pattern.

In another specific enhancement when test points are disabled for each first flip-flop and second flip-flop, the first and second flip-flops being adjacent in a scan chain, a value of the second flip-flop at a test cycle is maintained to be the same as a value of the second flip-flop at a previous test cycle.

In another specific enhancement when a test point is enabled for each first flip-flop and second flip-flop, the first and second flip-flops being adjacent in a scan chain, a value of the second flip-flop at a test cycle is altered by the test point between the first and second flip-flops.

More specifically at least two compatible test point signals are grouped together to be driven by a common control signal.

More specifically at least a at least two inversely compatible test points are grouped together to be driven by a common control signal.

Yet another aspect of the disclosed teachings is a method for designing test points for testing a circuit and identifying test points that should be enabled during each sub-phase of the testing, comprising: a) identifying dependency untestable transition delay faults; b) initializing global variables; c) initializing a current test cube pair set and a current test point vector; d) stopping the procedure if no more untested fault exists in a fault list; e) selecting and marking an unmarked fault that has a minimum test generation cost in the fault list;f) generating a test cube pair for the unmarked fault; g) if the test cube pair generated in step f cannot be added to the current test cube pair set due to a conflict with any other test cube pair in the current test cube pair set, discarding the generated test cube pair and going to step e; h) adding the generated test cube pair into the current test cube pair set and updating the current test point vector accordingly; and i) if no more test cube pair can be added into the test cube pair set without conflict with other test cube pairs in the current test cube pair set, updating a global test point vector and going to step c.

In a specific enhancement dependency untestable faults comprise faults that are not testable under standard scan environments but are testable under full enhanced scan environments.

In another specific enhancement full enhanced scan environments comprise testing environments where all possible combination of test pattern pairs are applied to test the circuit.

In another specific enhancement standard scan environments comprise testing environments where only a subset of all possible combination of test pattern pairs are applied to test the circuit.

In another specific enhancement in step f a test cube pair is generated such that a minimum number of test points are generated considering the current test point vector and the global test point vector.

In another specific enhancement the test cube pair is generated for two different time frames, one for an initialization pattern and another for a propagation pattern.

In another specific enhancement when more than one backtrace is possible, a backtrace path that generates minimum controllability costs are used.

In another specific enhancement controllability costs include a first time frame controllability cost and a second time frame controllability cost.

In another specific enhancement controllability costs include hardware cost to be incurred when a line in the circuit is set to a binary value.

In another specific enhancement a test pair is generated consider a test generation cost that is a sum of a controllability cost for an initialization, a controllability cost for activation and an observability cost which is a minimum cost for transferring an output of a propagated fault to a primary output of the circuit.

Other aspects of the disclosed teachings are computer program products, including a computer readable media comprising instructions, wherein said instructions comprise instruction for enabling a computer to perform testing for circuits using a scan-based technique using the above procedures.

III. BRIEF DESCRIPTION OF THE DRAWINGS

The disclosed teachings will become more apparent by describing in detail examples and embodiments thereof with reference to the attached drawings in which:

FIG. 1 shows an example of shift dependency.

FIG. 2 shows examples illustrating how shift dependency is broken by (a) inserting a dummy flip-flop and (b) inserting an OR gate.

FIG. 3(a) (d) illustrates example implementations of four different types of test points that can be inserted to enhance transition.

FIG. 4 shows an illustrative test point vector computation finite state machine.

FIG. 5 shows example test cube sets and test point vectors.

FIG. 6 shows an example of clustering test point enabled signals.

FIG. 7(a) (b) shows controlling cluster test point enable signals using test input pins and test flip-flops respectively.

FIG. 8 depicts a table showing experimental results.

IV. DETAILED DESCRIPTION

IV.A. Synopsis and Advantages

This disclosure teaches an ATPG-based technique to enhance delay fault coverage for standard scan designs. Since necessary test points are identified from suitable test cube pairs for target faults, which are generated by a special ATPG, rather than circuit topology, it can drastically reduce hardware overhead compared to circuit topology-based techniques. Unlike the conventional technique described on [12], which uses only flip-flops to break shift dependency between adjacent scan flip-flops, the disclosed technique inserts combinational gates as well as flip-flops. This can minimize the increase in scan chain lengths, which determines test application time in scan testing, due to adding extra flip-flops into scan chains. Since combinational gates can be implemented with less silicon area, this can also reduce hardware overhead.

It should be noted that even thought the examples and illustrations show scan flip-flops, the techniques are extendible to any types of memory elements that are used instead of flip-flops.

IV.B. Motivation

Unlike as in the non-limiting example of FIG. 1 , consider inserting a dummy scan flip-flop between D.sub.1 and D.sub.2 (see FIG. 2(a)). Again, if D.sub.1 is assigned a 0 at T.sub.1, then the 0 at D.sub.1, which is applied to initialize line l at T.sub.1, shifts to the dummy flip-flop at the next cycle T.sub.2. If the dummy flip-flop is loaded with a 1 and D.sub.2 is also loaded with a 1 at T.sub.1, these 1's shift to D.sub.2 and D.sub.3 at T.sub.2, respectively. Hence, if a 1 is scanned into D.sub.1 from the scan chain input at T.sub.2, then all state inputs s.sub.1, s.sub.2, and s.sub.3 are assigned 1's and the fault effect at l is activated and propagated to the circuit output at T.sub.2.

IV.C. Examples Illustrating Concepts Underlying the Disclosed Teachings

FIG. 2(b) illustrates that the STR fault at l can also be detected by inserting a two-input OR gate between D.sub.1 and D.sub.2. Assume that D.sub.1 is assigned a 0 and D.sub.2 and D.sub.3 are assigned 1's at T.sub.1. If signal E.sub.o which drives an input of the OR gate, is assigned a 1 at T.sub.2 then D.sub.2 is loaded with a 1 instead of the 0, which is shifted from D.sub.1. Hence, scan flip-flops D.sub.2 and D.sub.3 can be assigned 1's at T.sub.2 that are required to activate and propagate the STR at l (D.sub.1 can be assigned a 1 by scanning a 1 into the scan chain input at T.sub.2). In the disclosed techniques, test points are inserted into the scan path. Because of inserting test points in scan paths, no performance degradation is entailed by inserted test points.

An advantage of inserting combinational gates as test points over dummy flip-flops, which can also be considered as a special type of test point, is that combinational gates such as two-input AND and OR gates can be implemented with less silicon area than flip-flops. Second, test application time of scan testing is typically determined by the number of test patterns and the scan chain length, which is determined by the number of scan flip-flops in the longest scan chain. Hence, inserting dummy scan flip-flops increases test application time by increasing the scan chain length.

In contrast, inserting a combinational gate does not increase scan chain length. Another advantage is reduction in test data volume. Since test data should be provided for inserted dummy flip-flops as well as regular scan flip-flops, inserting dummy flip-flops increases test data volume, which is one of the major factors that determine test cost. Test data to control test points should be provided also to combinational test points from an external ATE. Hence, it is of importance to minimize the number of test points to minimize test data volume. Algorithms to minimize the number of test points are described in subsequent sub-sections. Test data to control test points are further reduced by merging control signals for multiple test points into a single control signal and driving these merged control signals by a control register rather than external input pins (see Section IVG).

FIG. 3 provides illustrative, non-limiting examples of four different types of test points that can be inserted to enhance transition delay fault coverage for standard scan designs and their possible d.sup.j.sub.i values, i.e., the value assigned at state input s.sub.i-1 in V.sup.j.sub.1 and the value assigned at state input s.sub.i in V.sup.j.sub.2, that can be applied to a pair of adjacent state inputs s.sub.i-1 and s.sub.i when each different type of test point is inserted between D.sub.i-1 and D.sub.i. Note that d.sup.j.sub.i=01 or 10 cannot be applied in standard scan environments (Note that in this example it is assumed that the scan path is constructed with only non-inverting outputs of scan flip-flops).

If an AND gate is inserted between scan flip-flops D.sub.i-1 and D.sub.i, d.sup.j.sub.i values that can be applied to s.sub.i-1 and s.sub.i are 00 and 10. Hence, if there exists a dependency untestable transition delay fault that requires d.sup.j.sub.i=01 to be detected, then the fault can be detected by inserting an OR gate between D.sub.i-1 and D.sub.i.

Likewise if an OR gate is inserted between scan flip-flops D.sub.i-1 and D.sub.i, d.sup.j.sub.i values that can be applied to s.sub.i-1 and s.sub.i are 11 and 01. Hence, if there exists a dependency untestable transition delay fault that requires d.sup.j.sub.i=10 to be detected, then the fault can be detected by inserting an AND gate between D.sub.i-1 and D.sub.i.

If there is a set of transition delay faults that require d.sup.j.sub.i=01 to be detected and there is another set of faults that require d.sup.j.sub.i=10 to be detected, then an AND-OR (or OR-AND) complex gate or dummy flip-flop can be inserted between D.sub.i-1 and D.sub.1 to detect all of them. While test patterns for a set of transition delay faults that require d.sup.j.sub.i=01 to be detected are being applied to the CUT, the test point enable signal for the OR test point, E.sub.o, is set to a 1 to enable the OR test point at every activation and propagation test cycle. On the other hand, while two pattern tests for the other set of transition delay faults that require d.sup.j.sub.i=10 to be detected are being applied to the CUT, the test point enable signal for the AND test point, E.sub.A, is set to a 1 to enable the AND type test point and E.sub.o is set to a 0 to propagate the 0 at the output of the AND gate to the scan input of D.sub.i.

Also when an AND test point is inserted, the test point needs to be disabled while test patterns for faults that require d.sup.j.sub.i=11, i.e., s.sub.i-1=1 (0) in V.sup.j.sub.1 and s.sub.i=1 in V.sup.j.sub.2, to be detected are applied. Likewise when an OR test point is inserted, the test point needs to be disabled while test patterns for faults that require d.sup.j.sub.i=00, i.e., s.sub.i-1=0 in V.sup.j.sub.1 and s.sub.i=0 in V.sup.j.sub.2, to be detected are applied.

The test application as in the disclosed teachings includes three phases. In the first test application phase, two pattern tests are applied by the skewed-load approach under standard scan environment. In the second application phase, test patterns, which target faults that are not detected during the first test application phase, are applied by the broadside-load approach also under standard scan environment. The first and the second phase can be exchanged without affecting resulting quality of testing. The third application phase is further divided into several sub-phases.

In each sub-phase of the third phase, a different set of test points are enabled every activation and propagation test cycle and the rest of test points are always disabled. For all pairs of adjacent scan flip-flops D.sub.i-1 and D.sub.i whose test points are disabled, the value at flip-flop D.sub.i at test cycle t is the same as the value at its immediate predecessor D.sub.i-1 at the previous test cycle t-1.

IV.D. Comparisons with Prior Work

Unlike combinational test points such as AND and OR gates, dummy flip-flops require no test point enable signals, which entail additional routing overhead. However, dummy flip-flops contribute to extra power consumption even during normal operation (note that combinational test points do not contribute to power consumption since scan chains are not used during normal operation). Hence, if a large number of dummy scan flip-flops are inserted, then clock signals that drive dummy flip-flops should be shut down during circuit's normal operation to save power in power conscious chips such as chips for portable devices. This requires driving dummy flip-flops with a separate clock tree or through individual clock gating logics. Hence, added clock tree(s) or clock gating logics for dummy flip-flops may cost even higher routing as well as area overhead than test point enable signals of combinational test points. It is well known that power dissipation during test application is often significantly higher than that during normal operation [3, 19, 5] due to excessive switching activity. Since dummy flip-flops can have transitions during entire scan shift cycles contributing to power dissipation, inserting dummy flip-flops will exacerbate this problem. In contrast, since combinational test points can have transitions only at activation and propagation cycles, which occur every n+1 test cycles, where n is the number of scan flip-flops in the longest scan chain, combinational test points contribute to power dissipation very little even during test application.

As described in the preceding paragraph, [9, 12] use topological correlation measures to decide between which pairs of scan flip-flops dummy flip-flops are to be inserted and orders of scan flip-flops that minimize decrease in fault coverage due to shift dependency. In order to break shift dependency between all pairs of adjacent scan flip-flops, a large number of dummy flip-flops need to be inserted for some circuits [12]. If both skewed-load and broadside-load approaches are used, many pairs of adjacent flip-flops that have topological correlation (drive same fanout cones) may not cause any dependency untestable fault since some faults that cannot be detected by the skewed-load approach due to shift dependency between adjacent flip-flops can be detected by the broadside-load approach. Hence, inserting dummy flip-flops, replacing scan flip-flops by enhanced scan flip-flops, or reordering scan flip-flops based only on topological correlation measures, may result in unnecessarily high area and routing overhead.

Unlike [9, 12], [2] uses pre-computed test patterns to select scan flip-flops that are replaced by enhanced scan flip-flops; if there exists pair of adjacent state inputs s.sub.i-1 and s.sub.i for which d.sup.j.sub.i is 01 or 10 (under the assumption that the scan path is constructed with only non-inverting outputs of scan flip-flops) in a two pattern test V.sup.j of the pre-computed test pattern set, scan flip-flop D.sub.i is replaced by an enhanced scan flip-flop. Typically, there may be a large number of two pattern tests for every dependency untestable transition delay fault. Hence, significantly different results in terms of hardware overhead can be obtained depending on which test patterns are used for consideration. In contrast to [2] where test patterns are generated in advance, in the disclosed technique, only suitable test cube pairs, which will result in minimal number of test points, are generated by a special ATPG.

IV.E. Scan Path Test Point Insertion

It is important to minimize the number of test points to minimize hardware overhead and test data volume. In the disclosed technique, one way of determining the test points to be inserted is to dynamically compute from test cube pairs for transition delay faults that are not testable in standard scan environment. A test cube pair generated thus is added to a test cube pair set, which is called the current test cube pair set. For example, if there currently exists test cube pair V.sup.a in the current test cube pair set in which values for a pair of adjacent state inputs s.sub.i-1 and s.sub.i are assigned a 0 in V.sup.a.sub.1 and a 1 in V.sup.a.sub.2, respectively, i.e., d.sup.a.sub.i=01, then an OR gate is required to be inserted and enabled between scan flip-flops D.sub.i-1 and D.sub.i to apply V.sup.a to the CUT (see FIG. 3). If d.sup.b.sub.i=00 in a newly generated test cube pair V.sup.b, then V.sub.b conflicts with V.sup.a at s.sub.i since V.sup.b cannot be applied to the CUT with the OR gate enabled between D.sub.i-1 and D.sub.i. Generated test cube pairs are placed into the current test cube pair set until no more test cube pairs can be added without conflict with test cube pairs that already exist in the test cube pair set.

1. Test Point Vector

A test point vector, which carries information on which test points are enabled in the corresponding test application sub-phase, is computed from a set of test cube pairs. The test point vector for k-th test cube pair set, TP.sub.k={tp.sup.k.sub.1, tp.sup.k.sub.2, . . . , tp.sup.k.sub.n}, is an n-bit tuple where tp.sup.k.sub.i .epsilon. {W, O, A}, (i=1, 2, 3, . . . , n, where n is the number of state inputs) is computed from test cube pair set C.sup.k as follows: if there is at least one two pattern test cube pair V.sup.j in set C.sup.k where d.sup.j.sub.i=01, i.e., s.sub.i-1}=0 in V.sup.j.sub.1 and s.sub.i=1 in V.sup.j.sub.2, then tp.sup.k.sub.i is assigned O; otherwise tp.sup.k.sub.i is assigned W. Likewise, if there is at least one two pattern test cube pair V.sup.j in set C.sup.k where d.sup.j.sub.i=10, i.e., s.sub.i-1}=1 in V.sup.j.sub.1 and s.sub.i=1 in V.sup.j.sub.2, then tp.sup.k.sub.i is assigned A; otherwise tp.sup.k.sub.i is assigned W. If tp.sup.k.sub.i=W, no test point between D.sub.i-1 and D.sub.i, if any, is enabled during the k-th test application sub-phase. Therefore, if tp.sup.k.sub.i=W, the value assigned to s.sub.i at every activation and propagation test cycle T.sup.r.sub.2, (r=1, 2, . . . , yk, where yk is the number of two pattern tests applied during k-th test application sub-phase) is always the same as the value assigned to s.sub.i-1 at the corresponding initialization test cycle T.sup.r.sub.1 during the entire k-th test application sub-phase. On the other hand, if tp.sup.k.sub.i=O, a two-input OR gate is inserted and enabled between D.sub.i-1 and D.sub.i and s.sub.i is always assigned a 1 at every activation and propagation test cycle T.sup.r.sub.2 independent of the value assigned to s.sub.i-1 at initialization test cycle T.sup.r.sub.1 during the entire k-th test application sub-phase. Likewise, if tp.sup.k.sub.i=A, a two-input AND gate is inserted and enabled between D.sub.i-1 and D.sub.i and s.sub.i is always assigned a 0 at every activation and propagation test cycle T.sup.r.sub.2 independent of the value assigned to s.sub.i-1 at initialization test cycle T.sup.r.sub.1 during the entire k-th test application sub-phase.

When a new test cube pair is added into the current test cube pair set, the test point vector is incrementally updated according to values assigned in the new test cube pair. In addition to symbols W, O, and A, symbols R, W0 and W1 are used as intermediate symbols during test point vector computation processes. The three intermediate symbols are used to compute a final test point vector for a test cube pair set and do not appear in any final test point vector that is used to determine test points to be enabled during each test application sub-phase; upon completion of computing a test point vector, all intermediate symbols in the test point vector are replaced by W's to produce a final test point vector. The finite state machine shown in FIG. 4 depicts a non-limiting illustrative procedure to calculate test points.

In this example, for every test point vector TP.sup.k (k=1, 2, . . . , k.sub.max, where k.sub.max is the number of test point vectors), initially, all state inputs except the state inputs that have no topological correlation with their immediate predecessor state inputs are assigned initial values R's (state R of the finite state machine shown in FIG. 4. In the rest of this disclosure, a pair of topologically correlated adjacent scan flip-flops and a pair of adjacent scan flip-flops that drive the same fanout cones are interchangeably used. The state inputs that do not drive any fanout cone that is driven by their immediate predecessor state inputs are assigned W's in every test point vector. Unlike initial R symbols, which may be updated to other symbols later in the test point vector computation process according to values assigned in test cube pairs added into the test cube pair set, the initial W symbols are fixed and do not change until the final test point vector is obtained. Since those state inputs that have no topological correlation with their immediate predecessor state inputs cause no dependency untestable transition delay faults, no test points need to be inserted in front of them. The scan flip-flop D.sub.1 located first in the scan chain is always assigned W in every test point vector.

Consider adding the first test cube pair V.sup.j into the current test cube pair set C.sup.k. If tp.sup.k.sub.i=R and d.sup.j.sub.i=10 in V.sup.j, then tp.sup.k.sub.i is updated to A (the state transition from state R to state O (A) of FIG. 4). Likewise, if tp.sup.k.sub.i=R and d.sup.j.sub.i=01 in V.sup.j, then tp.sup.k.sub.i is updated to O Otherwise, if state input s.sub.i is assigned R in the initial test point vector, and d.sup.j.sub.i=00 in V.sup.j, then tp.sup.k.sub.i is updated to W0 (the transition from state R to state W0 of FIG. 4). Note that d.sup.j.sub.i=00 can be applied with and without an AND test point between D.sub.i-1 and D.sub.i (see FIG. 3(b)). Hence, in this case, the final decision on the type of test point to be enabled between D.sub.i-1 and D.sub.i is postponed and an intermediate symbol W0 is assigned to tp.sup.k.sub.i. If a test cube pair V.sup.a where d.sup.a.sub.i=10, is added later in the process, tp.sup.k.sub.i is updated to A (the state transition from W0 to A in the finite state machine). Instead, if a test cube pair V.sup.b where d.sup.b.sub.i=11 is added, then tp.sup.k.sub.i is updated to W (note that d.sup.b.sub.i=11 cannot be applied if an AND test point is enabled between D.sub.i-1 and D.sub.i). Otherwise, no test cube pair V.sup.c where d.sup.c.sub.i is either 10 or 11 is added until no more test cube pairs can be added into the test cube pair set without conflict, the intermediate symbol W0 is replaced by W in the final test point vector.

Note that no matter what binary value is assigned to the X if d.sup.j.sub.i=0X or X0, the fault targeted by V.sup.j can be detected. If the X is assigned a 1, i.e., d.sup.j.sub.i=01 or 10, then tp.sup.k.sub.i is updated to O or A, respectively, and an OR test point should be inserted between D.sub.i-1 and D.sub.i if currently no OR test point is inserted between D.sub.i-1 and D.sub.i. In contrast, if the X is assigned a 0, then tp.sup.k.sub.i will be assigned W0, which requires no test point. Hence, it is more suitable to assign a 0 to the X.

Hence, when d.sup.j.sub.i=0X or X0, tp.sup.k.sub.i is updated to W0 (if d.sup.j.sub.i=0X or X0, state R transitions to state W0 in the finite state machine shown in FIG. 4) The transition from state R to state W1 is similar to the transition from state R to state W0.

Once tp.sup.k.sub.i is assigned A, then no test cube pairs where d.sup.j.sub.i=11, 01, or X1 can be added into the current test cube pair set without conflict with test cube pairs already existing in the test cube pair set. Likewise, once tp.sup.k.sub.i is assigned O, then no test cube pairs where d.sup.j.sub.i=00,10, and X0 can be added into the current test cube pair set without conflict with test cube pairs already existing in the test cube pair set. Recall that if tp.sup.k.sub.i=A, then s.sub.i is always assigned a 0 at every activation and propagation test cycle during the entire k-th test application sub-phase. Likewise, recall that if tp.sup.k.sub.i=O, then s.sub.i is always assigned a 1 at every activation and propagation test cycle during the entire k-th test application sub-phase. This is described as the transition from state O to state FAIL in FIG. 4.

EXAMPLE

FIG. 5 illustrates calculating test point vectors for two example sets of test cube pairs: C.sup.1 and C.sup.2. Assume that adjacent pairs of state inputs, s.sub.2 and s.sub.3, s.sub.4 and s.sub.5, and s.sub.5 and s.sub.6, drive different fanout cones. Therefore, tp.sup.k.sub.3, tp.sup.k.sub.5, and tp.sup.k.sub.6, where k=1,2, are always assigned W's in every test point vector. When test cube pair V.sup.1 is added to C.sup.1, tp.sup.1.sub.2 is updated to O since s.sub.1 is assigned a 0 in V.sup.1.sub.1 and s.sub.2 is assigned a 1 in V.sup.1.sub.2, i.e., d.sup.1.sub.2=01, and tp.sup.1.sub.4 and tp.sup.1.sub.7 are updated to W0 since d.sup.1.sub.4=d.sup.1.sub.7=X0 in V.sup.1. When test cube pair V.sup.2 is added to C.sup.1, tp.sup.1.sub.4 is updated to A since d.sup.2.sub.4=10. On the other hand, tp.sup.1.sub.7 holds the previous value W0 since d.sup.2.sub.7=00. Assume that no test cube pair can be added to C.sup.1 without conflict after V.sup.2 is added. Now, all intermediate symbols, R, W0, and W1, are replaced by W; in the example, the W0 assigned to tp.sup.1.sub.7 is replaced by W to produce the final test point vector TP.sup.1={W,O,W,A,W,W,W}.

The test point vector TP.sup.2 for test cube pair set C.sup.2 also starts with the same initial vector TP.sup.2={W,R,W,R,W,W,R} as initial TP.sup.1. Since d.sup.3.sub.2, d.sup.3.sub.4, and d.sup.3.sub.7 are respectively assigned X0, 10, and 11 in V.sup.3, TP.sup.2 is updated to {W,W0,W,A,W,W,W1} when V.sup.3 is added into C.sup.2. Since d.sup.4.sub.2=10 and d.sup.4.sub.7=01 in V.sup.4, tp.sup.2.sub.2 and tp.sup.2.sub.7 are again updated to A and O, respectively, when V.sup.4 is added into C.sup.2.

2. Global Test Point Vector

Hardware overhead for implementing the disclosed technique is determined by the number of inserted test points. The types of test points that will be inserted between each pair of adjacent scan flip-flops are expressed in the global test point vector, GTP=gtp.sub.1, gtp.sub.2, . . . , where n is the number of flip-flops in the scan chain and gtp.sub.i .epsilon. {W, A, O, AO} (i=1,2, . . . , n). The global test point vector GTP is obtained from test point vectors as follows: If tp.sup.k.sub.i, where k=1, 2, . . . , k.sub.max, where k.sub.max is the number of test point vectors (test cube pair sets), is assigned only W or O and assigned O in at least one test point vector, then tp.sup.k.sub.i is assigned O. Likewise, if tp.sup.k.sub.i, is assigned only W or A and assigned A in at least one test point vector, then tp.sup.k.sub.i is assigned A. Otherwise, tp.sup.k.sub.i is always assigned W in every test point vector, then no test point is necessary between D.sub.i-1 and D.sub.i and gtp.sub.i is assigned W. Finally, if tp.sup.k.sub.i is assigned O in at least one test point vector and also assigned A in at least one test point vector, then both AND and OR test points should be inserted between D.sub.i-1 and D.sub.i and gtp.sub.i is assigned AO, i.e., AND-OR complex gate. The global test point vector is updated upon completion of a test point vector computation process.

It is assumed that two-input AND and OR gates and AND-OR gates are used as test points in the illustrative non-limiting examples used in this disclosure. Hence, only symbols A, O, and AO are defined for the global test point vector GTP. However, the disclose technique can be extended to include other types of test points such as dummy flip-flops and/or XOR gates by adding appropriate symbols to represent new types of test points. Results obtained by using two-input AND and OR gates and dummy flip-flops as test points are also presented and compared with results obtained by using two-input AND and OR