JP2812008B2 - Test sequence generator - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

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

[0002]

2. Description of the Related Art As a recent test sequence generation device, an ASIC having a circuit configuration capable of observing states of all circuit elements.
Semiconductors are receiving attention. Inspection of a semiconductor having such a configuration uses a test sequence to turn on and off the states of circuit elements.
F, and by measuring this, a semiconductor failure such as a short circuit or disconnection of a circuit is detected.

A conventional test sequence generation method will be described with reference to FIG. The assumption here is the output line of NOR31.
It is assumed that 0 contraction fault where 32 is in contact with the ground. In order to detect this failure, a test sequence for setting the state of the output line 32 to 1 is input, and whether the state of the output line 32 is 0 (the output line 32 has a possibility of 0 contraction failure) or 1 (The output line 32 is not a zero-body failure.)

The conventional test sequence generation method reverses the logic. The procedure for generating a test sequence will be described with reference to FIG. First, in order to set the output line 32 of the NOR 31 to 1 assuming a 0-body fault, it is necessary to set the input 33 to 0 and the output line 35 of the D flip-flop 34 to 0. In order to set the output line 35 of the flip-flop 34 to 0, it is necessary to set the output line 37 of the NOR 36 to 0 in advance and then start the clock 38. In order to make the output line 37 of the NOR 36 zero, it is necessary to make the input 39 or the output line 32 of the NOR 31. In this case, since it is easier to set the input 39 to 1, the test sequence becomes (000, 0) by the above procedure.
01: input 33, input 39, clock 38) are obtained.

[0005]

However, the conventional system has the following problems. (1) When tracing back the logic, a correct solution does not always exist, and a loop or a termination often occurs. Therefore, a backtrack is required, and the calculation time becomes enormous. (2) Since reversing the flip-flop returns the time axis backward, the inspection apparatus must store the logical state for each time in order to cope with the backtrack, and an enormous amount of memory is required. Required.

[0006]

In order to solve the above problems, a sequential circuit having N inputs and M outputs, an arbitrary fault setting signal line assuming a stuck-at 0 or 1 fault, and
A circuit simulator that simulates the sequential circuit and outputs a logic value signal of each circuit element, a continuous logic value derivation unit that derives a continuous logic value of each circuit element, and derives a controllable cost of each circuit element. A controllable cost derivation unit, an input signal generation unit that generates two or more L input signals for the N inputs, and a pseudo execution of the sequential circuit for each of the input signals; A cost deriving unit that derives the sum of the controllable cost and the continuous logical value on the signal line as a cost, and a minimum cost deriving unit that determines the minimum cost in the obtained cost group. Compare the costs.If the minimum cost is smaller, set the input signal indicating the minimum cost as the next input signal. Otherwise, change the input signal indicating the clock to the previous input signal. Enter the following And No., the test sequence generation device configuration.

The continuous logic value of the circuit element is expressed by a continuous value between a logic 0 representing an OFF state, a logic 1 representing an ON state, and a logic X representing an undetermined state, and each input of the circuit element is represented by a continuous value. Based on the continuous logical value of the line, the continuous logical value output to the output line of the circuit element based on the circuit element.

Furthermore, the controllable cost of the output line of the circuit element is
Based on the structure of the circuit, the controllable cost set of the input line set of each circuit element and the logical value of the output line of the circuit element as parameters,
0 controllable cost, which is the number of procedures required to set the logical value of the output line to 0, and 1 controllable cost, which is the number of procedures required to set the logical value of the output line to 1; The P controllable cost, which is the number of procedures required to change the logical value of the output line from 0 to 1, and the logical value of the output line from 1 to 0
N controllable cost, which is the number of procedures required to make

[0009]

According to the structure of the first aspect of the present invention, when a local solution often occurs during search for a test sequence of a circuit having tens of thousands of gates or a circuit having a complicated structure, backtracking is not performed. By inverting the clock input, it is possible to provide an input signal that changes the state the most and escape from the local solution.

According to the second and third aspects of the present invention, four types of controllable costs are set as the number of procedures required to set the output line of each circuit element to an arbitrary logical value based on the circuit structure. Further, since a continuous logical value indicating the degree of change due to the input pattern of the output line of each circuit element is used and the minimum value of the sum of the controllable cost and the continuous logical value on the failure setting signal line is used as the cost, It is possible to search for an input pattern based on the number of procedures, which is the number of changes in the input pattern, and the degree of change in the logical value of the failure setting signal line due to the change in the input pattern, without falling into a local solution.

[0011]

