The fault simulator is a 3-valued deductive simulator.   In a deductive simulator,
there is a fault list associated with every line. The basic step in deductive
simulation is to compute the  fault-free output value and the output fault-lists.
The computation of fault lists is called fault-list propagation.

\subsection{Design and implementation}


The most important point to be considered in a deductive fault simulator is
the representation of fault lists and fault-list propagation. Once the fault
list representation is decided upon, routines for list manipulations can be
easily written.

This particular implementation has the following features:
\begin{enumerate}
\item There is a fault list associated with every line. It is implemented as an
array of {\em integers}, with each {\em bit} associated with a line. If a fault on any 
line is present in the fault list, the particular bit in the fault list is set
to 1. Note that in a deductive simulator it is not necessary to store the actual
fault value of the line in the fault list. It is enough to know the presence
of a faulty line in a fault list. The actual fault can be determined by
observing the good value of the particular line.

\item Macros are defined which perform bitwise manipulation of lists. FUNION,
FINTERSECT, FCOMPLEMENT are the basic macros which implement union, intersection
and complementation of lists.

\item A levelizer routine first assigns levels to all the gates and output
fault lists are computed for gates at succeeding levels.

\item Routines are provided for generating various tests like {\em exhaustive,
random} and {\em weighted random}. The system also provides a link between
the test generator, described in an earlier chapter, and the fault simulator.
\end{enumerate}

Before going on to a detailed description of the algorithms, a brief overview
of the fault simulator is provided here.

There are three main tasks which the fault simulator performs
\begin{enumerate}
\item Initialisation
\item Test vector generation
\item Fault list propagation
\end{enumerate}

These tasks are explained in detail below:
\begin{enumerate}
\item During initialisation the circuit is levelized. All gates are assigned a level,
with primary inputs having level 0. The fault lists are initialised to have
a fault corresponding to that line itself. The logic values of all the lines are
set to {\em x}.

\item Depending upon the user choice, a set of test vectors is generated. The simulator
writes these vectors to a file and then reads them one by one and simulates them.
This test generation routines should not be confused with the D-algorithm based
test generator which a part of {\bf LTEST}. The D-algorithm based test generator
comes up with a test for a particular fault. The test generation routines here
create a set of {\em exhaustive}, {\em random} or {\em weighted random} for the
purpose of fault simulation.

\item The core of the simulator is fault list propagation. For every test vector, a 
logic simulation is first performed. For every gate $Z$, the output fault list
is computed as follows:
\\
Let $I$ be the set of inputs of gate $Z$ with controlling value $c$ and inversion $i$. Let $C$ be the set of inputs with value $c$.
\\

