Method for automatically generating test vectors for digital integrated circuits

• US 5,377,197 A
• Filed: 02/24/1992
• Issued: 12/27/1994
• Est. Priority Date: 02/24/1992
• Status: Expired due to Fees

• Current Assignee: University of Illinois
• Original Assignee: University of Illinois
• Inventors: Niermann, Thomas, Patel, Janak
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): TU, CHRISTINE TRINH LE
• Application Number:
  US07/840,792
• Time in Patent Office: 1,037 Days
• Field of Search: 371/23, 371/27, 371/22.1, 371/22.3, 371/22.4, 371/22.5
• US Class Current: 714/724
• CPC Class Codes: G01R 31/318307 computer-aided, e.g. automatic test program generator [ATPG], program translations, test program debugging
• CPC Class Codes: G01R 31/318342 by preliminary fault modelling, e.g. analysis, simulation
• CPC Class Codes: G01R 31/318392 for sequential circuits G01R31/318544 takes precedence

Abstract

A sequential circuit test generation system and method to generate test patterns for sequential without assuming the use of scan techniques or a reset state utilizes the iterative logic array (ILA) model of the sequential circuit and a targeted-D propagation scheme employing both forward time processing (FTP) and reverse time processing (RTP) techniques for assigning a sequence of primary input (PI) values and for producing a an initial pseudo primary input (PPI) vector representing the initial state of the digital circuit at a particular time frame. Improved state justification techniques generate the remaining sequence of PI vectors necessary to put the circuit into the initial state from either known or don'"'"'t care first states, by means of a heuristic method for reducing required initial state assignments. The method can also be applied to reduce the required number of PI vector assignments is also presented. In another phase of test vector generation, knowledge about the digital circuit behavior is obtained from a fault simulator to identify circuit nodes at which error signals are activated and partly propagated by already generated sequences of test vectors, and this knowledge is utilized with FTP techniques to generate test vector sequences for these nodes.

Claims

1. In a digital circuit testing system including a memory for storing therein digital circuit data that is representative of a digital circuit which includes gates having input nodes and output nodes;

the digital circuit testing system including a central processing unit (CPU) coupled to the memory for storing and retrieving the digital circuit data therein, the CPU also emulating an application of signals to nodes in the digital circuit, and emulating logic operations of the gates in the digital circuit and output signals thereof in response to emulated input signals applied thereto, and storing results of the emulation within the memory, a method of generating a test sequence of primary input (PI) signal vectors for detecting a stuck-at fault having a stuck-at value at a faulty node that propagates as an error signal in the digital circuit, the method comprising the steps of;

a) assigning signal values to a first set of nodes including initial primary input (PI) nodes and initial pseudo-primary input (PPI) nodes that cooperate in the digital circuit to generate a good signal having a value that is a complement of the stuck-at value at the faulty node;

b) determining a set of gates in the digital circuit having an error signal on a gate input node attributable to the stuck-at value and also having an undetermined (X) value on an output node;

c) selecting a next gate from the set of gates, and storing in the memory indications of unselected gates remaining in the set;

d) for each dominator gate of the next gate, assigning propagating signal values to a set of dominator input nodes that cooperate in the digital circuit to cause the error signal to propagate to an output node of each dominator gate;

e) for every assigned propagating signal value, assigning to as yet unassigned initial PI and initial PPI nodes initial PI and initial PPI signal values that cooperate in the digital circuit to generate the assigned propagating signal values at the dominator input nodes;

f) emulating the propagation of the error signal through each dominator gate and all other gates in the circuit that are conditioned by the assigned initial PI and initial PPI signal values to propagate the error signal to a set of successor input nodes of a set of successor gates; and

g) repeating steps c) through f), using the successor gates in place of the next gates and using the successor input nodes in place of the gate input nodes, until the error signal has arrived at a primary output (PO); and

h) processing at the CPU to produce from the initial PI and initial PPI signal values a known PPI signal vector and the test sequence of PI signal vectors.

2. A method according to claim 1 further comprising the steps of:

e) after step g), determining whether signal assignments can be made to as yet unassigned initial PI and initial PPI nodes that generates the assigned propagating signal values at the dominator input nodes, and if not, then unassigning all initial PI and initial PPI signal values assigned during step e), and retrieving from the memory the indications of the unselected gates and selecting a next gate therefrom, and continuing at step d); and

wherein step h) comprises the steps of

j) determining whether steps b) through i) succeeded in propagating the error signal to the PO, and if so, then processing at the CPU to produce from the initial PI and initial PPI signal values a known PPI signal vector and the test sequence of PI signal vectors.

3. A method according to claim 2 wherein in step j), the substep of processing at the CPU to produce from the initial PI and initial PPI signal values a known PPI signal vector and the test sequence of PI signal vectors comprises the steps of:

k) selecting a known PPI signal vector having all of its signals unassigned; and

l) processing according to a reverse time processing technique to produce the test sequence of PI signal vectors.

4. A method according to claim 2 wherein in step j), a substep of processing at the CPU to produce from the initial PI and initial PPI signal values a known PPI signal vector and the test sequence of PI signal vectors, comprises the steps of:

k) selecting a known PPI signal vector;

l) setting a trial sequence of PI signal vectors to an unassigned (X) state;

m) emulating the application of the known PPI signal vector and the trial sequence of PI signal vectors to a model digital circuit representing an n time frame iterative logic array (ILA) expansion of the digital circuit to be tested, where n is an integer greater than or equal to one, to produce n model PPI signal vectors, each model PPI signal vector comprising a set of signals which may or may not have an assigned signal value;

n) selecting a best PPI signal vector from the n model PPI signal vectors, that satisfies the conditions that it does not have fewer signal values assigned to corresponding assigned initial PPI signal values than any other PPI signal vector, and all of its assigned signal values are either equal to corresponding signal values in the initial PPI signal values or else correspond to unassigned signal values in the initial PPI signal values; and

o) assigning values to a test sequence of unassigned PI signal values to produce a test sequence of PI signal vectors spanning a first time frame at which the known PPI signal vector is present to a last time frame at which the best PPI signal vector is active, wherein the assigned PI signal values cooperate with the known PPI signal vector to generate remaining signal values in the initial PPI signal values.

5. In a digital circuit testing system including a memory for storing therein digital circuit data that is representative of a digital circuit which includes gates having input nodes and output nodes;

the digital circuit testing system including a central processing unit (CPU) coupled to the memory for storing and retrieving the digital circuit data therein, the CPU also emulating an application of signals to nodes in the digital circuit, and emulating logic operations of the gates in the digital circuit and output signals thereof in response to emulated input signals applied thereto, and storing results of the emulation within the memory, wherein the digital circuit testing system generates a test sequence of primary input (PI) signal vectors and a known pseudo-primary input (PPI) signal vector for detecting a stuck-at fault at a faulty node in the digital circuit having a stuck-at value, the test sequence of PI signal vectors and the known PPI signal vector cooperating when applied to the digital circuit to cause an error signal at the faulty node to propagate to a primary output (PO) of the digital circuit, the digital circuit testing system generating the test sequence by producing an initial sequence of PI signal vectors and an initial PPI signal vector from which the known PPI signal vector and the test sequence of PI signal vectors are generated, the initial sequence of PI signal vectors and the initial PPI signal vector cooperating when applied to the digital circuit to cause the error signal at the faulty node in the digital circuit to propagate to the PO of the digital circuit, a method of producing a reduced initial PPI signal vector that has fewer assigned PPI signals than the initial PPI signal vector and that cooperates with the initial sequence of PI signal vectors when applied to the digital circuit to propagate the error signal from the faulty node to the PO, the method comprising the steps of;

a) selecting an initial PPI signal that has an assigned signal value from the initial PPI signal vector;

b) storing the assigned signal value in the memory and setting the selected initial PPI signal to an unassigned value to produce a reduced initial PPI input signal vector;

c) applying the reduced initial PPI signal vector and the initial sequence of PI signal vectors to the digital circuit; and

