US 6,857,094 B2 · Method and system for inferring fault propagation paths in combinational logic circuit

A fault propagation path inference system for inferring a logic state in a combinational logic circuit by repeating logic state decisions and implications and comparing the logic state with an expected value, which corresponds to a logic state that prevails when the combinational logic circuit operates normally, thereby inferring a fault propagation path in the combinational logic circuit, comprising:

decision-limit discrimination means for providing an upper limit on a decision level that represents a number of logic state decisions and, if the number of logic state decisions exceeds the upper limit on the decision level, switching the logic state decision to simple retrieval of a fault propagation path;
and
fault propagation path simple retrieval means for extracting a fan-in cone by tracing a net-list of the combinational logic circuit in an input direction from an undetermined gate whose output signal is faulty and whose input/output signal lines have a signal line the logic state of which is unknown, and registering, as a fault propagation path, a signal line, which is included in the fan-in cone, the logic state of which has not been decided.

In a method of inferring a logic state in a combinational logic circuit by repeating logic state decisions and implications and comparing the logic state with an expected value, which corresponds to a logic state that prevails when the combinational logic circuit operates normally, thereby inferring a fault propagation path in the combinational logic circuit, a fault propagation path simple retrieval method comprising the steps of:

retrieving an unprocessed gate, which has not undergone simple retrieval of a fault propagation path, from among one or plural undetermined gates whose output signals are faulty and whose input/output signal lines have a signal line the logic state of which is unknown;
and
retrieving a signal line, for which the logic state has not been determined, from among one or plural input signal lines of the unprocessed gate, and adopting the logic state of the retrieved signal line as a fault state and recording the logic state of the signal line in a logic state memory.

In a method of inferring a logic state in a combinational logic circuit by repeating logic state decisions and implications and comparing the logic state with an expected value, which corresponds to a logic state that prevails when the combinational logic circuit operates normally, thereby inferring a fault propagation path in the combinational logic circuit, a fault propagation path simple retrieval method comprising the steps of:

retrieving an unprocessed gate, which has not undergone simple retrieval of a fault propagation path, from among one or plural undetermined gates whose output signals are faulty and whose input/output signal lines have a signal line the logic state of which is unknown, and retrieving a signal line, for which the logic state has not been determined, from among one or plural input signal lines of the unprocessed gate;
and
retrieving, from the retrieved one or plural input signal lines, an input signal line for which there is a possibility that an output logic state of a gate will be made a fault state, by referring to gate function and expected values of gate input/output terminals, and adopting the logic state of the retrieved signal line as a fault state and registering the logic state of the signal line in a logic state storage unit.

A computer program for causing a computer to execute fault propagation path inferring processing for inferring a logic state in a combinational logic circuit by repeating logic state decisions and implications and comparing the logic state with an expected value, which corresponds to a logic state that prevails when the combinational logic circuit operates normally, thereby inferring a fault propagation path in the combinational logic circuit, said program causing the computer to execute the following processing:

unprocessed-gate retrieval processing for retrieving an unprocessed gate, which has not undergone simple retrieval of a fault propagation path, from among one or plural undetermined gates whose output signals are faulty and whose input/output signal lines have a signal line the logic state of which is unknown;
input signal line retrieval processing for retrieving a signal line, for which the logic state has not been determined, from among the input signal lines of the unprocessed gate;
and
fault propagation path registration processing for adopting the logic state of the retrieved signal line as a fault state and recording the state of the signal line in a logic state memory.

1 more element

A fault propagation path inferring method of inferring a logic state in a combinational logic circuit by repeating logic state decisions and implications and comparing the logic state with an expected value, which corresponds to a logic state that prevails when the combinational logic circuit operates normally, thereby inferring a fault propagation path in the combinational logic circuit, said method comprising the steps of:

(a) setting logic states of input/output terminals of the combinational circuit provided by an input unit, initializing a decision level that represents a number of logic state decisions, and setting an upper-limit value on the decision level;
(b) performing an implication operation for inferring logic states of input/output lines of an un-inferred gate from logic states of input/output signal lines of an already inferred gate at each gate in the combinational logic circuit, recording the inferred logic states in a logic state memory, and recording the decision level and a history of implications in a decision state memory;
(c) if a logic contradiction in the implication operation has not exceeded an allowable number, referring to logic states of signal lines that have been stored in the logic state memory and determining whether the logic states of all signal lines have been inferred to be a first logic value, a second logic value or “don't care”;
(d) if inferring of logic states of all signal lines is not finished, examining the logic states of input/outputs of gates in the combinational logic circuit and retrieving undetermined gates the logic state of which is incomplete;
(e) retrieving an undetermined gate, which has an output signal for which a fault state has been inferred, from the retrieved undetermined gates by referring to a logic circuit structure that has been stored in a logic-circuit structure memory and to the logic state of each signal line that has been stored in the logic state memory;
(f) determining whether the decision level has exceeding the upper-limit value;
(g) if the decision level has not exceeded the upper-limit value, deciding that a signal line that has been detected in logic value decision means is at the first logic value, incrementing the decision level, which represents the number of decisions, and returning processing to said step (b);
(h) executing fault propagation path simple retrieval comprising the following steps:
if the decision level has exceeded the upper-limit value, retrieving an unprocessed gate, which has not undergone simple retrieval of a fault propagation path, from among one or plural undetermined gates whose output signals are faulty and whose input/output signal lines have a signal line the logic state of which is unknown;
retrieving a signal line, for which the logic state has not been determined, from among one or plural input signal lines of the unprocessed gate;
and
adopting the logic state of the retrieved signal line as a fault state and recording the logic state of the signal line in the logic state memory;
(i) if it is determined that the logic states of all signal lines have been inferred, extracting signal lines having logic states different from those of expected values as fault propagation paths, extracting from the fault propagation paths a fault propagation path that will have a direct influence upon a fault output terminal when a fault exists on the path, and outputting the fault propagation path to an output unit;
(j) determining whether decision processing with regard to both the first and second logic values is finished for all decision lines that have been decided;
(k) if it has been determined that decision processing is not finished, retrieving by backtrack processing a decision line for which it has not been decided that the logic state is the second logic value, deciding that the state of the decision line is the second logic value, and returning the implication operation of said step (b);
and
(l) if it has been determined that decision processing is finished, terminating processing for extracting a fault propagation path.

14 more elements

A fault propagation path inferring method of inferring a logic state in a combinational logic circuit by repeating logic state decisions and implications and comparing the logic state with an expected value, which corresponds to a logic state that prevails when the combinational logic circuit operates normally, thereby inferring a fault propagation path in the combinational logic circuit, said method comprising the steps of:

(a) setting logic states of input/output terminals of the combinational circuit provided by an input unit, initializing a decision level that represents a number of logic state decisions, and setting an upper-limit value on the decision level;
(b) performing an implication operation for inferring logic states of input/output lines of an un-inferred gate from logic states of input/output signal lines of an already inferred gate at each gate in the combinational logic circuit, recording the inferred logic states in a logic state memory, and recording the decision level and a history of implications in a decision state memory;
(c) if a logic contradiction in the implication operation has not exceeded an allowable number, referring to logic states of signal lines that have been stored in the logic state memory and determining whether the logic states of all signal lines have been inferred to be a first logic value, a second logic value or “don't care”;
(d) if inferring of logic states of all signal lines is not finished, examining the logic states of input/outputs of gates in the combinational logic circuit and retrieving undetermined gates the logic state of which is incomplete;
(e) retrieving an undetermined gate, which has an output signal for which a fault state has been inferred, from the retrieved undetermined gates by referring to a logic circuit structure that has been stored in a logic-circuit structure memory and to the logic state of each signal line that has been stored in the logic state memory;
(f) determining whether the decision level has exceeding the upper-limit value;
(g) if the decision level has not exceeded the upper-limit value, deciding that a signal line that has been detected in logic value decision means is at the first logic value, incrementing the decision level, which represents the number of decisions, and returning processing to said step (b);
(h) executing fault propagation path simple retrieval comprising the following processing:
if the decision level has exceeded the upper-limit value, retrieving an unprocessed gate, which has not undergone simple retrieval of a fault propagation path, from among one or plural undetermined gates whose output signals are faulty and whose input/output signal lines have a signal line the logic state of which is unknown;
retrieving a signal line, for which the logic state has not been determined, from among one or plural input signal lines of the unprocessed gate;
and
retrieving, from the retrieved one or plural input signal lines, an input signal line for which there is a possibility that an output logic state of a gate will be made a fault state, by referring to gate function and expected values of gate input/output terminals;
and
adopting the logic state of the retrieved signal line as a fault state and recording the logic state of the signal line in the logic state memory;
(i) if it is determined that the logic states of all signal lines have been inferred, extracting one or plural signal lines having logic states different from those of expected values as fault propagation paths, extracting from the fault propagation paths a fault propagation path that will have a direct influence upon a fault output terminal when a fault exists on the path, and outputting the fault propagation path to an output unit;
(j) determining whether decision processing with regard to both the first and second logic values is finished for all decision lines that have been decided;
(k) if it has been determined that decision processing is not finished, retrieving by backtrack processing a decision line for which it has not been decided that the logic state is the second logic value, deciding that the state of the decision line is the second logic value, and returning the implication operation of said step (b);
and
(l) if it has been determined that decision processing is finished, terminating processing for extracting fault propagation paths.

