METHOD FOR DESIGNING FAULT DETECTION CIRCUIT

Abstract

A method for designing a fault detection circuit includes an extraction step of selecting a fixed signal value based on an index, and extracting, by using the fixed signal value selected, one or some but not all of three-signal implication relationships.

Claims

1. A method for designing a fault detection circuit configured to detect a fault in a target circuit for fault detection, the method comprising: an extraction step of selecting a fixed signal value based on an index, and extracting, by using the fixed signal value selected, one or some but not all of three-signal implication relationships that hold between nets in the target circuit; and a designing step of designing the fault detection circuit by selecting an implication relationship that is high in area efficiency from among the three-signal implication relationships extracted in the extraction step and a two-signal implication relationship that holds between the nets in the target circuit, wherein the extraction step includes at least one of: a first extraction step in which such ones of the three-signal implication relationships as have a fault-detection capability that is predictable from a number of faults detected by a two-signal implication relationship constitute a population for extraction, and the index is a first index which corresponds to a number of faults detected by three two-signal implication relationships; a second extraction step in which such ones of the three-signal implication relationships as have a fault-detection capability that is partly predictable from a number of faults detected by a two-signal implication relationship constitute a population for extraction, and the index is a second index which corresponds to a number of faults detected by one two-signal implication relationship; and a third extraction step in which such ones of the three-signal implication relationships as have a fault-detection capability that is unpredictable from a number of faults detected by a two-signal implication relationship constitute a population for extraction, and the index is a third index which corresponds to a number of implication relationships newly generated by the fixed signal value.

2. The method for designing a fault detection circuit according to claim 1, wherein the extraction step includes at least two of the first extraction step, the second extraction step, and the third extraction step.

3. The method for designing a fault detection circuit according to claim 2, wherein the extraction step includes all of the first extraction step, the second extraction step, and the third extraction step.

4. The method for designing a fault detection circuit according to claim 1, wherein the extraction step includes the first extraction step, and the first index is an index that corresponds to: a number of faults detected by a two-signal implication relationship between the fixed signal value and a value of a third port of a logic gate, the value of the third port of the logic gate serving as a condition for generating a new implication relationship between a first port and a second port of the logic gate; a maximum number of faults detected by a two-signal implication relationship of which a starting point is the first port; and a maximum number of faults detected by a two-signal implication relationship of which a starting point is the second port.

5. The method for designing a fault detection circuit according to claim 2, wherein the extraction step includes the first extraction step, and the first index is an index that corresponds to: a number of faults detected by a two-signal implication relationship between the fixed signal value and a value of a third port of a logic gate, the value of the third port of the logic gate serving as a condition for generating a new implication relationship between a first port and a second port of the logic gate; a maximum number of faults detected by a two-signal implication relationship of which a starting point is the first port; and a maximum number of faults detected by a two-signal implication relationship of which a starting point is the second port.

6. The method for designing a fault detection circuit according to claim 3, wherein the extraction step includes the first extraction step, and the first index is an index that corresponds to: a number of faults detected by a two-signal implication relationship between the fixed signal value and a value of a third port of a logic gate, the value of the third port of the logic gate serving as a condition for generating a new implication relationship between a first port and a second port of the logic gate; a maximum number of faults detected by a two-signal implication relationship of which a starting point is the first port; and a maximum number of faults detected by a two-signal implication relationship of which a starting point is the second port.

7. The method for designing a fault detection circuit according to claim 1, wherein the extraction step includes the second extraction step, and the second index is an index that corresponds to a number of faults detected by a two-signal implication relationship between the fixed signal value and a value of a third port of a logic gate, the value of the third port of the logic gate serving as a condition for generating a new implication relationship between a first port and a second port of the logic gate.

8. The method for designing a fault detection circuit according to claim 2, wherein the extraction step includes the second extraction step, and the second index is an index that corresponds to a number of faults detected by a two-signal implication relationship between the fixed signal value and a value of a third port of a logic gate, the value of the third port of the logic gate serving as a condition for generating a new implication relationship between a first port and a second port of the logic gate.

9. The method for designing a fault detection circuit according to claim 3, wherein the extraction step includes the second extraction step, and the second index is an index that corresponds to a number of faults detected by a two-signal implication relationship between the fixed signal value and a value of a third port of a logic gate, the value of the third port of the logic gate serving as a condition for generating a new implication relationship between a first port and a second port of the logic gate.

10. The method for designing a fault detection circuit according to claim 1, wherein the index is an index that corresponds to an occurrence probability of the fixed signal value.

11. The method for designing a fault detection circuit according to claim 2, wherein the index is an index that corresponds to an occurrence probability of the fixed signal value.