d) if the error signal does not propagate from the faulty node to the PO, retrieving the stored assigned signal value from the memory, and assigning the stored assigned signal value to the selected initial PPI signal in the reduced initial PPI signal vector.

6. In a digital circuit testing system including a memory for storing therein digital circuit data that is representative of a digital circuit which includes gates having input nodes and output nodes;

the digital circuit testing system including a central processing unit (CPU) coupled to the memory for storing and retrieving the digital circuit data therein, the CPU also emulating an application of signals to nodes in the digital circuit, and emulating logic operations of the gates in the digital circuit and output signals thereof in response to emulated input signals applied thereto, and storing results of the emulation within the memory, wherein the digital circuit testing system generates a test sequence of primary input (PI) signal vectors and a known pseudo-primary input (PPI) signal vector for detecting a stuck-at fault at a faulty node in the digital circuit, the stuck-at fault having a stuck-at value, the test sequence of PI signal vectors and the known PPI signal vector cooperating when applied to the digital circuit to cause an error signal at the faulty node to propagate to a primary output (PO) of the digital circuit, the digital circuit testing system generating the test sequence by producing an initial sequence of PI signal vectors and an initial PPI signal vector from which the known PPI signal vector and the test sequence of PI signal vectors are generated, the initial sequence of PI signal vectors and the initial PPI signal vector cooperating when applied to the digital circuit to cause the error signal at the faulty node in the digital circuit to propagate to the PO of the digital circuit, a method of producing a sequence of reduced PI signal vectors that has fewer assigned PI signals than the first sequence of PI signal vectors and that cooperates with the known PPI signal vector when applied to the digital circuit to propagate the error signal from the faulty node to the PO, the method comprising the steps of;

a) selecting a test PI signal that has an assigned value from the test sequence of PI signal vectors;

b) storing the assigned signal value in the memory and setting the selected test PI signal to an unassigned value to produce a sequence of reduced PI signal vectors;

c) applying the sequence of reduced PI input signal vectors and the known PPI signal vector to the digital circuit; and

d) if the error signal does not propagate from the faulty node to the primary output, retrieving the stored assigned signal value from the memory, and assigning the stored assigned signal value to the selected test PI signal in the sequence of reduced PI signal vectors.

7. In a digital circuit testing system including a memory for storing therein digital circuit data that is representative of a digital circuit which includes gates having input nodes and output nodes;

the digital circuit testing system including a central processing unit (CPU) coupled to the memory for storing and retrieving the digital circuit data therein, the CPU also emulating an application of signals to nodes in the digital circuit, and emulating logic operations of the gates in the digital circuit and output signals thereof in response to emulated input signals applied thereto, and storing results of the emulation within the memory, wherein the digital circuit testing system generates a test sequence of primary input (PI) signal vectors and a known pseudo-primary input (PPI) signal vector for detecting a stuck-at fault at a faulty node in the digital circuit having a stuck-at value, the test sequence of PI signal vectors and the known PPI signal vector cooperating when applied to the digital circuit to cause an error signal at the faulty node to propagate to a primary output (PO) of the digital circuit, the digital circuit testing system generating the test sequence by producing an initial sequence of PI signal vectors and an initial PPI signal vector from which the known PPI signal vector and the test sequence of PI signal vectors are generated, the initial sequence of PI signal vectors and the initial PPI signal vector cooperating when applied to the digital circuit to cause the error signal at the faulty node in the digital circuit to propagate to the PO of the digital circuit, a method of producing a reduced initial PPI signal vector that has fewer assigned PPI signals than the initial PPI signal vector and that cooperates with the initial sequence of PI signal vectors when applied to the digital circuit to propagate the error signal from the faulty node to the PO, the method comprising the steps of;

a) selecting an initial PPI signal that has an assigned signal value from the initial PPI signal vector;

b) storing the assigned signal value in the memory and setting the selected initial PPI signal to the complement of the stored assigned signal value to produce a modified initial PPI input signal vector;

c) applying the modified initial PPI signal vector and the initial sequence of PI signal vectors to the digital circuit; and

