JP2932749B2 - Test sequence generation method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for generating a test sequence for a digital circuit.

[0002]

2. Description of the Related Art Conventional test sequence generation methods include Prentice Hall, Inglewood Cliff, and New Jersey (Prentice-Hall, Englewood C).
life, New Jersey)
Tolerant Computing Theory and Techniques Volume I (FAULTTOLERAN)
TCOMPUTING TheoryandTechni
quesVolumeI) ”, Chapter 1.
4.2 “StuckatFaultTesting” and 1
Material of the International Test Conference of 989 [M. H. SchulzandE. Auth, "E
SENTIAL: AnEffectiveSelf-
LearningTestPatternGenera
TionAlgorithmforSequentia
1Circuits, "Proc. Int. TestC
onf. Pp. 28-37, Aug. 1989] and these references.

The prior art of a test sequence generation method related to the present invention will be described below with reference to the drawings. FIG. 3 is a diagram showing a conventional test sequence generation method for a sequential circuit.

In FIG. 1, step 301 indicates the start of a test sequence generation process for a sequential circuit. First, step 302
Then, it is determined whether or not there is a fault that has not been detected and has not yet been selected as a test sequence generation target. The process proceeds to step 303, and if not, the process proceeds to step 307.

Next, in step 303, one fault is selected as a target fault from a group of faults that have not been detected and have not yet been selected as test sequence generation targets. In step 304, for the target fault selected in step 303, a fault propagation process for generating a sequence for propagating the target fault from the fault location to an arbitrary external output pin is performed, and it is determined whether the generation of the sequence is successful. If the failure propagation process succeeds, the process proceeds to step 305;
Then, the next fault is processed.

Next, in step 305, state initialization processing for generating a sequence for transitioning from the initial state of the circuit to the state of the circuit at the time when the failure propagation processing has been completed is performed. Proceeding, if unsuccessful, proceed to step 302 to perform processing for the next failure.

Next, in step 306, step 303
The fault simulation is executed with the test sequence of the target fault selected in the above, and the fault detected at an arbitrary external output pin is deleted from the undetected fault group.

Step 307 indicates the end of the test sequence generation processing of the sequential circuit. FIG. 4 is a diagram showing the operation of a conventional test sequence generation method for a sequential circuit. FIG. 4A shows a sequential circuit having three flip-flops used for explaining the operation of a conventional test circuit generation method for a sequential circuit. FIG.
4B is a conceptual diagram when a test sequence is generated for a fault in the sequential circuit of FIG. Reference numeral 401 denotes an external input pin. 402 is a combinational circuit part. 403 is an external output pin. 404 to 406 are flip-flops. Reference numeral 407 denotes a target fault in the sequential circuit of FIG. 408 is a fault propagation path of the target fault 407.

The operation of a conventional test circuit generation method for a sequential circuit will be described below with reference to FIG. For the target fault 407, as shown by the fault propagation path 408, a sequence is generated that propagates from the fault location at time t-1 through the flip-flop 405 at time t to any external output pin 403 at time t. And a fault propagation process. Next, a state initialization process is performed to generate a sequence that matches the initial state from the states of the flip-flops 404 to 406 at time t-1 at which the failure propagation process ends. The series generated here is
In addition, a test sequence having a length of n + 1 for the target fault 407 is generated, and a fault simulation is performed using this test sequence.

[0010]

However, in the above-described test sequence generation method, when the failure propagation process or the state initialization process fails, the test sequence is generated even if the test sequence for the target fault is generated halfway. If the test sequence generation of the target fault often fails in order to give up and process the next target fault, the frequency of executing the fault simulation is reduced and the state of the circuit does not change. If the test sequence generation becomes difficult, there is a high possibility that the test sequence generation becomes difficult for other faults, and the fault detection rate does not increase.

SUMMARY OF THE INVENTION The present invention has been made in view of the above, and has as its object to provide a test sequence generation method capable of obtaining a high fault coverage.

[0012]

According to the present invention, in order to solve these problems, in a process for obtaining a test sequence for a certain fault in a sequential circuit, an input sequence for transmitting the fault to an external output pin is generated. a first processing and a second processing propagation of the fault from the initial state of the sequential circuit to generate an input sequence to transition to a state of time ended, before
The input sequence generated in the first processing and the second processing is
In addition, it is generated as a failure test sequence and
A third process for executing a failure simulation;
In either the first process or the second process,
When the generation of the force sequence has failed, if the length of the test sequence at least halfway through the generation just before the failure is at least 1 or more, a failure simulation is performed with the test sequence up to the halfway in the third process. This is a test sequence generation method characterized by being executed.