An embodiment of the present invention will be described below.
FIG. 1 shows the configuration of the test sequence generation device of this embodiment.

The sequential circuit 1 includes a storage element such as a flip-flop, a logic element such as an AND circuit, N inputs IN2, and M outputs OUT3. The circuit simulator 4
The sequential circuit 1 is pseudo-executed to obtain an input for controlling the logical value signal Vi of each circuit element i. In the example of this figure, the purpose of the test sequence generation of the semiconductor circuit is to generate a test sequence signal for controlling the output of the AND circuit to 1 so that a difference occurs between the states of the normal circuit and the faulty circuit.

The input signal generation unit 6 receives the previous input signal Vin
Generate L input signals Vin, i (t) (i = 1, L) separated from (t-1) by a Hamming distance 1. The generation method here may select all N input numbers, or use an input signal V using a weighted random number for frequently used input pins.
You may select L in.

[0014] continuous logical value deriving unit 8 calculates a continuous logic value CVi _o at the output line i _o of each circuit element i. The continuous logical value is represented by a real number from 0 to 30 shown in FIG. A logic 0 representing an OFF state is represented by 0, a logic 1 representing an ON state is represented by 10, a logic X representing an undetermined state is represented by 20,
Logic 0, Logic 1, and Logic X are arranged on a circle. A continuous logical value between 0 and 10 represents an intermediate value between logical 0 and logical 1. A continuous logic value between 10 and 20 represents an intermediate value between logic 1 and logic X. A continuous logical value between 20 and 30 represents an intermediate value between logical X and logical 0.

The continuous logical value CVi of the output line of each circuit element
_o is determined from the successive logical values applied to the input lines. The relation between input and output is OR, AND, NOT, exclusive OR, and de-flip-flop. The relationship between the input and output of each logic element is expressed as a logic function reflecting the degree of logic uncertainty or the degree of logic determination. FIG. 3 shows an input / output relationship of a continuous logical value in the OR element.

The controllable cost deriving unit 7 calculates the number of procedures required to set the logical value Vi ₀ of the output line i _{0 to 0} based on the circuit structure for the output line i ₀ of each circuit element i. 0-controllability costs CC0i ₀ is, the logical value Vi ₀ output lines i ₀ 1
Controllable cost CC, which is the number of procedures required to make
1i ₀ and the P controllable cost CCPi ₀ which is the number of procedures required to change the logical value Vi ₀ of the output line i ₀ from 0 to 1.
Calculating the N-controllability costs CCNI ₀ is the number of procedures necessary to the logical value Vi ₀ from 1 to 0 of the output lines i _0. That is, based on the structure of interest to the circuit element i, and controllable costs CC0,1 input lines i _i of the circuit element i, P, a logic value Vi ₀ of N and the output lines i ₀ as a parameter, an input circuit, a logical product The controllable costs CC0, 1, P, and N of the circuit, the OR circuit, the exclusive OR circuit, and the flip-flop are determined as follows. When Vi ₀ = 0, when _{CC0i 0 = 0 Vi 0 = 1} , if CC1i ₀ = ₀ circuit element i is an input circuit _{CC0i 0 = 1 (Vi 0 =} 1, X) CC1i 0 = 1 (Vi 0 = 0, X) CCPo ₀ = 1 (Vi ₀ = 0) CCPo ₀ = 2 (Vi ₀ = 1, X) CCNi ₀ = 1 (Vi ₀ = 1) CCNi ₀ = 2 (Vi ₀ = 0, X) circuit When element i is an AND circuit

[0017]

(Equation 1)

When the circuit element i is an OR circuit

[0019]

(Equation 2)