12. The method for designing a fault detection circuit according to claim 3, wherein the index is an index that corresponds to an occurrence probability of the fixed signal value.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0017] FIG. 1 is a diagram showing SPFM and LFM set for each level of ASIL.

[0018] FIG. 2 is a diagram showing a logic circuit for describing direct implication.

[0019] FIG. 3 is a diagram showing a logic circuit for describing indirect implication.

[0020] FIG. 4 is a diagram showing an example of the configuration of an implication checker using a two-signal implication relationship.

[0021] FIG. 5 is a diagram showing a two-input AND gate.

[0022] FIG. 6 is a diagram showing a three-input AND gate.

[0023] FIG. 7 is a diagram showing a two-input XOR gate.

[0024] FIG. 8 is a diagram showing a three-input AND-NOR gate.

[0025] FIG. 9 is a diagram showing a four-input multiplexer.

[0026] FIG. 10A is a diagram showing a first case of a three-signal implication relationship.

[0027] FIG. 10B is a diagram showing a second case of a three-signal implication relationship.

[0028] FIG. 10C is a diagram showing a third case of a three-signal implication relationship.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

[0029] First, a description will be given of a two-signal implication relationship. There are two methods for extracting a two-signal implication relationship that holds between nets in a circuit. One is a method that includes static learning of the configuration of a circuit, and the other is a method that uses a tool such as SAT Solver to confirm a relationship that holds in a simulation that is based on random input.

[0030] The method including the static learning of the configuration of a circuit is a method in which extraction of an implication relationship by means of direct implication and indirect implication is repeated until no more new implication relationship can be found.

[0031] FIG. 2 is a diagram showing a logic circuit for describing direct implication. FIG. 3 is a diagram showing a logic circuit for describing indirect implication. The logic circuits shown in FIG. 2 and FIG. 3 each include AND gates G1 and G2 and an OR gate G3. To a second input terminal of the AND gate G1 and to a first input terminal of the AND gate G2, an input signal a is fed. An output terminal of the AND gate G1 is connected to a first input terminal of the OR gate G3, and an output terminal of the AND gate G2 is connected to a second input terminal of the OR gate G3. From an output terminal of the OR gate G3, an output signal d is outputted.

[0032] Direct implication is an implication obtained from input-output relationship of a logic gate and the transitive law. In the example shown in FIG. 2, by following relationships (1) and (2) below, a direct implication (3) below is extracted.

a=0.fwdarw.b=0,a=0.fwdarw.c=0  (1)

b=0C∩c=0.fwdarw.d=0  (2)

a=0.fwdarw.d=0  (3)

[0033] Indirect implication is an implication that cannot be obtained from input-output relationship of a logic gate alone. For example, in the example shown in FIG. 3, even by following an input-output relationship of the logic gate from the output terminal of the OR gate G3, it cannot be determined to which one of the first and second input terminals of the OR gate G3, a signal of “1” is fed. Then, an indirect implication can be obtained through static learning by making use of “If P.fwdarw.Q is true, its contrapositive {circumflex over ( )}Q.fwdarw.{circumflex over ( )}{circumflex over ( )}P is also true.” In the example shown in FIG. 3, an indirect implication (4) below is extracted.

d=1.fwdarw.a=1  (4)

[0034] The method that uses a tool such as SAT Solver to confirm a relationship that holds in a simulation that is based on random input is executed in the following steps (i), (ii), and (iii) in this order. [0035] (i) Perform a simulation with about 32000 random input patterns, for example, and record values of all nets in a circuit. [0036] (ii) Extract, with respect to all signal pairs, relationships that are equivalent or inverse to results of the simulation. [0037] (iii) Confirm whether the relationships extracted in the step (ii) are correct by using a tool such as SAT Solver. Only a relationship that is confirmed to be correct by using a tool such as SAT Solver is regarded as an implication relationship.

[0038] FIG. 4 is a diagram showing an example of the configuration of an implication checker (an abnormality detection circuit) using a two-signal implication relationship. The implication checker shown in FIG. 4 includes an AND gate G4. To a first input terminal of the AND gate G4, a signal A is fed. To a second input terminal of the AND gate G4, an inverse signal of a signal B is fed. The implication checker shown in FIG. 4 confirms whether or not the implication relationship “A=1.fwdarw.B=1” is maintained. If the implication relationship “A=1.fwdarw.B=1” is maintained, an error signal ERR outputted from an output terminal of the AND gate G4 is “0”, which indicates normality. On the other hand, if the implication relationship “A=1.fwdarw.B=1” is not maintained due to a fault, an error signal ERR outputted from the output terminal of the AND gate G4 is “1”, which indicates a fault.