[0013]

According to the present invention, even if the test sequence generation for a certain target failure fails, if the length of the test sequence up to the halfway to be generated before the failure is at least 1 or more, the present invention will be described. By performing a fault simulation with the test sequence generated up to this point, the possibility of detecting a fault other than the target fault increases, and even if the circuit status is in a state where the test sequence is difficult, transition to a state where the test sequence is easy The possibility is increased, and a high failure detection rate can be obtained.

[0014]

FIG. 1 is a flow chart of a test sequence method for a sequential circuit used to show an embodiment of the present invention. In FIG. 1, step 101 indicates the start of the test sequence generation processing of the sequential circuit. First, in step 102, it is determined whether or not there is a fault that has not been detected and has not yet been selected as a test sequence generation target. If there is, the process proceeds to step 103, and if not, the process proceeds to step 108.

Next, in step 103, one fault is selected as a target fault from a fault group that has not been detected yet and has not yet been selected as a test sequence generation target. In step 104, for the target fault selected in step 103, a fault propagation process for generating a sequence for propagating the target fault from the fault location to any external output pin is performed, and it is determined whether or not the generation of the sequence is successful. If the failure propagation process succeeds, the process proceeds to step 105;
Proceed to.

Next, in step 105, state initialization processing for generating a sequence for transitioning from the initial state of the circuit to the state of the circuit when the failure propagation processing is completed is performed. If the generation of the series is successful, the process proceeds to step 107. Proceed to step 106 if unsuccessful.

Next, in step 106, step 104
And the series generated in step 105
When the test sequence generation fails, it is determined whether the length of the partially generated test sequence is 1 or more. If the length of the partial test sequence is 1 or more, step 107 is performed. If the result is less than 1, that is, if a test sequence cannot be generated at all, the process proceeds to step 102, where the next fault is processed.

Next, in step 107, step 103
Step 104 and Step 105 of the target failure selected in
The fault simulation is executed with the test sequence obtained by combining the sequences generated in the above or the test sequence with a length of 1 or more that has been generated halfway, and the fault detected at any external output pin is selected from the undetected fault group. delete.

Step 108 indicates the end of the test sequence generation processing for a certain fault in the sequential circuit. FIG. 2 is an explanatory diagram of an operation of generating a test sequence of a sequential circuit according to the present invention. FIG. 2 (a)
FIG. 3 is a circuit diagram used to explain an operation of generating a test sequence in a sequential circuit according to the present invention. FIG. 2 (b) is the same as FIG.
3 is a conceptual diagram when a test sequence is generated for a fault in the sequential circuit of FIG. FIG. 2C is a diagram showing the propagation status of the fault list at the time of performing the test sequence generation shown in FIG. 2B. FIG. 2D is a state transition diagram of the circuit of FIG.

Reference numeral 201 denotes an external input pin. 202 is a combinational circuit part. 203 is an external output pin. 2
04 to 206 are flip-flops. 207 is a target failure. 208 is a fault propagation path. Reference numeral 209 denotes a failure list that has been propagated to the flip-flop 204 when the test sequence is generated for the target failure 207. Reference numeral 210 denotes a fault list that has been propagated to the flip-flop 205 at the time of generating a test sequence for the target fault 207. Reference numeral 211 denotes a failure list that has been propagated to the flip-flop 206 at the time of generating a test sequence for the target failure 207. Reference numerals 212 to 216 denote states in the state transition diagram. 217 to 226 indicate transition destinations in the state transition diagram.

The operation of the test sequence generation method for a sequential circuit according to the present invention will be described below with reference to FIG. Test sequence generation is performed on the sequential circuit of FIG. First, as shown in FIG. 2B, 207 is selected as the target failure. Next, a sequence is generated that propagates through the fault propagation path 208 and propagates the fault to the external output pin 203. Next, an attempt is made to generate a sequence that transitions from the initial state of the circuit to the state at time t−1, that is, the state at the time when the fault propagation processing ends, but during the state initialization processing, Assuming that generation has failed, it is necessary to perform a partial detection of the state initialization sequence and the fault propagation sequence that were generated just before the failure.
Execute failure simulation in the inspection sequence .

