The simplest technique for fault simulation is serial fault simulation. In this method, a fault will be inserted into the circuit and test vectors are applied one at a time. The main disadvantage of this fault simulation method is the time it takes for running simulations or all test vectors as many times as there are faults in the circuit. This method does not require any special software and a standard gate level simulator can be used for this purpose. Other approaches such as concurrent or parallel fault simulation are used for a better performance. The success of a concurrent fault simulator lies in the fact that only the difference between the good model of the circuit and faulty circuits are simulated. Since the difference between a good and a faulty circuit is only at the site of a fault, the values of the majority of the signals in the two circuits remain the same. Simulation speed is improved by simulating only those parts of the circuit that are different from the good circuit. Therefore, instead of recording the circuit status of all the bad machines, a concurrent fault simulator records the differences between faulty circuits and the good machine. Concurrent fault simulation is efficient but it requires a dedicated simulation program.

for every test vector, Vi,
{ /* compute good machine circuit status */
if (Vi is the first vector)
{ Initialize circuit status; }
else
{ Remove the previously injected fault;
Recover current states;}
Set Vi pattern at the primary inputs;
Perform event-driven simulation;
/* compute faulty machine circuit status */
for every undetected faulty machine, Bj,
{Remove the previous injected fault;
Recover current states;
Inject current fault;
Perform event driven simulation;
if the fault is detected
Drop the fault;}
}

In this algorithm, a test vector is applied to the circuit and the good machine will be simulated for that test. After simulation of the good machine, simulation will be done for every undetected fault with the same test vector. This is done by applying a test and injecting an undetected fault to the circuit model and performing the simulation. Simulation results will be compared with that of the fault-free circuit. The injected fault is detected if primary outputs of the faulty circuit are different than those of the good circuit. In this case the fault will be removed from fault list, otherwise the memory status of the faulty circuit will be saved for fault simulation of the next test vector. This is illustrated in Figure 2. The process of applying tests and examination of faulty circuits continues until a satisfactory fault coverage has been reached or there are no more test vectors.

Referring to Figure 2, in the first time frame, the output values of all circuit memory elements are X and all the good and bad machines will be simulated with the applied test vector (V1). Since simulation of the next time frame must be the continuation of the present time frame, faulty circuits save their current status to be restored in the next time frame (f_1,1, f_2,1, and f_3,1 states of f₁, f₂, and f₃ faulty circuits are saved in the first time frame). To keep the current status of a circuit, it is sufficient to store the input value of all circuit flip-flops. This is achieved by flip-flops having internal storage capability which has been implemented as a dynamic list to reduce memory requirements.

In the next time frame, the next test vector (V2) will be applied to the circuit and the faults will be injected to the circuit. For every faulty circuit the flip-flop output values will be retrieved so that the circuit returns to its correct status for the simulation to continue from this point on. Also in each simulation step, if the inserted fault is detected, it will be removed from fault list and its corresponding allocated memory in flip-flop internal data structure will be freed. An example of this case is fault f₂ in Figure 2 which has been detected in the second time frame and its state (f_2,1) removed. The fault is detected because its effect propagates to the circuit primary outputs.

It is worth noting that unlike concurrent fault simulation that requires the value difference information on every node, this method only requires the value difference information on the flip-flops. This results in a substantial less memory requirement for the differential fault simulator.

Figure 2. Fault Simulation Steps

Differential fault simulation has been implemented by modeling gates and wires in VHDL and running VHDL simulation for performing fault simulation. The VHDL implementation consists of a circuit analyzer and an interconnection of gates and wires. The circuit analyzer is responsible for construction of a fault list, reading test vectors from an input file and simulation of the circuit for all undetected faults. After simulating with each test vector, the output response will be analyzed and detected faults will be removed from fault list. This process will be done for all test vectors and the final fault coverage will be reported by the circuit analyzer.

A block diagram of our VHDL differential fault simulation environment is shown in Figure 3. The primary inputs and outputs of the sequential circuit are connected to the circuit analyzer which applies test vectors to the circuit and analyzes the output response. The fault list is also implemented as a dynamic linked list that facilitates removal of detected faults. Two global signals are used for injecting faults to the circuit. The first signal represents the id number of the line to be faulted and the second represents the fault type, i.e. stuck at 0 or stuck at 1. The sections that follow describe modeling for gates, wires, flip-flops, and the circuit analyzer in VHDL.

Figure 3. Fault Simulation Testbench

Most digital circuits can be considered as a collection of gates that are connected by signal lines. Since the main functionality of the circuit is based on the functionality of its gates, the usual way for modeling a circuit in VHDL is writing a model for each gate and connecting them by signals. These signals have no special task except carrying values from one place to another. Although this is an accepted way for describing circuit structures, for our fault simulation, we found it more convenient to model lines as components and gates as resolution functions. In other words, instead of considering the circuit as a set of gates that are connected by lines, we have considered it as an interconnection of lines that are joined by gates. Figure 4 shows these two gate level structures.

Figure 4. Gate Level Description Alternatives

The first and most important advantage of this modeling method is that it allows gates with any number of inputs. In the conventional modeling style, several models must be developed for the same logical function with different number of inputs. Using a resolution function for gate models, allows multiple signals to be connected to the same function.

ENTITY wire is
GENERIC (id_num : NATURAL);
PORT (input : IN qit; output : OUT qit);
END wire;
ARCHITECTURE behavioral OF wire IS
BEGIN
-- faulty_wire and fault_type are global signals
PROCESS (inputs, faulty_wire)
BEGIN
IF(id_num /= faulty_wire) THEN
output <= input;
ELSIF (fault_type = s_a_0) THEN
output <= 0';
ELSE
output <= 1';
END IF;
END PROCESS;
END behavioral;