[0039] Next, a description will be given of a three-signal implication relationship. By extracting, with respect to all signals in a target circuit for fault detection, a two-signal implication relationship that holds in a case where a value of each signal is 0 and a two-signal implication relationship that holds in a case where the value of each signal is 1, it is possible to extract all three-signal implication relationships.

[0040] However, a target circuit for fault detection having a larger circuit scale has a larger number of signals therein and thus it will require a longer period of time to extract implication relationships therefrom.

[0041] Thus, according to the present embodiment, in a method for designing a fault detection circuit, there is introduced an index for selecting a fixed signal value to be used in extracting a three-signal implication relationship. By extracting one or some but not all of three-signal implication relationships that hold between nets in a target circuit for fault detection by using a fixed signal value selected based on an appropriate index, it is possible to extract a three-signal implication relationship that is high in fault-detection capability. Thereby, without extracting all the three-signal implication relationships, it is possible to design a fault detection circuit that has high fault-detection capability.

[0042] The inventor of the present invention analyzed three-signal implication relationships, and found out that many three-signal implication relationships are attributable to a new implication relationship between input and output of a logic gate caused by a fixed signal value.

[0043] For example, between input and output ports of a two-input AND gate G11 shown in FIG. 5, there are an implication relationship “Port A1: 0.fwdarw.Port Z: 0” and an implication relationship “Port A2: 0.fwdarw.Port Z: 0”. Here, by a value of a port of the two-input AND gate G11 being fixed, that is, by using a fixed signal value, a new implication relationship is generated.

[0044] As shown in FIG. 5, with the value of the port A2 fixed to 1, a new implication relationship “Port A1: 1.fwdarw.Port Z: 1” is generated. Also, as shown in FIG. 5, if the value of the port A1 is fixed to 1, a new implication relationship “Port A2: 1.fwdarw.Port Z: 1” is generated. Also, as shown in FIG. 5, if the value of the port Z is fixed to 0, a new implication relationship “Port A1: 1.fwdarw.PortA2: 0” is generated.

[0045] A three-input AND gate G12 shown in FIG. 6 is an example in which a new implication relationship is generated by fixing values of two ports.

[0046] A new implication relationship is generated not only between input and output ports, but also between two input ports. The two-input AND gate G11 shown in FIG. 5, a two-input XOR gate G13 shown in FIG. 7, and a three-input AND-NOR gate G14 shown in FIG. 8 are examples where a new implication relationship is generated between two input ports.

[0047] Further, in complex logic gates such as the three-input AND-NOR gate G14 shown in FIG. 8 and a four-input multiplexer M1 shown in FIG. 9 as well, a new implication relationship is generated by a fixed signal value. Note that, in FIG. 5 to 9, contrapositive implication relationships are also true, but indication thereof is omitted for the sake of simplicity. For example, in FIG. 5, when A2=1, “Port Z: 0.fwdarw.Port A1: 0” is also true.

[0048] A signal value in a target circuit for fault detection that is determined by a fixed signal value will all be identified with information of a two-signal implication relationship. Thus, a new implication relationship generated between input and output of a logic gates in the target circuit for fault detection also will all be identified by referring to a rule that defines an implication relationship newly generated in each of the logic gates.

[0049] From combinations of fixed signal values and newly generated implication relationships, various three-signal implication relationships are generated. Three-signal implication relationships can be classified into three cases as shown in FIG. 10A to FIG. 10C.

[0050] A two-signal implication relationship IM1 is a two-signal implication relationship between a signal value (a fixed signal value) fixed in a net N1 in a target circuit for fault detection and a value of a third port P3 of a logic gate G21, the value of the third port P3 of the logic gate G21 serving as a condition for generating a new implication relationship between a first port P1 and a second port P2 of the logic gate G21. Note that the third port P3 may include a plurality of third ports P3. A two-signal implication relationship IM2 is a two-signal implication relationship of which a starting point is the first port P1 and of which an end point is a net N2 in the target circuit for fault detection. A two-signal implication relationship IM3 is a two-signal implication relationship of which a starting point is the second port P2 and of which an end point is a net N3 in the target circuit for fault detection.

[0051] A first case shown in FIG. 10A is a case where a fault detection capability of a three-signal implication relationship is predictable from a number of faults detected by a two-signal implication relationship.

[0052] In the first case, a number of abnormalities detected by a three-signal implication relationship that holds between the nets N1 to N3 in the target circuit for fault detection is equal to a total of numbers of abnormalities detected by the two-signal implication relationships IM1 to IM3. And, a plurality of candidates exist for the net N2, and a plurality of candidates exist for the net N3 as well.