16 more elements

A fault propagation path inference device comprising:

a logic-circuit structure memory for storing structure and connection information of a logic circuit;
a logic contradiction memory for storing gates in which one or plural logic contradictions have occurred during implication processing and the number of times logic contradictions have occurred;
a decision state memory for storing a decision level that prevails when logic states of respective ones of signal lines are inferred by implication;
a logic state memory for storing the logic state of each signal line, a history of implications and an expected value, which is a logic state, of each signal line prevailing when a combinatorial logic circuit is normal;
initializing means for setting logic-circuit type and logic states of input/output terminals provided by an input unit, initializing logic states of signal lines of the logic circuit, initializing the decision level and setting an upper-limit value thereof;
implication means for referring to a logic circuit structure that has been stored in said logic-circuit structure memory and to the logic state of each signal line that has been stored in said logic state memory, performing an implication operation at a gate connected to an input/output signal line set by said initialization means and at a gate connected to a signal line decided by the logic value decision means, inferring the logic states of gate input/output signal lines and, if a logic value has been inferred anew, recording the logic value and history of implication in said logic state memory and recording the decision level in said decision state memory, said decision level indicating under how many decisions the inference was made;
logic contradiction determination means for referring to said logic contradiction memory and determining whether number of logic contradictions of signal lines detected by said implication means has exceeded a predetermined allowable number;
processing-end discrimination means for referring to the logic state of each signal line stored in said logic state memory and determining whether the logic states of all signal lines have been inferred;
backtrack means for referring to states of decision stored in said decision state memory and to the logic states of signal lines stored in said logic state memory, erasing the logic state of a decision level for which processing has been completed as well as the history of implications and logic contradictions, and restoring the logic state of each signal line back to the logic state that prevailed prior to the rendering of the decision;
undetermined-gate retrieval means for examining the logic states of input/outputs of gates in the logic circuit and retrieving gates the logic state of which is incomplete;
fault propagation path influenced line retrieval means for retrieving an undetermined gate, which has an output signal for which a fault state has been inferred, from the undetermined gates retrieved by said undetermined-gate retrieval means, by referring to a logic circuit structure that has been stored in said logic-circuit structure memory and to the logic state of each signal line that has been stored in said logic state memory;
decision-limit discrimination means for determining whether the next decision exceeds a predetermined upper-limit value on decisions;
logic value decision means for deciding a logic state by selecting an input signal line of an undetermined gate for which the output signal is faulty, said undetermined gate having been detected by said fault propagation path influenced line retrieval means;
fault propagation path simple retrieval means for extracting a fan-in cone by tracing a circuit in an input direction from an undetermined gate, and registering all signal lines, for which the logic state has not been decided among paths included in the fan-in cone, as fault propagation paths in said logic state memory;
logic value comparison means for comparing the obtained logic state of each signal line with an expected value representing the logic state of each signal line found by logic simulation in a normal circuit, and extracting a fault propagation path;
and
fault output terminal related line extraction means for extracting, from one or plural fault propagation paths that have been extracted by said logic value comparison means, a fault propagation path that will have a direct influence upon a fault output terminal when a fault exists on the path, and outputting data to an output unit.

14 more elements

A fault propagation path inference device comprising:

a logic-circuit structure memory for storing structure and connection information of a logic circuit;
a logic contradiction memory for storing gates in which logic contradictions have occurred during implication processing and the number of times logic contradictions have occurred;
a decision state memory for storing a decision level that prevails when logic states of respective ones of signal lines are inferred by implication;
a logic state memory for storing the logic state of each signal line, a history of implications and an expected value, which is a logic state, of each signal line prevailing when a combinatorial logic circuit is normal;
initializing means for setting logic-circuit type and logic states of input/output terminals provided by an input unit, initializing logic states of signal lines of the logic circuit, initializing the decision level and setting an upper-limit value thereof;
implication means for referring to a logic circuit structure that has been stored in said logic-circuit structure memory and to the logic state of each signal line that has been stored in said logic state memory, performing an implication operation at a gate connected to an input/output signal line set by said initialization means and at a gate connected to a signal line decided by the logic value decision means, inferring the logic states of gate input/output signal lines and, if a logic value has been inferred anew, recording the logic value and history of implication in said logic state memory and recording the decision level in said decision state memory, said decision level indicating under how many decisions the inference was made;
logic contradiction determination means for referring to said logic contradiction memory and determining whether number of logic contradictions of signal lines detected by said implication means has exceeded a predetermined allowable number;
processing-end discrimination means for referring to the logic state of each signal line stored in said logic state memory and determining whether the logic states of all signal lines have been inferred;
backtrack means for referring to states of decision steroids in said decision state memory and to the logic states of signal lines stored in said logic state memory, erasing the logic state of a decision level for which processing has been completed as well as the history of implications and logic contradictions, and restoring the logic state of each signal line back to the logic state that prevailed prior to the rendering of the decision;
undetermined-gate retrieval means for examining the logic states of input/outputs of gates in the logic circuit and retrieving gates the logic state of which is incomplete;
fault propagation path influenced line retrieval means for retrieving an undetermined gate, which has an output signal for which a fault state has been inferred, from the undetermined gates retrieved by said undetermined-gate retrieval means, by referring to a logic circuit structure that has been stored in said logic-circuit structure memory and to the logic state of each signal line that has been stored in said logic state memory;
decision-limit discrimination means for determining whether the next decision exceeds a predetermined upper-limit value on decisions;
logic value decision means for deciding a logic state by selecting an input signal line of an undetermined gate for which the output signal is faulty, said undetermined gate having been detected by said fault propagation path influenced line retrieval means;
fault propagation path simple retrieval means for tracing, in an input direction, a signal line along which there is a possibility that a fault state will propagate to an undetermined gate, while referring to expected values of signal lines and to gate function, from an undetermined gate whose output signal is faulty and whose input/output signal lines have a signal line the logic state of which is unknown, and registering the traced signal lines as fault propagation paths;
logic value comparison means for comparing the obtained logic state of each signal line with an expected value representing the logic state of each signal line found by logic simulation in a normal circuit, and extracting a fault propagation path;
and
fault output terminal related line extraction means for extracting, from the fault propagation paths that have been extracted by said logic value comparison means, a fault propagation path that will have a direct influence upon a fault output terminal when a fault exists on the path, and outputting data to an output unit.

14 more elements

A fault propagation path inferring system for inferring a logic state in a combinational logic circuit by repeating logic state decisions and implications and comparing the logic states with expected values, which are logic states that prevail when the combinational logic circuit operates normally, thereby inferring a fault propagation path in the combinational logic circuit, comprising:

decision-limit altering means for determining whether a predetermined decision-limit reset condition has been satisfied and, if said condition has been satisfied, resetting a decision level that represents a number of logic state decisions and restoring the logic state to a logic state where the number of decisions falls below a decision limit value that has been reset;
decision-limit discrimination means for providing an upper limit on the decision level that represents the number of logic state decisions and, if the number of logic state decisions exceeds the upper limit of the decision level, switching the decision of logic states to simple retrieval of fault propagation paths;
and
either
first fault propagation path simple retrieval means for extracting a fan-in cone by tracing a net list of the combinational logic circuit in an input direction from an undetermined gate whose output signal is faulty and whose input/output signal lines have a signal line the logic state of which is unknown, and registering, as fault propagation paths, signal lines, included in the fan-in cone, the logic states of which have not been decided;
or
second fault propagation path simple retrieval means for tracing, in an input direction, a signal line along which there is a possibility that a fault state will propagate to an undetermined gate, while referring to expected values of signal lines and to gate function, from an undetermined gate whose output signal is faulty and whose input/output signal lines have a signal line the logic state of which is unknown, and registering the traced signal line as a fault propagation path.

4 more elements

Method and system for inferring fault propagation paths in combinational logic circuit

Life of this patent

Method and system for inferring fault propagation paths in combinational logic circuit

Life of this patent

Abstract

Claims27