The circuit element i is (think of two inputs for simplicity.) When an exclusive OR circuit _{CC0i o = min (CC0i 1 +} CC0i 2, CC1
_{i 1 + CC1i 2) (Vi} o = 1, X) CC1i o = min (CC0i 1 + CC1i 2, CC1
i ₁ + CC 0 i ₂ ) (Vi _o = 0, X) CCP i _o = min (CC 0 i ₁ + CCPi ₂ , CC 0)
i ₂ + CCPi ₁ , CC1i ₁ + CCNi ₂ , CC1i
_{2 + CCNi 1) CCNi o =} min (CC1i 1 + CCPi 2, CC1
i ₂ + CCPi ₁ , CC0i ₁ + CCNi ₂ , CC0i
If ₂ + CCNi ₁₎ circuit element i is Di flip-flop circuit _{CC0i o = CC0i set + min (} CC1i reset,
_{CC0i data + CCPi clock) (Vi} o = 1, X) CC1i o = CC0i reset + min (CC1i set,
_{CC1i data + CCPi clock) (Vi} o = 0, X) CCPi o = CC1i o (Vi o = 0) CCPi o = CC0i o + CC1i o (Vi o = 1, X) CCNi o = CC1i o + CC0i o (Vi o = _{0, X) CCNi o = CC0i} o (Vi o = 1) the cost derivation section 9, the fault-signal line i _f, controllable costs CCTi as a negative logic T = to S configuration stuck-type S
_f and the continuous logical value CVi on the fault setting signal line _if .
(When the set stuck-at fault species S is 1 0, S is 10 when 0) _f and control continuous logic value to derive the constant weighted sum of the differences CCVi _f between the cost CTi. _{CTi = a × CCTi f + b} × CCVi f (a,
b: constant) The minimum cost deriving unit 10 derives the minimum cost Cmin from the obtained cost group CTi.

The input signal setting unit 11 calculates the minimum cost Cmi
n and the previous cost COST (t-1). If the minimum cost Cmin is smaller, the input signal Vin, min (t) indicating the minimum cost Cmin is set as the next input signal Vin (t). Then, one of the inputs _icl indicating the clock is selected with respect to the previous input signal Vin (t-1), and the input signal obtained by inverting the input _icl is set as the next input signal.

As shown in FIG. 4, the input i _cl indicating the clock is directly connected to the clock input of the flip-flop (a) as shown in FIG. 4 or indirectly connected to the clock input of the flip-flop (b) through a logic circuit. ) Etc. are connected. In the example of FIG. 4, there are two (a) and (b). As a selection method, when there is only one clock input, this is selected, and when there are two or more clock inputs, one is selected using a random number.

Next, an embodiment will be described with reference to the flowchart of FIG.
The operation of the present invention will be described using the circuit of FIG. 6 and the cost search tree of FIG. For the fault 12 assumed this time, the fault setting signal line is G17, and the fault type is 1 stuck-at fault. However, the constants a = 1 and b = 3 were used for calculating the cost CTi.

First, the input signal Vin (0) is changed to (clk =
0, G0 = 0, G1 = 0, G2 = 0, G3 = 0, G4 =
0).

Next, a circuit simulation is performed on the input signal Vin (0), and the logical value signal V
and i, a continuous logic value CVi _d of the circuit element i _d, 0,
The control cost CC0i of 1, P, N is obtained, and the cost COST (0) at time 0 is derived. In the embodiment here, COS
T (0) was 38.9.

Next, five input signals Vin, i (t) which are separated from the initial input signal Vin (0) by a Hamming distance 1 are generated, a circuit simulation is performed for each input signal, and an initial input signal is generated. Similarly, the cost CTi is derived.

The minimum cost Cmin is:
35.1. Here, input line number 0 is selected.

[0028]

[Table 1]

Since the cost Cmin is smaller than the cost 38.9 one time before, the input signal is the 0th (1, 0, 0,
0, 0) is selected, and the test sequence at time 1 is obtained.

Next, the time is advanced by one, the next test sequence is created, and the process is continued until the minimum cost becomes smaller than 10 which is the difference between binary logical values in continuous logical values. In this example, at time 5, the cost becomes smaller than 1.3 and 10, and a test sequence for detecting an assumed failure (G17: VD) can be generated.

If the cost does not become smaller than the previous cost, it is necessary to change the state of the sequential circuit without initializing the search and resetting the input pattern that is longer than the Hamming distance as in the conventional example. Since the method of changing the clock input is suitable, it is effective for circuits with tens of thousands of gates or circuits with complicated structures where the phenomenon that the cost does not decrease often occurs, and the calculation time for generating the test sequence Can be shortened.

In the logic circuit shown in FIG.
Consider a problem in which 23 signal lines have a stuck-at-1 fault and find a test sequence to find it. In the initial state, the input 22 is logic 1, and the output of the de-flip-flop 24 is logic X. From this initial state, a test sequence for controlling the output value of the output 23 to logic 0 is obtained. In the circuit of FIG. 8, there is no input pattern sequence that directly changes the output value of the output 23 from the logic X to the logic 0. In order to control the output value of the output 23 to the logic 0,
It must change from logic X to logic 1 and to logic 0. When the conventional logical value shown in FIG. 9 is used,
When the output value of the output 23 is changed from logic X to logic 1,
Comparing the distance to the final logical state of logical 0, logical 1 is farther than logical X. Therefore, the output value is set to logic 1
The input pattern sequence to be changed to is not selected and falls into a local solution. On the other hand, when continuous logical values are used, the distance from the final logical state, logical 0, is the same in logical X and logical 1, and the test sequence can be obtained without falling into a local solution. .