[0053] In the method for designing a fault detection circuit according to the present embodiment, a first extraction step is executed in which three-signal implication relationships corresponding to the first case constitute a population for extraction, a fixed signal value is selected based on a first index which corresponds to a number of faults detected by the three two-signal implication relationships IM1 to IM3, and by using the fixed signal selected, one or some but not all of the three-signal implication relationships are extracted.

[0054] Specifically, the first index is an index that corresponds to the number of faults detected by the two-signal implication relationship IM1, a maximum number of faults detected by the two-signal implication relationship IM2 of which the starting point is the first port P1, and a maximum number of faults detected by the two-signal implication relationship IM3 of which the starting point is the second port P2.

[0055] More specifically, the first index is a value obtained by multiplying a total value of the number of faults detected by the two-signal implication relationship IM1, the maximum number of faults detected by the two-signal implication relationship IM2 of which the starting point is the first port P1, and the maximum number of faults detected by the two-signal implication relationship IM3 of which the starting point is the second port P2 by an occurrence probability of the fixed signal value. Here, a occurrence probability of a fixed signal value is the probability of occurrence of the fixed signal value in the net N1 when the target circuit for fault detection is in operation.

[0056] In the first extraction step, by selecting such a fixed signal value as will cause the first index to be large, a three-signal implication relationship that is high in fault-detection capability is selected from among the three-signal implication relationships corresponding to the first case. In the first extraction step, with respect to the first index, by selecting about 5% of all fixed signal values, a three-signal implication relationship that is high in fault-detection capability can be efficiently selected from among the three-signal implication relationships corresponding to the first case.

[0057] A second case shown in FIG. 10B is a case where a fault-detection capability of a three-signal implication relationship is partly predictable from a number of faults detected by a two-signal implication relationship.

[0058] In the second case, the number of faults detected by the two-signal implication relationship IM1 is reflected in the number of abnormalities detected by the three-signal implication relationships that hold between the nets N1 to N3 in the target circuit for fault detection, but a number of detected abnormalities attributable to an implication relationship newly generated between the first port P1 and the second port P2 is unpredictable from a two-signal implication relationship.

[0059] In the method for designing a fault detection circuit according to the present embodiment, a second extraction step is executed in which three-signal implication relationships corresponding to the second case constitute a population for extraction, a fixed signal value is selected based on a second index which corresponds to the number of faults detected by the two-signal implication relationships IM1, and by using the fixed signal value selected, one or some but not all of the three-signal implication relationships are extracted.

[0060] Specifically, the second index is an index that corresponds to the number of faults detected by the two-signal implication relationship IM1.

[0061] More specifically, the second index is a value obtained by multiplying the number of faults detected by the two-signal implication relationship IM1 by the occurrence probability of the fixed signal value.

[0062] In the second extraction step, by selecting such a fixed signal value as will cause the second index to be large, a three-signal implication relationship that is high in fault-detection capability is selected from among the three-signal implication relationships corresponding to the second case. In the second extraction step, with respect to the second index, by selecting about 5% of all fixed signal values, a three-signal implication relationship that is high in fault-detection capability can be efficiently selected from among the three-signal implication relationships corresponding to the second case.

[0063] A third case shown in FIG. 10C is a case where a fault-detection capability of a three-signal implication relationship is unpredictable from a number of faults detected by a two-signal implication relationship.

[0064] In the method for designing a fault detection circuit according to the present embodiment, a third extraction step is executed in which three-signal implication relationships corresponding to the third case constitute a population for extraction, a fixed signal value is selected based on a third index which corresponds to a number of implication relationships newly generated by the fixed signal value, and by using the fixed signal value selected, one or some but not all of the three-signal implication relationships are extracted. Specifically, the third index is a value obtained by multiplying the number of newly generated implication relationships by the occurrence probability of the fixed signal value.

[0065] In the third extraction step, by selecting such a fixed signal value as will cause the third index to be large, a three-signal implication relationship that is high in fault-detection capability is selected from among the three-signal implication relationships corresponding to the third case. In the third extraction step, with respect to the third index, by selecting about 5% of all fixed signal values, a three-signal implication relationship that is high in fault-detection capability can be efficiently selected from among the three-signal implication relationships corresponding to the third case. Note that “about 5%” mentioned above is a mere example, and it can be thought that, depending on a target circuit, there may be a case where the percentage can be much smaller or larger than that.