d) if the error signal does not propagate from the faulty node to the primary output, retrieving the stored assigned signal value from the memory, and assigning the stored assigned signal value to the selected initial PPI signal in a reduced initial PPI signal vector, otherwise setting the selected initial PPI signal to an unassigned value in the reduced initial PPI signal vector.

8. In a digital circuit testing system including a memory for storing therein digital circuit data that is representative of a digital circuit which includes gates having input nodes and output nodes;

the digital circuit testing system including a central processing unit (CPU) coupled to the memory for storing and retrieving the digital circuit data therein, the CPU also emulating an application of signals to nodes in the digital circuit, and emulating logic operations of the gates in the digital circuit and output signals thereof in response to emulated input signals applied thereto, and storing results of the emulation within the memory, wherein the digital circuit testing system generates a test sequence of primary input (PI) signal vectors and a known pseudo-primary input (PPI) signal vector for detecting a stuck-at fault at a faulty node in the digital circuit, the stuck-at fault having a stuck-at value, the test sequence of PI signal vectors and the known PPI signal vector cooperating when applied to the digital circuit to cause an error signal at the faulty node to propagate to a primary output (PO) of the digital circuit, the digital circuit testing system generating the test sequence by producing an initial sequence of PI signal vectors and an initial PPI signal vector from which the known PPI signal vector and the test sequence of PI signal vectors are generated, the initial sequence of PI signal vectors and the initial PPI signal vector cooperating when applied to the digital circuit to cause the error signal at the faulty node in the digital circuit to propagate to the PO of the digital circuit, a method of producing a sequence of reduced PI signal vectors that has fewer assigned PI signals than the first sequence of PI signal vectors and that cooperates with the known PPI signal vector when applied to the digital circuit to propagate the error signal from the faulty node to the PO, the method comprising the steps of;

a) selecting a test PI signal that has an assigned signal value from the test sequence of PI signal vectors;

b) storing the assigned signal value in the memory and setting the selected test PI signal to the complement of the stored assigned signal value to produce a sequence of modified PI signal vectors;

c) applying the sequence of modified PI input signal vectors and the known PPI signal vector to the digital circuit; and

d) if the error signal does not propagate from the faulty node to the primary output, retrieving the stored assigned signal value from the memory, and assigning the stored assigned signal value to the selected test PI signal in a sequence of reduced PI signal vectors, otherwise setting the selected test PI signal to an unassigned value in the sequence of reduced PI signal vectors.

9. In a digital circuit testing system including a memory for storing therein digital circuit data that is representative of a digital circuit which includes gates having input nodes and output nodes;

the digital circuit testing system including a central processing unit (CPU) coupled to the memory for storing and retrieving the digital circuit data therein, the CPU also emulating an application of signals to nodes in the digital circuit, and emulating logic operations of the gates in the digital circuit and output signals thereof in response to emulated input signals applied thereto, and storing results of the emulation within the memory, wherein the digital circuit testing system generates an activating sequence of primary input (PI) signal vectors and an activating pseudo-primary input (PPI) signal vector, the activating sequence of PI signal vectors and the activating PPI signal vector cooperating when applied to the digital circuit to cause an error signal to appear at a faulty node in the digital circuit and to propagate to at least one pseudo-primary output (PPO) of the digital circuit, a method of generating a test sequence of PI signal vectors for causing the error signal at the faulty node to propagate to a primary output (PO) of the digital circuit, the method comprising the steps of;

a) applying the activating PPI signal vector and the activating sequence of PI signal vectors to the digital circuit;

b) determining the set of those gates in the digital circuit that have an error signal on a gate input node and also have an undetermined (X) value on an output node;

c) selecting a next gate from the set of gates, and storing in the memory indications of the remaining unselected gates in the set;

d) for each dominator gate of the next gate, assigning propagating signal values to a set of dominator input nodes that cooperate in the digital circuit to cause the error signal to propagate to an output node of each dominator gate;

e) for every assigned propagating signal value, assigning to as yet unassigned test PI nodes, test PI signal values that cooperate in the digital circuit to generate the assigned propagating signal values at the dominator input nodes;

f) emulating the propagation of the error signal through each dominator gate and all other gates in the circuit that are conditioned by the assigned test PI signal values to propagate the error signal to a set of successor input nodes of a set of successor gates; and