As described above, according to the present invention, the number of procedures required for inspecting the fault setting signal line _if and the fault type f and a continuous value indicating the degree of change due to the input pattern of the fault setting signal line _if. Since a logical value is used as a cost, a combinatorial search that does not change unnecessary D flip-flops is not performed, so that the test sequence can be reduced and the calculation time can be reduced.

[0034]

According to the present invention, when the calculated cost does not become smaller than the previous cost, the state of the sequential circuit can be changed without initializing the search or resetting the input pattern farther than the Hamming distance. Since this is the most effective method of changing the clock input, it is effective for circuits with tens of thousands of gates or circuits with complicated structures where phenomena that do not reduce the cost often occur. The calculation time for can be shortened.

Further, as a cost, the failure setting signal line _if
And a continuous logic value indicating the degree of change due to the input pattern with the number of required procedures to inspect the fault type f fault-signal line i _f due to the use as a cost, unnecessary D flip-flop Since a combinatorial search that does not change is not performed, the test sequence can be reduced and the calculation time can be reduced.

Successive logical values are logical 0, logical 1, logical X
Are arranged on a circle, and the undetermined logic X is distinguished from the determined logic, so that a circuit including a D flip-flop having an undetermined logic value does not fall into a local solution, and the test sequence Can be generated.

[Brief description of the drawings]

FIG. 1 is a configuration diagram of a test sequence generation device according to an embodiment of the present invention.

FIG. 2 is a continuous logical value diagram of a circuit element;

FIG. 3 is a logical relationship diagram of an OR circuit element;

FIG. 4 is a diagram showing a clock input;

FIG. 5 is a flowchart of an embodiment of the present invention.

FIG. 6 is a sequential circuit diagram.

FIG. 7 is a cost search tree diagram showing search results in the embodiment.

FIG. 8 is a sequential circuit diagram for explaining a continuous logical value;

FIG. 9 is a conventional logical value diagram of a circuit element.

FIG. 10 is a sequential circuit diagram for explaining a conventional example.

[Explanation of symbols]

 Reference Signs List 1 input signal generation unit 2 IN 3 OUT 4 circuit simulator 5 failure setting signal 6 input signal generation unit 7 controllable cost derivation unit 8 continuous logical value derivation unit 9 cost derivation unit 10 minimum cost derivation unit 11 input signal setting unit 12 failure 21 clock 22 input 23 output 24 D flip-flop 31 NOR 32 output line 33 input 34 D flip-flop 35 output line 36 NOR 37 output line 38 clock 39 input

Claims (3)

(57) [Claims] 1. A sequential circuit having N inputs and M outputs, an arbitrary fault setting signal line assuming a stuck-at fault of 0 or 1, a logic value of each circuit element by pseudo-executing the sequential circuit Circuit simulator, a continuous logic value derivation unit for deriving a continuous logic value of each circuit element, a controllable cost derivation unit for deriving a controllable cost of each circuit element, and the N inputs An input signal generation unit for generating two or more L input signals, and executing the sequential circuit for each of the input signals in a pseudo manner to control the controllable cost and the continuous logical value of the fault setting signal line. A cost deriving unit that derives the total as a cost,
A minimum cost deriving unit for obtaining the minimum cost among the obtained costs, and comparing the minimum cost with the previous cost. If the current minimum cost is smaller, an input signal indicating the minimum cost is input to the next input signal. Otherwise, the test sequence generation device includes: an input signal determination unit that sets an input signal obtained by inverting one of the inputs indicating the clock with respect to the previous input signal as a next input signal. 2. A continuous logic value of a circuit element is expressed by a continuous value between a logic 0 representing an OFF state, a logic 1 representing an ON state, and a logic X representing an undetermined state. The test sequence generation device according to claim 1, wherein the test sequence generation device is a continuous logic value output to an output line of the circuit element based on the circuit element, based on the continuous logic value of the line. 3. The controllable cost of the output line of the circuit element is based on the structure of the circuit, and the controllable cost set of the input line set of each circuit element and the logical value of the output line of the circuit element are used as parameters. 0 controllable cost, which is the number of procedures required to set the logical value of the line to 0, 1 controllable cost, which is the number of procedures required to set the logical value of the output line to 1, and P controllable cost, which is the number of procedures required to change the logical value of the line from 0 to 1, and N controllable cost, which is the number of procedures required to change the logical value of the output line from 1 to 0 The test sequence generation device according to claim 1, wherein