Apparatus and method for simulating logic faults

Claim 2

An automated process of constructing an output fault list for digital circuitry including at least one pair of cascaded logic elements, said process comprising the use of a programmed digital computer having stored in its internal memory a program enabling the computer to periodically perform the following steps: determining the particular logic elements having inputs or input fault lists that changed during the preceding computation; and computing for each of said particular logic elements the errorfree output and a list of all faults on the input fault lists of that particular element and all possible internal faults of that particular element which alter the output of that particular logic element.

Claim 3

An automated process of computing lists of fault conditions that can be detected in a logic circuit containing a plurality of cascaded logic elements, said process comprising the use of a programmed digital computer having stored in its interval memory a program enAbling the computer to perform at periodic intervals the following steps: computing a list of active logic elements, that is, those logic elements having inputs or input fault lists that changed during the preceding interval; computing the error-free output of each active logic element; computing for each particular active logic element a first list of only those fault conditions on the input fault lists of said particular element capable of propagating through said particular element, thereby causing the output signal of said particular element to be complemented; computing a second list of those fault conditions occurring within said particular active logic element that cause said output signal to be complemented; and combining said first and second lists to form the output fault list of said particular logic element.

Claim 4

An automated process of computing lists of fault conditions that can be detected in a logic circuit containing a plurality of cascaded logic elements, said process comprising the use of a programmed digital computer having stored in its interval memory a program enAbling the computer to perform at periodic intervals the following steps: computing a list of active logic elements, that is, those logic elements having inputs or input fault lists that changed during the preceding interval; computing the error-free output of each active logic element; computing for each particular active logic element a first list of only those fault conditions on the input fault lists of said particular element capable of propagating through said particular element, thereby causing the output signal of said particular element to be complemented; computing a second list of those fault conditions occurring within said particular active logic element that cause said output signal to be complemented; and combining said first and second lists to form the output fault list of said particular logic element.

Claim 5

The machine process of claim 2 further comprising the automated step of; flagging each logic element having as an input the output of one of said active logic elements.

Claim 6

The automated process of claim 2 wherein said step of computing a first list of only those fault conditions that are capable of propagating through said particular logic element further comprises, in case said particular logic element is a NOR gate or an OR gate, the automated steps of: forming the mathematical set intersection, I, of the fault lists on all inputs to said particular logic element that have an error-free logic value of 1; forming the mathematical set union, U, of the fault lists on all inputs to said particular logic element that have an error-free logic value of 0; setting said list of fault conditions equal to the mathematical set difference I-U if any of said inputs to said particular logic element have an error-free logic value of 1; and setting said list of fault conditions equal to said set union U if all of said inputs to said particular logic element have an error-free logic value of 0.

Claim 7

The automated process of claim 2 wherein said step of computing a first list of only those fault conditions that are capable of propagating through said particular logic element further comprises, in case said particular logic element is a NAND or an AND gate, the automated steps of: forming the mathematical set intersection, I, of the fault lists on all inputs to said particular logic element that have an error-free logic value of 0; forming the mathematical set union, U, of the fault lists on all inputs to said particular logic element that have an error-free logic value of 1; setting said list of fault conditions equal to the mathematical set difference I-U if any of said inputs to said particular logic element have an error-free logic value of 0; and setting said list of fault conditions equal to said set union U if all of said inputs to said particular logic element have an error-free logic value of 1.

Claim 8

The automated process of claim 2 wherein said step of computing a first list of only those fault conditions that are capable of propagating through said particular logic element further comprises, in case said particular logic element is a NOR gate or an OR gate, the automated steps of: determining whether said particular logic element is a reconverging fan-out element; performing the following four steps if said particular logic element is a reconverging fan-out element: forming the mathematical set intersection, I, of the fault lists on all inputs to said particular logic element that have an error-free logic value of 1, forming the mathematical set union, U, of the fault lists on all inputs to said particular logic element that have an error-free logic value of 0, setting said list of fault conditions equal to the mathematical set difference I-U if any of said inputs to said particular logic element have an error-free logic value of 1, and setting said list of fault conditions equal to said set union U if all of said inputs to said particular logic element have an error-free logic value of 0; and performing the following three steps if said particular logic element is not a reconverging fan-out element: setting said list of fault conditions equal to the mathematical set union of the fault lists on all inputs to said particular logic element if the error-free logic values on all said inputs are 0; setting said list of fault conditions equal to the fault list on the input to said particular logic element that has an error-free logic value of 1 if only one of the inputs to said particular logic element has an error-free logic value of 1; and setting said list of fault conditions equal to the null set if more than one of the inputs to said particular logic element has an error-free logic value of 1.

Claim 9

The machine process of claim 2 wherein said step of computing a first list of only those fault conditions that are capable of propagating through said particular logic element further comprises, in case said particular logic element is a flip-flop, the machine steps of: determining the current error-free output logic values of said flip-flop; determining the current input and output fault lists of said flip-flop; determining the new error-free input logic values that are to be applied to said flip-flop; accessing a table having information such as that shown in FIGS. 3D and 3E, by using said current output logic values and said new input logic values, to determine the relationship between said current input and output fault lists and the new output fault lists that will result from the application of said new error-free input logic values to said flip-flop; and using said current input and output fault lists to compute said new output fault lists in accordance with said relationship.