g) repeating steps c) through f), using the successor gates in place of the next gates and using the successor input nodes in place of the gate input nodes, until the error signal has arrived at the PO.

10. A method accordingly to claim 9 further comprising the steps of:

h) determining whether signal assignments can be made to as yet unassigned test PI nodes that generate the assigned propagating signal values at the dominator input nodes, and if not, then unassigning all test PI signal values assigned during step e), and retrieving from the memory the set of remaining unselected gates and selecting a next gate therefrom, and continuing at step d).

12. A method according to claim 10, wherein the step of assigning PI signal values to as vet unassigned PI nodes in the reduced test sequence of PI signal vectors, the PI signal values cooperating when applied in conjunction with the activating PPI signal vector and the activating sequence of PI signal vectors to cause the error signal to propagate to the PO comprises the steps of:

e) determining the set of those gates in the digital circuit that have an error signal on a gate input node and also have an undetermined (X) value on an output node;

f) selecting a next gate from the set of gates, and storing in the memory indications of the remaining unselected gates in the set;

g) for each dominator gate of the next gate, assigning propagating signal values to a set of dominator input nodes that cooperate in the digital circuit to cause the error signal to propagate to an output node of each dominator gate;

h) for every assigned propagating, signal value, assigning to as yet unassigned PI nodes in the reduced test sequence of PI signal vectors, PI signal values that cooperate in the digital circuit to generate the assigned propagating signal values at the dominator input nodes;

i) emulating the propagation of the error signal through each dominator gate and all other gates in the circuit that are conditioned by the assigned PI signal values in the reduced test sequence of PI signal vectors to propagate the error signal to a set of successor input nodes of asset of successor gates; and

j) repeating steps f) through i), using the successor gates in place of the next gates and using the successor input nodes in place of the gate input nodes, until the error signal has arrived at the PO.

13. A method according to claim 12 further comprising the steps of:

k) determining whether signal assignments can be made to as yet unassigned PI nodes in the reduced test sequence of PI signal vectors that generate the assigned propagating signal values at the dominator input nodes, and if not, then unassigning all PI signal values that were assigned during step h), and retrieving from the memory the set of remaining unselected gates and selecting a next gate therefrom, and continuing at step g).

11. In a digital circuit testing system including a memory for storing therein digital circuit data that is representative of a digital circuit which includes gates having input nodes and output nodes;

the digital circuit testing system including a central processing unit (CPU) coupled to the memory for storing and retrieving the digital circuit data therein, the CPU also emulating an application of signals to nodes in the digital circuit, and emulating logic operations of the gates in the digital circuit and output signals thereof in response to emulated input signals applied thereto, and storing results of the emulation within the memory, wherein the digital circuit testing system generates an activating sequence of primary input (PI) signal vectors and an activating pseudo-primary input (PPI) signal vector, the activating sequence of PI signal vectors and the activating PPI signal vector cooperating when applied to the digital circuit to cause an error signal to appear at a faulty node in the digital circuit, and to propagate to a pseudo primary output (PPO) in the digital circuit, a method of generating a reduced test sequence of PI signal vectors for causing the error signal at the PPO to propagate to at least one primary output (PO) of the digital circuit, the method comprising the steps of;

a) selecting a last PI signal vector from the activating sequence of PI signal vectors and assigning the selected PI signal vector to a reduced test sequence of PI signal vectors;

b) applying the reduced test sequence of PI signal vectors to the digital circuit;

c) if the error signal propagates from the faulty node to the PPO, then continuing at step d), otherwise selecting from the activating sequence of PI signal vectors a predecessor PI signal vector to the previously selected PI signal vector, assigning the selected predecessor PI signal vector to the reduced test sequence of PI signal vectors and repeating steps b) and c); and

d) assigning PI signal values to as yet unassigned PI nodes in the reduced test sequence of PI signal vectors, the PI signal values cooperating when applied in conjunction with the activating PPI signal vector and the activating sequence of PI signal vectors to cause the error signal to propagate to the PO.