As seen in this description, when there is no fault on a line, it simply propagates values from one end of the line to its other end (output). In the presence of a fault, the signal line will have a fixed 0 or 1 value depending on the fault type. Presence or absence of a fault is determined by comparing a line id number with faulty_line global signal. Each line has a unique id number that distinguishes it from other lines. Fault on a line is inserted by assigning its id number to the fault specification global signals.

SIGNAL nand1 : nand_gate;
SIGNAL input1, input2, output1 : primary_io;
w1 : a_wire GENERIC MAP (1)
PORT MAP (input1, nand1);
w2 : a_wire GENERIC MAP (2)
PORT MAP (input2, nand1);
w3 : a_wire GENERIC MAP (3)
PORT MAP (nand1, output1);

The list containing the flip-flop value differences are kept internal to each flip-flop. This is a linked list and grows hen faults propagate to flip-flops, and shrinks when faults are detected, or good circuit values reach flip-flops of a faulty circuit. This list has been implemented as an ACCESS type shared variable local to flip-flop models.

ENTITY circuit_analyzer IS
GENERIC (total_wires : NATURAL);
PORT (inputs : OUT qit_vector;
outputs : IN qit_veqtor);
END circuit_analyzer;
ARCHITECTURE behav OF circuit_analyzer IS
BEGIN
PROCESS . . .
BEGIN
read_faultlist();
WHILE NOT ENDFILE (test_patterns) LOOP
READ (test_vector);
-- Simulate good circuit first
inputs <= test_vector;
fault_type <= no_fault;
WAIT FOR simulation of circuit;
good_outputs := outputs;
WHILE faults exist in fault list LOOP
inject fault;
WAIT FOR simulation of the circuit;
IF output /= good_outputs THEN
fault is detected, remove it;
ELSE
fault is still not detected;
END IF;
END LOOP;
END LOOP;
calculate fault coverage and generate report;
WAIT;
END PROCESS;
END behav;

In our fault simulator, applying test vectors, analyzing output response, removing detected faults from fault list and reporting the final fault coverage are done by a component called circuit analyzer. The pseudo code of this component is shown in Figure 8. The architecture of this component uses a single process statement. In this process, the fault list that may be the output of a fault collapsing program is initially read from an external input file. Then for each undetected fault, the corresponding bad machine will be simulated. At each time frame, if the value of any primary output signal of the bad machine is different from that of the good machine, the fault is detected and will be removed from fault list. Otherwise it will remain in the fault list to be simulated with other test vectors. After simulation of all test vectors the fault coverage and undetected faults will be reported.

Table 1 shows the results of fault simulation for several circuits of the ISCAS89 sequential benchmarks. The circuits are simulated with random test vectors and the results are compared with those of the COMBINED[7] fault simulator. This table shows that the results are comparable with those of a concurrent fault simulator. The simulation time, however, is substantially more with VHDL models using a commercial VHDL simulator.

This paper presented VHDL models for fault simulation of synchronous sequential circuits. These models are based on a novel method that has better performance than conventional methods. Obviously this performance improvement does not cause VHDL models to simulate as efficient as conventional fault simulators. However, the goal here has been to illustrate that a standard VHDL simulator can be used for fault simulation and adapt a technique for this purpose that will minimize the performance penalty. The use of a VHDL netlist that can be used for simulation, test generation and fault simulation in an integrated VHDL based design environment, and the use of the same VHDL simulation program for all such applications is the main intention of this and other works on VHDL testing by our research group.

For this scheme of VHDL fault simulation to be of practical use, standard file formats for test vectors and fault lists must be developed for better test data exchange between various applications. A parallel fault simulation based on this scheme will greatly improve the simulation speed. Also, to improve the simulation speed, faults should be ordered such that succeeding faults injected in the circuit under test are in the same area of the circuit. This way circuit activities between application of one fault to the next will be minimized.

[1] T. M. Niermann, Wu-Tung Cheng, and Janak H. Patel, "PROOFS: A Fast, Memory-Efficient Sequential Circuit Fault Simulator," in IEEE Trans. Computer-Aided Design, Vol. 2, No 2, pp. 198-207, Feb. 1992.

[2] H. K. Lee and D. S. Ha, "New Methods of Improving Parallel Fault Simulation in Synchronous Sequential Circuits," in Proc. Int. Conf. on Computer Aided Design, pp. 10-17, Oct., 1993.

[3] E. G. Ulrich and T. G. Baker, "Concurrent Simulation of Nearly Identical Digital Networks," Computer, Vol. 7, No. 4, pp. 39-44, April, 1974.

[4] W. T. Cheng and M. L.Yu, "Differential fault simulation -- A new method using minimal memory," in Proc. 26th Design Automation Conference., pp. 424-428, June, 1989.

[5] Z. Navabi, VHDL: Analysis and Modeling of Digital Systems, McGraw-Hill Publishing, New York, 1993.

[6] Z. Navabi, N. Cooray and R. Liyanage, "Using VHDL in Parallel Fault Simulation," in Proc. scs. Int. Conf. on simulation in Engineering Education, January 17-20, 1993, Vol. C-25, pp. 198-203

[7] M. Mojtahedi and W. Geisselhardt, "New Methods for Parallel Pattern Fast Fault Simulation for Synchronous Sequential Circuits," in Proc. Int. Conf. in Computer Aided Design, pp. 2-5, 1993.

[8] F. Berglez, D. Bryan, and K. Kozminski, "Combinational Profiles of Sequential Benchmark Circuits," in Proc. Int. Symp. on Circuits and Systems, May 1989, pp. 1929-1934.