Here, as shown in FIG. 2C, the propagation status of the fault list at the time of generating the test sequence for the target fault 207 indicates that the flip-flop 204 has faults a and b.
List 209 including the flip-flop 205
A fault list 210 including faults c and d is propagated to the flip-flop 206, and a fault list 211 including faults e and f is propagated to the flip-flop 206. That is, the faults a and b are in the flip-flop 204, the faults c and d are in the flip-flop 205,
Faults e and f have propagated to flip-flop 206.
Although the test sequence generation for the target fault 207 has failed, the generation of the fault propagation sequence has been at least successful, and the test sequence has propagated through the flip-flop 204 to the external output pin 203 as shown in the fault propagation path 208. That is, since the test sequence for the fault propagating to the flip-flop 204 is generated, the state initialization sequence and the fault propagation sequence generated just before the test sequence generation failed are combined.
When a failure simulation is performed in the test sequence up to the middle, the failures a and b that have propagated to the flip-flop 204 may be detected at the external output pin 203. Of course, there is a possibility that a failure other than the target failure can be detected by the external output pin 203.

As shown in FIG. 2 (d), when the initial state is 212 and there are many faults that cannot be generated unless a transition to the state of 216 is made, a sequence of 214 through 212 to 219 is executed. The state transitions from state 214 to state 213 through state 220 to state 213 from state 213 to state 212 through state 218. When the state falls into a loop and the test sequence generation fails, the test sequence generation for a certain fault is performed halfway. Since the state may transition to 215 by performing a failure simulation with the test sequence of, it can be seen that the state can transition to 216 without selection. Therefore 216
There is a possibility that the test sequence generation may succeed even for other faults for which the test sequence cannot be generated unless the state transitions to the above state. FIG. 5 shows the results of an experiment performed using a benchmark circuit of ISCAS89 (International Symposium Circuit and System 89).

As described above, according to this embodiment, even if the generation of a test sequence for a certain target failure fails, if a test sequence having a length of at least 1 is generated immediately before the failure, the test sequence may be interrupted. By performing a fault simulation on the test sequence up to the middle of the test sequence, there is a possibility that other faults than the target fault can be detected.In addition, the initial state is a state where test sequence generation is difficult. If a test sequence at least halfway through the length of at least 1 has been generated just before the failure at the time of the failure, the failure simulation is performed on the test sequence up to the halfway to make it easy to generate the test sequence. And the fault detection rate is improved.

[0025]

As described above, the test sequence method according to the present invention has a problem that the fault detection rate does not increase when a large number of censored faults occur in the conventional test sequence method for sequential circuits. Thus, a test sequence with a high failure detection rate can be generated.

[Brief description of the drawings]

FIG. 1 is a flowchart of a test sequence generation method used to show an embodiment of the present invention.

FIG. 2A is a circuit diagram used for explaining the operation of a method for generating a test sequence of a sequential circuit according to the present invention; FIG. 2B is a conceptual diagram for explaining the operation of the method for generating a test sequence of a sequential circuit according to the present invention; (C) is a circuit diagram for explaining the propagation status of the fault list immediately before applying the test sequence generation method of the sequential circuit according to the present invention. (D) shows the effect of the test sequence generation method of the sequential circuit according to the present invention. State transition diagram for showing

FIG. 3 is a flowchart of a conventional test circuit generation method for a sequential circuit;

FIG. 4A is a circuit diagram used to explain the operation of a conventional sequential circuit test sequence generation method. FIG. 4B is a conceptual diagram for explaining the operation of a conventional sequential circuit test sequence generation method.

FIG. 5 is a diagram showing an experimental result by a benchmark circuit of ISCAS89 in the present invention and the prior art.

[Explanation of symbols]

106 When the failure propagation process or the state initialization process fails, a process of determining whether or not the length of the partial test sequence generated just before the failure is 1 or more 107 Inspection sequence or processing 10 for failure
If the failure propagation processing or the state initialization processing fails in step 6, the length of the test sequence generated until immediately before the failure is 1
A process for executing a failure simulation with a test sequence up to the middle of the above

Claims (1)

(57) [Claims] In a process for obtaining a test sequence for a certain fault in a sequential circuit, a first process for generating an input sequence for transmitting the fault to an external output pin, and a process of transmitting the fault from an initial state of the sequential circuit A second process for generating an input sequence that causes a transition to a state at the time when the process has ended, and the input sequence generated in the first process and the second process are combined to generate a test sequence for a failure, and A third process for executing a failure simulation in the first
When the generation of the input sequence fails in any of the processing of the second processing or the second processing, if the length of the test sequence at least halfway through the generation before the failure is at least 1 or more, A test sequence generation method, characterized in that a fault simulation is executed in the test sequence halfway through the process.