[0066] Further, in the method for designing a fault detection circuit according to the present embodiment, a designing step is executed in which a fault detection circuit is designed by selecting such implication relations as are high in area efficiency from among the three-signal implication relationships extracted in the first to third extraction steps and a two-signal implication relationship that holds between the nets in a target circuit. Thereby, an implication checker (an abnormality detection circuit) is designed in which the three-signal implication relationships extracted in the first to third extraction steps are used. In the designing step, for example, selection is repeated, in order of area efficiency starting from an implication relationship with the highest area efficiency, until an area of the fault detection circuit reaches a predetermined value. Note that the area efficiency of an implication relationship is a rate of errors detected by the implication checker using the implication relationship with respect to a circuit area of the implication checker using the implication relationship.

[0067] The first to third extraction steps and the designing step are executed by an information processing device, for example.

[0068] In addition to the embodiments described above, the configuration of the present invention can be modified in many different forms without departing from the scope of the present disclosure. It should be understood that the foregoing embodiments are not limitative but illustrative in every respect, and that the technical scope of the present invention is not determined by the foregoing embodiments but by the claims, and should be construed to include all modifications equivalent in meaning and scope to the claims.

[0069] In the above embodiments, the first to third extraction steps are executed, but instead, only one of the first to third extraction steps may be executed, or only two of the first to third extraction steps may be executed. Note that, however, with more of the first to third extraction steps executed, more various types of target circuits can be dealt with.

[0070] The above-discussed method for designing a fault detection circuit is a method for designing a fault detection circuit configured to detect a fault in a target circuit for fault detection, the method including: an extraction step of selecting a fixed signal value based on an index, and extracting, by using the fixed signal value selected, one or some but not all of three-signal implication relationships that hold between nets in the target circuit; and a designing step of designing the fault detection circuit by selecting an implication relationship that is high in area efficiency from among the three-signal implication relationships extracted in the extraction step and a two-signal implication relationship that holds between the nets in the target circuit. Here, the extraction step includes at least one of: a first extraction step in which such ones of the three-signal implication relationships as have a fault-detection capability that is predictable from a number of faults detected by a two-signal implication relationship constitute a population for extraction, and the index is a first index which corresponds to a number of faults detected by three two-signal implication relationships; a second extraction step in which such ones of the three-signal implication relationships as have a fault-detection capability that is partly predictable from a number of faults detected by a two-signal implication relationship constitute a population for extraction, and the index is a second index which corresponds to a number of faults detected by one two-signal implication relationship; and a third extraction step in which such ones of the three-signal implication relationships as have a fault-detection capability that is unpredictable from a number of faults detected by a two-signal implication relationship constitute a population for extraction, and the index is a third index which corresponds to a number of implication relationships newly generated by the fixed signal value (a first configuration).

[0071] The method for designing a fault detection circuit according to the first configuration makes it possible to extract a three-signal implication relationship that is high in fault-detection capability.

[0072] In the method for designing a fault detection circuit according to the first configuration, the extraction step may include at least two of the first extraction step, the second extraction step, and the third extraction step (a second configuration).

[0073] The method for designing a fault detection circuit according to the second configuration is capable of dealing with a wide variety of target circuits.

[0074] In the method for designing a fault detection circuit according to the second configuration, the extraction step may include all of the first extraction step, the second extraction step, and the third extraction step (a third configuration).

[0075] The method for designing a fault detection circuit according to the third configuration is capable of dealing with a wider variety of target circuits.

[0076] In the method for designing a fault detection circuit according to any one of the first to third configurations, the extraction step may include the first extraction step, and the first index may be an index that corresponds to a number of faults detected by a two-signal implication relationship between the fixed signal value and a value of a third port (P3) of a logic gate (G21), the value of the third port P3 of the logic gate G21 serving as a condition for generating a new implication relationship between a first port (P1) and a second port (P2) of the logic gate (G21), a maximum number of faults detected by a two-signal implication relationship of which a starting point is the first port, and a maximum number of faults detected by a two-signal implication relationship of which a starting point is the second port (a fourth configuration).

[0077] In the method for designing a fault detection circuit according to any one of the first to fourth configurations, the extraction step may include the second extraction step, and the second index may be an index that corresponds to a number of faults detected by a two-signal implication relationship between the fixed signal value and a value of a third port (P3) of a logic gate, the value of the third port (P3) of the logic gate serving as a condition for generating a new implication relationship between a first port (P1) and a second port (P2) of the logic gate (G21) (a fifth configuration).

[0078] In the method for designing a fault detection circuit according to any one of the first to fifth configurations, the index may be an index corresponding to an occurrence probability of the fixed signal value (a sixth configuration).