\hspace*{0.5in} {\bf if} $C = \phi$ {\bf then} $L_{Z} = \{\bigcup_{j \in I} L_{j}\} \; \bigcup \; \{Z
s\_a\_(c \oplus i\}$

\hspace{0.5in} {\bf else} $L_{Z} = \{\bigcap_{j \in C} L_{j}\} - \{\bigcup_{j \in I-C} L_{j}\}
\;  \bigcup \; \{Z s\_a\_(\overline{c} \oplus i\}$
\\

That is if, no input has value $c$, any fault effect on an input propagates to
the output. If some inputs have value $c$, only a fault that affects all the
inputs at $c$ without affecting any of the inputs at $\overline c$ propogates
to the output. In both cases the local fault at the output is added.
\end{enumerate}

\subsection{Fault simulator functions}

\subsubsection{Initialisation routines}

\begin{verbatim}
int compute_level(gate_index)
int gate_index;
\end{verbatim}
\begin{quotation}
This function returns the level of the gate specified by {\em gate\_index}. The 
level of the gate is one more than the maximum of the levels of the gates
feeding this gate.
\end{quotation}

\begin{verbatim}
levelize()
\end{verbatim}
\begin{quotation}
This function levelizes the circuit by calling {\em compute\_level(gate\_index)}
recursively. The level field of every gate is assigned an integer value.
\end{quotation}

\begin{verbatim}
ch_dest_gate_lcount(line_ind, gate_ind)
int line_ind, gate_ind;
\end{verbatim}
\begin{quotation}
This function changes the logic count of the gate {\em gate\_ind} as a result
of one of it's input lines, {\em line\_ind} changing it's value.
\end{quotation}

\begin{verbatim}
initialize_ckt()
\end{verbatim}
\begin{quotation}
This function initialises the circuit. It computes initial logic values, logic
counts and does some other book-keeping operations.
\end{quotation}
 
\begin{verbatim}
change_d_db()
\end{verbatim}
\begin{quotation}
This function changes any line values which are $d$ to 1 and $dbar$ to 0. This is
necessary when the fault simulator is used in conjunction with the test generator,
since the fault simulator recognises only 3 logic values.
\end{quotation}

\subsubsection{Test vector generation routines}


\begin{verbatim}
gen_exhaust_test()
\end{verbatim}
\begin{quotation}
This function creates all possible input vectors and writes them to a file 
named {\em exhaust}.
\end{quotation}

\begin{verbatim}
char* rand_vector(seed,sig_pr)
int *seed;
float sig_pr[];
\end{verbatim}
\begin{quotation}
This function returns a pointer to a string which is a random vector. The routine
uses the seed pointed to by {\em seed} and the input signal probabilities
specified by the array {\em sig\_pr}.
\end{quotation}

\begin{verbatim}
gen_random_test()
\end{verbatim}
\begin{quotation}
This function cretes  as many random vectors as specified by the user. It calls
function {\em rand\_vector(seed,sig\_pr)} for every vector. All the elements in
the array {\em sig\_pr} are initialised to 0.5 for truly random vectors. The 
vectors are writen to a file called {\em rand}.
\end{quotation}

\begin{verbatim}
gen_wtd_test()
\end{verbatim}
\begin{quotation}
This function creates weighted random vectors. The input signal probabilities are
assigned by the user. The vectors are written to a file named {\em wtd\_rand}.
\end{quotation}


\subsubsection{Fault propagation routines}

\begin{verbatim}
activate_faults()
\end{verbatim}
\begin{quotation}
This function initialises the fault lists. For every line, the bit in the fault list
corresponding to the line is set.
\end{quotation}

\begin{verbatim}
get_f_list(gate, f_list_c, f_list_nc)
int gate;
int f_list_c[MAXINTS], f_list_nc[MAXINTS];
\end{verbatim}
\begin{quotation}
This function computes the controlling and the non-controlling fault lists for
{\em gate}.
The steps in this function are:
\begin{enumerate}
\item Depending upon the type of {\em gate}, set controlling value, {\em c\_val}.
\item For every input $i$ of {\em gate}
\begin{enumerate}
\item If input value, {\em in\_val} = $X$, do nothing.
\item If {\em in\_val} = {\em c\_val} then compute $L_{i} \cap f\_list\_c$.
\item If {\em in\_val} $\neq$ {\em c\_val} then compute $L_{i} \cup f\_list\_nc$.
\end{enumerate}
\end{enumerate}

What this function effectively does is compute $\{\bigcup_{j \in I} L_{j}\},
\{\bigcap_{j \in C} L_{j}\}$ and $\{\bigcup_{j \in I-C} L_{j}\}$, where
$I$ is set of inputs and $C$ is set of inputs with controlling value.

\end{quotation}

\begin{verbatim}
fpropogate(gate)
int gate;
\end{verbatim}
\begin{quotation}
This function computes the output fault list of {\em gate}. It calls routine
{\em get\_f\_list(gate, f\_list\_c, f\_list\_nc)} to compute $\{\bigcup_{j \in I} L_{j}\}, \{\bigcap_{j \in C} L_{j}\}$ and $\{\bigcup_{j \in I-C} L_{j}\}$.
The steps are:
\begin{enumerate}
\item If {\em gate} is of type {\em inv}, $L_{Z} = L_{input} \: \bigcup \: L_{Z}$.
\item If {\em gate} is of type {\em buf}, for every output $j$, $L_{Z_{j}} = L_{input} \: \bigcup \: L_{Z_{j}}$.
\item If {\em gate} is of any other type:\\
       {\bf if} $C = \phi$ {\bf then} $L_{Z} = \{\bigcup_{j \in I} L_{j}\} \; \bigcup \; \{L_{Z}\}$\\
       {\bf else} $L_{Z} = \{\bigcap_{j \in C} L_{j}\} - \{\bigcup_{j \in I-C} L_{j}\} \; \bigcup \; \{L_{Z}\}$

\end{enumerate}
\end{quotation}


\begin{verbatim}
fault_sim()
\end{verbatim}
\begin{quotation}
This function performs output fault list propagation for every gate in the circuit.
The fault list corresponding to the primary output gates, is the list of
detected faults. It also prints the fault lists of the primary outputs which are the faults detected.
\end{quotation}


\subsubsection{Other functions}

\begin{verbatim}
drop_fault(linenum, sa_value)
int linenum, sa_value;
\end{verbatim}
\begin{quotation}
This function drops the fault, {\em line} stuck-at {\em sa\_value} from all
the fault lists. So the next test vector does not simulate these faults again.
\end{quotation}

In addition to the functions mentioned above, there are other functions which
do the job of reading in data and printing out the results. The code of these
functions is self-explanatory.


\subsection{An example program}

The following program is in the file {\em fault\_sim.c} in the {\em fsim}
directory.

\begin{verbatim}
void fault_sim()
{
  int count, gate_index, level;
  
   
  change_d_db();
  activate_faults();
  ckt_depth = levelize();

  for (level = 1; level < ckt_depth; level++)
    for (gate_index = 0; gate_index < first_pi; gate_index++)
      if (gate_list[gate_index].level == level)
        fpropogate(gate_index);
  print_det_faults();
}
\end{verbatim}

The function description is provided in the previous section.

 