Claim 10

The automated process of claim 2 wherein said step of computing a first list of only those fault conditions that are capable of propagating through said particular logic element further comprises, in case said particular logic element is a NAND gate or an AND gate, the automated steps of: determining whether said particular logic element is a reconverging fan-out element; performing the following four steps if said particular logic element is a reconverging fan-out element: forming the mathematical set intersection, I, of the fault lists on all inputs to said particular logic element that have an error-free logic value of 0, forming the mathematical set union, U, of the fault lists on all inputs to said particular logic element that have an error-free logic value of 1, setting said list of fault conditions equal to the mathematical set difference I-U if any of said inputs to said particular logic element have an error-free logic value of 0, and, setting said list of fault conditions equal to said set union U if all of said inputs to said particular logic element have an error-free logic value of 1; and performing the following three steps if said particular logic element is not a reconverging fan-out element: setting said list of fault conditions equal to the mathematical set union of the fault lists on all inputs to said particular logic element if the error-free logic values on all said inputs are 1; setting said list of fault conditions equal to the fault list on the input to said particular logic element that has an error-free logic value of 0 if only one of the inputs to said particular logic element has an error-free logic value of 0; and setting said list of fault conditions equal to the null set if more than one of the inputs to said particular logic element has an error-free logic value of 0.

Claim 13

Apparatus for performing a plurality of computations at periodic intervals so as to compute lists of fault conditions that can be detected in a logic circuit containing a plurality of cascaded logic elements, said apparatus comprising: means for computing a list of active logic elements, that is, those logic elements having inputs or input fault lists that changed during the preceding interval; means for computing the error-free output of each active logic element; means for computing for each particular active logic element a first list of only those fault conditions on the input fault lists of said particular element capable of propagating through said particular element, thereby causing the output signal of said particular element to be complemented; means for computing a second list of only those fault conditions occurring within said particular active logic element that cause said output signal to be complemented; and means for combining said first and second lists to form the output fault list of said particular logic element.

Claim 14

Apparatus for performing a plurality of computations at periodic intervals so as to compute lists of fault conditions that can be detected in a logic circuit containing a plurality of cascaded logic elements, said apparatus comprising: means for computing a list of active logic elements, that is, those logic elements having inputs or input fault lists that changed during the preceding interval; means for computing the error-free output of each active logic element; means for computing for each particular active logic element a first list of only those fault conditions on the input fault lists of said particular element capable of propagating through said particular element, thereby causing the output signal of said particular element to be complemented; means for computing a second list of only those fault conditions occurring within said particular active logic element that cause said output signal to be complemented; and means for combining said first and second lists to form the output fault list of said particular logic element.

Claim 15

The apparatus of claim 10 further comprising: means for flagging each logic element having as an input the output of one of said active logic elements.

Claim 16

The apparatus of claim 10 wherein said means for computing a first list of only those fault conditions that are capable of propagating through said particular logic element further comprises, in case said particular logic element is a NOR gate or an OR gate: means for forming the mathematical set intersection, I, of the fault lists on all inputs to said particular logic element that have an error-free logic value of 1; means for forming the mathematical set union, U, of the fault lists on all inputs to said particular logic element that have an error-free logic value of 0; means for setting said list of fault conditions equal to the mathematical set difference I-U if any of said inputs to said particular logic element have an error-free logic value of 1; and means for setting said list of fault conditions equal to said set union U if all of said inputs to said particular logic element have an error-free logic value of 0.

Claim 17

The apparatus of claim 10 wherein said means for computing a first list of only those fault conditions that are capable of propagating through said particular logic element further comprises, in case said particular logic element is a NAND or an AND gate: means for forming the mathematical set intersection, I, of the fault lists on all inputs to said particular logic element that have an error-free logic value of 0; means for forming the mathematical set union, U, of the fault lists on all inputs to said particular logic element that have an error-free logic value of 1; means for setting said list of fault conditions equal to the mathematical set difference I-U if any of said inputs to said particular logic element have an error-free logic value of 0; and means for setting said list of fault conditions equal to said set union U if all of said inputs to said particular logic element have an error-free logic value of 1.

Claim 18

The apparatus of claim 10 wherein said means for computing a first list of only those fault conditions that are capable of propagating through said particular logic element further comprises, in case said particular logic element is a flip-flop: means for determining the current error-free output logic values of said flip-flop; means for determining the current input and output fault lIsts of said flip-flop; means for determining the new error-free input logic values that are to be applied to said flip-flop; means for accessing a table having information such as that shown in FIGS. 3D and 3E, by using said current output logic values and said new input logic values, to determine the relationship between said current input and output fault lists and the new output fault lists that will result from the application of said new error-free input logic values to said flip-flop; and means for using said current input and output fault lists to compute said new output fault lists in accordance with said relationship.