
The problem of test generation is divided into
three subproblems. The first is fault collapsing, to obtain a minimal test
set. During the fault collapsing process all dominating relations between
fault classes are found and a hierarchy is maintained. The test
generation process begins with a minimal set containing only dominated classes 
and a dominating class is added only
whena test for all its dominated faults cannot be found. Maintaining
these relations and keeping track of all the book keeping involved is the
responsibility of the second module. The third module is the test generation
module, which, when given a fault, tries to find a test vector for it. This
module is an implementation of the D algorithm.

\subsection{Fault collapsing}

First the fault collapsing process is described - how equivalence classes are
built and how dominating relations are established. Then the model
used for the dominating hierarchy and the way this model is implemented is
described.
Finally the algorithm used for fault collapsing and a description of all the functions involved is presented.

\subsubsection{Building the equivalence hierarchy}

The fault collapsing process is based on the local equivalence and dominating
relations between input and output faults of a gate. For the five gate types
{\em AND, OR, INV, NAND, NOR,} these relations are easily determined. Basically,
if $c$ denotes the controlling value of the gate and $i$ denotes the inversion 
value of the gate, then all input faults stuck
at $c$ are equivalent to the output stuck at $c \oplus i$ and an input stuck at
$\overline{c}$ is dominated by the output stuck at $\overline{c \oplus i}$.
For a {\em buffer},
which models a fanout point, there is no equivalence-dominance relation between
stem faults and branch faults. The same applies for an {\em XOR} gate, there is 
no equivalence-dominance relation between an input fault and an output fault.
Therefore, the {\em buffer} and {\em XOR} outputs will be called
{\em stop lines} and the {\em buffer} and {\em XOR} inputs will be called
{\em start lines}.

This leads us to the following observations
\begin{enumerate}
\item The process of fault collapsing is an inherent {\em backward} procedure
on the circuit graph, i.e. you begin with the primary outputs and start lines,
and advance,
backwards, to the primary inputs.
\item As long as the output fault is equivalent to all corresponding input 
faults, you add
the input faults to the list and continue the process with these faults.
\item When the output fault dominates an input fault, the input fault is
the first element of a new equivalence class. This new class will not include
any other fault on the input lines of the gate.
\item An equivalence class has just one dominating class, while it can dominate
more than one class. The second part is trivial. The first follows from the 
construction process. Faults are added to the class only when they are input
faults equivalent to the output fault. Since a gate has just one output, there 
is no fault that can dominate these additional faults.
\item When a stop line is reached, no additional
faults can be added to the class and no dominance relation exists between the
fault and the corresponding start line faults.
\end{enumerate}

As a result of these observations, the collapsing strategy is to start with an
initial representative list of all primary output faults and start line
faults. These are all representatives of different equivalence classes. This
initial list is constructed by the parser. For each
representative, a backward search for equivalent faults is initiated. When a
dominated fault is found, since it represents a new equivalence class, it is
added to the list of representatives. The process ends when the representative 
list is emptied.

\subsubsection{Modeling and representing the equivalence hierarchy}

To represent the equivalence hierarchy a {\em directed acyclic graph} is used.
The nodes of the graph are the equivalence classes and an edge exists from node
$i$ to node $j$ if and only if class $i$ is dominated by class $j$. Thus, in
the beginning of the test generation process, the {\em in-degree} of a node is
the number of classes it dominates. The {\em out-degree} of each node is one, 
since a class can be dominated by just one other class.
The initial fault list consists of all 
classes whose {\em in-degree} is zero. When a test is found for a class, all
the faults in the class, and all the faults in all the dominating classes of
that class, can be tested for, thus, the original class
and all the nodes reachable from the original class can be erased from the graph. When 
a test for a class cannot be generated, the class node and its outgoing edge from the
graph is erased. This decreases by one the {\em in-degree} of the dominating class.
When the {\em in-degree} of a dominating class is zero, it means that a test for all its dominated classes cannot be generated, hence, to catch the class, an attempt to generate a test for it must be made. Thus, the list of faults always consists of
all nodes with an {\em in-degree} of zero.

In implementing this model care must be taken for
\begin{enumerate}
\item Representing all equivalence classes.
\item Representing all dominance relations.
\item Be able to eliminate classes from being considered for test generation.
\item For each dominating class, keep track of the number of dominated classes
still begin considered for (possible) test generation.
\end{enumerate}

Only one table is used to represent all the information needed. Each column of the 
table represents a line, where, obviously, column $i$ represents line $i$.
The table has eight rows.

Row $0$ ($1$) contains a name of a fault that is equivalent to line $i$ being 
stuck at zero (one). Thus, each equivalent class is represented as a cyclic
list. Starting at one fault and following the pointers will carry us through
all the equivalent faults of the initial fault.

Row $2$ ($3$) contains the name of the fault that is the representative of the
class to which line $i$ stuck at zero (one) belongs to.

If line $i$ stuck at zero (one) is the representative of its equivalent class,
then row $4$ $(5)$ contains the name of the fault that dominates the equivalence
class. Otherwise, this field is -1. If there is no dominating fault 
for the class then this entry is -1.

Row $6$ $(7)$ is the count of the number of dominated fault classes still 
(possibly) considered for test generation. This field is only valid if
line $i$ stuck at zero (one) is the representative of its class. When a test
can not be generated for a dominated fault, this field is decreased. When a
test has been found for the class (either by test generation or by generating
a test for a dominated fault) the field is changed to -1 and we traverse the
path reachable from the node, changing all counters to -1 until either the
path ends or a negative counter is reached (meaning this class is already
caught by some other vector or vectors).

\subsubsection{The fault collapsing algorithm}

The algorithm maintains four lists. The first, {\em equivalence\_reps}, is a 
list of equivalence class
representatives. The second, {\em equivalence\_list} is a list of equivalent
faults that have not been processed, i.e. tested for equivalence or
dominance with their corresponding input faults or for being stop lines.
The third, {\em fault\_list}, is a list of representatives for non-dominating
fault classes, i.e. classes in the initial minimal fault list. The fourth list,
{\em dominant\_list}, is a list of all the dominating classes.

The algorithm also has two special fault statuses. {\em first} is the first
fault in a class which is the class representative. When processing a class,
{\em active} is the fault that is currently processed. A boolean flag,
{\em dominant}, is checked at the end of the class processing, to determine
whether it is a dominating class or not. Other variables used are $f$, the 
fault type, {\em site}, the fault site, {\em source}, the source gate of the
fault site, {\em c} and {\em i}, the controlling and inversion values of the
source gate.

To represent faults as integers we use the following formula. Line $i$ stuck
at zero is represented as $2i$ while line $i$ stuck at one is $2i+1$.

The algorithm goes as follows

\noindent
\begin{enumerate}
\item While the {\em equivalence\_reps} list is not empty
\begin{enumerate}
\item $active = -1$, {\em dominant = false}
\item Choose a fault from {\em equivalence\_reps}
\begin{enumerate}
\item Add the fault to {\em equivalence\_list}
\item Delete the fault from {\em equivalence\_reps}
\item If the fault is stuck at $f$ and the line is $j$, $first = 2j+f$.
\item The representative of line $j$ stuck at $f$ is {\em first}, the
stuck at $f$ dominated count of line $j$ is 0.
\end{enumerate}
\item While {\em equivalence\_list} is not empty
\begin{enumerate}
\item Choose a fault from {\em equivalence\_list}.
\item If the fault is line $j$ stuck at $f$
\begin{enumerate}
\item $equivalence\_table[f][j] = active$
\item $active = 2j+f$
\item $equivalence\_table[4+f][j] = first$
\end{enumerate}
\item If line $j$ is a primary input, a buffer output or a {\em XOR} output,
do nothing.
\item If line $j$ is an inverter output, add the inverter input stuck at $1-f$
to {\em equivalence\_list}.
\item If $f = c \oplus i$, add all input lines stuck at $c$ to 
{\em equivalence\_list}
\item If $f = \overline {c \oplus i}$ 
\begin{enumerate}
\item Add all input lines stuck at $\overline {c}$ to {\em equivalence\_reps}.
\item {\em dominant = true}.
\item For each input line $k$, $equivalence\_table[2+\bar{c}][k] = active$
(meaning the current equivalence class dominates the equivalence classes of the
input lines stuck at $\bar{c}$).
\item $f = first \pmod {2}$, $line = (first - f) / 2$, 
$equivalence\_table[6+f][line] += number\_of\_inputs$. 
\end{enumerate}
\end{enumerate}

\item $f = first \pmod {2}$, $line = (first - f) / 2$, 
$equivalence\_table[f][line] = active$. 
\item If $dominant == true$ add {\em first} to {\em dominant\_list}, else 
add {\em first} to {\em fault\_list}.
\end{enumerate}
\end{enumerate}

\subsubsection{The fault collapsing functions}

\begin{verbatim}
add_to_dom_list(fault,line)
int fault , line ;
\end{verbatim}
\begin{quotation}
Adds a new element to {\em dominant\_list}. {\em fault} is the fault type,
{\em line} is the fault site.
\end{quotation}

\begin{verbatim}
add_to_eq_list(fault,line)
int fault , line ;
\end{verbatim}
\begin{quotation}
Adds a new element to {\em equivalence\_list}. {\em fault} is the fault type,
{\em line} is the fault site.
\end{quotation}

\begin{verbatim}
add_to_eq_reps(fault,line)
int fault , line ;
\end{verbatim}
\begin{quotation}
Adds a new element to {\em equivalence\_reps}. {\em fault} is the fault type,
{\em line} is the fault site.
\end{quotation}

\begin{verbatim}
add_to_f_list(fault,line)
int fault , line ;
\end{verbatim}
\begin{quotation}
Adds a new element to {\em fault\_list}. {\em fault} is the fault type,
{\em line} is the fault site.
\end{quotation}

\begin{verbatim}
fc()
\end{verbatim}
\begin{quotation}
This function constructs the equivalence table and the minimal fault list.
It assumes that the parser has already created a fault list which includes all
primary outputs and start lines. The function follows the
above fault collapsing algorithm to the letter.
\end{quotation}

\begin{verbatim}
fc_warn(num,site)
int num , site ;
\end{verbatim}
\begin{quotation}
Prints warning number {\em num} for site {\em site}. Currently there
is only one warning message saying that fault collapsing over gates of the
type of gate {\em site} is not implemented.
\end{quotation}

\begin{verbatim}
init_fc()
\end{verbatim}
\begin{quotation}
Initiates the lists (creates the first elements, sets the header pointer and 
current pointer to point to that element) {\em equivalence\_list, 
equivalence\_reps, dominant\_list} and {\em fault\_list}.
\end{quotation}

\begin{verbatim}
print_eq_tab()
\end{verbatim}
\begin{quotation}
This function is a useful debugging tool for {\em fc()}. It prints the
equivalence table of the circuit, transposed, i.e. it prints rows as columns
and columns as rows.
\end{quotation}

\begin{verbatim}
print_fc()
\end{verbatim}
\begin{quotation}
This function prints the equivalence classes in the fault list followed by
the equivalent classes in the dominant list.
\end{quotation}

\subsubsection{An example program}

The following program is in the file {\em collapse.c} in the {\em fc}
directory.

\begin{verbatim}
#include <stdio.h>

#include "global.h"
#include "global.g"

main(argc,argv)
int argc ;
char *argv[] ;
{ FILE *circuit ;
  int ok ;

  circuit = fopen(argv[1],"r") ;
  ok = parse(circuit) ;
  if (ok == success) 
    { fc() ;
      print_eq_tab() ;
      print_fc() ;
    }
}
\end{verbatim}

The program is called with the circuit description file as a parameter. It
opens the description file in read mode and calls {\em parse()} to parse the
circuit. If parsing is successful, it calls {\em fc()} to perform the fault
collapsing and then it calls two output functions. The first, 
{\em print\_eq\_table()}, prints the equivalence table. The second,
{\em print\_fc()}, prints the equivalence classes. It first prints the classes
on the fault list and then the classes on the dominant list.

\subsection{Creating a test set}

When creating a test set, we assume that fault collapsing has already been
done and the equivalence table and fault list are ready. All that is left
is to start taking faults off the fault list and trying to generate a test
for it. If test generation is successful, the equivalence class, and all 
generations of dominating classes are considered tested, and the dominating
count entries in the equivalence table must be changed accordingly. If test
generation fails, the class is added to a list of redundant faults and the
dominating count of the first generation dominating class is decreased. If
this count reaches zero, the class is added to the fault list. The list of
redundant faults is either a list of true redundant faults, if there are
no resource limits (e.g. time, number of backtracks) on the algorithm, or,
if there are resource limits,
pseudo redundant faults, i.e. faults the test generation algorithm was not
able to catch within the required limits.

The algorithm used is as follows

\noindent
While the {\em fault\_list} is not empty
\begin{enumerate}
\item Take a fault off the list.
\item Denoting the fault site as {\em site} and the stuck at value as $f$,
call {\em gen\_test(site, f)}.
\item If {\em gen\_test} returned {\em success}
\begin{enumerate}
\item While {\em site} stuck at $f$ is dominated
\begin{enumerate}
\item $site = dominating\_site$, $f = dominating\_f$.
\item Change dominating count of {\em site} stuck at $f$ to $-1$.
\end{enumerate}
\end{enumerate}
\item {\em gen\_test} returned {\em fail}
\begin{enumerate}
\item Add {\em site} stuck at $f$ to the redundant list.
\item If there is a dominating fault, decrement the dominating count of its
representative.
\item If the result is zero, add this dominating class representative to the 
fault list.
\end{enumerate}
\end{enumerate}

\subsubsection{Test set functions}

\begin{verbatim}
add_to_red_list(fault,line)
int fault , line ;
\end{verbatim}
\begin{quotation}
Adds line {\em line} stuck at {\em fault} to the redundant list.
\end{quotation}

\begin{verbatim}
caught(site,fault)
int site , fault ;
\end{verbatim}
\begin{quotation}
The function is called by fault\_sim() when it finds that line {\em site} stuck
at {\em fault} is also caught by the simulated input vector. It finds the
representative of the class the fault belongs to and proceeds to take it
off the fault list (if it is on the list) and mark all dominating classes
as also caught (by setting their dominating count to -1).

Function steps :
\begin{enumerate}
\item Find the representative fault of the equivalence class of line {\em site}
   stuck at {\em fault}.
\item If the representative is on the fault list, take it off.
\item While the representative is dominated
\begin{enumerate}
\item representative = dominating class representative
\item set dominating count to -1
\end{enumerate}
\end{enumerate}
\end{quotation}

\begin{verbatim}
int gen_test(site,flt)
int site , flt ;
\end{verbatim}
\begin{quotation}
The parameters to this function are an internal line name ({\em site}) and
a stuck at value ({\em flt}). The function initializes the D algorithm
variables, creates the implied actions list, does first-level excitation
of the fault and implies the fault through the destination gate of the faulty
line. If all this succeeds, it calls the D algorithm.

The function follows the following algorithm

\noindent
\begin{enumerate}
\item Call {\em init\_search()}.
\item Create the first element of the implied action list and set 
{\em imply\_ptr} to point to it (although we will never use this list for
backtracking, there is nowhere to backtrack to, subsequent functions use
the list, hence we must provide it).
\item Set {\em fault\_gate} to the destination gate of {\em site} (this is
necessary to prevent the output of the gate from being set during 
first-level justification).
\item Call {\em imply\_and\_check(site,1-flt,justify)} to first-level justify
(excite) the fault.
\item If {\em imply\_and\_check} returned {\em success}
\begin{enumerate}
\item Decrement the {\em logic\_count[1-flt]} field of the destination gate.
\item Increment the {\em logic\_count[x]} field of the destination gate.
\item Set {\em fault\_gate} to {\em number\_of\_gates}.
\item Call {\em imply\_and\_check(site,d+flt,imply)} to imply the fault value 
through the destination gate of the fault site.
\item If {\em imply\_and\_check} returned {\em success} call {\em d\_alg()} and
return its returned value, else return an error message (first drive failed).
\end{enumerate}
\item Else, return an error message (first level justification failed).
\end{enumerate}
\end{quotation}

\begin{verbatim}
gen_tests_init()
\end{verbatim}
\begin{quotation}
Creates the first element in the d-frontier and j-frontier list and sets the
header and current pointers of these lists ({\em d\_front\_hdr, d\_front\_last,
j\_front\_hdr, j\_front\_last}) to point to their respective element.
\end{quotation}

\begin{verbatim}
init_red_list()
\end{verbatim}
\begin{quotation}
Creates the first element in the redundant fault list with null fields.
It then sets the header pointer, {\em redundant\_hdr}, and current pointer
{\em redundant\_list}, to point to this element.
\end{quotation}

\begin{verbatim}
init_search()
\end{verbatim}
\begin{quotation}
Initializes all the data structures and fields associated with the D algorithm.
This function is called before beginning a search for a test vector with the
D algorithm.
\end{quotation}

\begin{verbatim}
gen_sim()
\end{verbatim}
\begin{quotation}
The function assumes fault collapsing has been done. It picks a fault from
the fault list and tries to generate a test for it. If a test is found, it
carries out fault simulation for the produced test vector. At the end of the 
fault simulation process, all faults that are caught by the test are taken off
the fault list and all the dominating calsses of these caught classes have
their dominating count set to -1.
\end{quotation}

\begin{verbatim}
test_set()
\end{verbatim}
\begin{quotation}
This function first calls {\em init\_red\_list()} and {\em gen\_tests\_init()}.
These functions initialize the redundant fault list and d-frontier and
j-frontier lists used during the D algorithm. After these initializations,
the function follows the above algorithm.
\end{quotation}

\subsubsection{An example program}

The example program can be found in the file {\em gen\_test\_set.c} in the
{\em test\_set} directory.

\begin{verbatim}

#include <stdio.h>

#include "/home/poisson3/ee658/global.h"
#include "/home/poisson3/ee658/global.g"

main(argc,argv)
int argc ;
char *argv[] ;
{ FILE *circuit ;
  int ok ;

  circuit = fopen(argv[1],"r") ;
  ok = parse(circuit) ;
  if (ok == success)
    { fc() ;
      test_set() ;
    }
}
\end{verbatim}

The program is called with the circuit description file as a parameter. It opens
the file and parses the circuit. If parsing succeeds, it calls {\em fc()}, to
create the fault classes and equivalence table, and then calls {\em test\_set}
to generate a test set for all non-redundant faults.

\subsection{The test generation algorithm}

The
test generation algorithm and its implementation is the heart of the test generation module. The algorithm used
to generate a test for a given fault is the D algorithm. In this section, 
first certain aspects of the design and implementation  are highlighted and 
 a full description of each function used in the algorithm is given.

\subsubsection{Design and strategy}

In any implementation of the D algorithm, the following points must be cared for
\begin{enumerate}
\item Maintaining a list of all gates which have a fault on their input and
their output value is not yet set. This list is known as the d-frontier.
\item Maintain a list of all lines whose value is not in conflict, but not yet
determined, by the input values to their source gate. This list is known as the
j-frontier.
\item For every decision made, keep track of all the changes in circuit line
values that resulted from that decision (a decision is the assignment of a value
to a line and the changes are the forward and backward implications of that
assignment). In case of backtracking, the decision is cancelled
and the changes that resulted from the decision must also be cancelled.
\item Keep track of the number of primary outputs with faulty values.
\end{enumerate}

From the above considerations, a number of functions must be written with the 
following goals
\begin{enumerate}
\item List manipulation routines.
\item Selection functions for choosing the next action, whether it will be
a line justification or an error propagation.
\item Imply and check routines for forward and backward implications. These
routines carry the implication process as far as possible while checking that 
they do not conflict with unjustified line values.
\item Line justification routines. For every line needing justification, we
must either set all free input lines to the non-controlling input value or set
one input to a controlling value. In the first case there is no decision
involved whereas in the second case we must choose which free input to set.
\item A {\em cancelling} routine that cancels all line assignments due to a 
cancelled decision.
\end{enumerate}

A natural way to implement the D algorithm is by recursion. The recursion however uses both global variables, 
accessible to all recursion levels, and local variables, which belong only to
one specific level. This enables the program not to make multiple copies of data
structures for each call, thus saving a lot of memory space and context switch
time, but it also makes cancelling decisions and restoring states more 
difficult, because it is not done automatically by the recursion mechanism.

The global structures are, besides the circuit structures ({\em gate\_list,
line\_list, fan\_table, ect.)}, the d-frontier and j-frontier lists with
their header and current pointers and counters and the counter for the
number of primary outputs with faulty values.

The most important local structure is the implied actions list and its
header and current pointers. This list contains all the line assignments
and all the line justifications that resulted from a line assignment
decision. When this decision is cancelled, all line assignments must be
cancelled (i.e. line values set back to $x$) and the resulting line 
justifications must be taken off the j-frontier.

An important aspect of every search procedure is pruning the search space
as much as possible. One pruning method
is implemented here. Assume the circuit is in a certain state,
$s$,
and we decide to drive a fault through some gate. At some point the recursive
call we made following that decision returns with a {\em fail} value. This
means that in state $s$, driving a fault through our gate can not
produce a test vector. We must cancel this drive and choose another action,
whether a drive or a line justification. In subsequent search stages, we might
reach a point where the fault at the input of our gate is propagated to the
output. Since we know that in state $s$, or any state that includes state $s$,
we can not find a test when the output of our gate is faulty, it is useless
to pursue this search path and we can return a {\em fail} value immediately.
To keep track of these gates, we use the {\em marked} field in the gate 
structure. If this field is {\em true}, any attempt to propagate a fault 
through this 
gate results in failure. The field is changed to {\em false}
only when we backtrack
from the level where the drive decision was first made. This backtrack will
change some previous decision, hence will change the state $s$.

Before going into a detailed description of the functions and algorithms, a brief top-down overview of our implementation is presented.

When a call is made to the D algorithm it first checks its lists. If a
fault has been propagated to a primary output and there are no more lines
in need of justification, it returns {\em success}. If there are no faults
at any primary output and the d-frontier is empty, it returns {\em fail}. If
a special error flag is true, it returns {\em fail}. In all other cases,
it must select an action. This action is either justifying the value of a line 
or driving a fault through a gate .

When justifying a line we distinguish between two cases. The first is when the
source gate of the line is of type {\em AND, OR, INV, NAND} or {\em NOR} and
the second is when the gate is of type {\em XOR}.

In the first case we first check whether the line value is $c \oplus i$ or
$\overline{c \oplus i}$, where $c$ is the controlling value and $i$ is the 
inversion value of the gate. When the output is $c \oplus i$ we must select
a free input and set it to $c$. When the output is $\overline{c \oplus i}$
we must set all free inputs to $\bar{c}$. In both cases we add all the 
assignments to the implied list and carry out backward implication for these
assignments. 

When the source gate is an {\em exclusive-OR} gate, since we allow only
two-input {\em XOR} gates, there are only two ways
to justify a line. A decision was made as to which of the two alternatives
to try first. After setting these line values, backward implication is carried 
out.

When doing backward implication, if a line receives a values of
$\overline{c \oplus i}$ ($c$ and $i$ are source gate dependent) all free input
lines to the source gate are set to $\bar{c}$ and the backward implication 
continues with these lines. If a line receives a value of $c \oplus i$ we
check how many free inputs there are. If there is only one, it is set to $c$
and the process continues. If there are more than one, a decision has to be
made as to which free input to set, hence the line is added to the j-frontier.
A special case arises when the source gate is a {\em BUF, INV} or {\em XOR}.
In case of a {\em buffer}, backward implication continues on the stem and
forward implication is carried out on all other branches. In case of an
{\em inverter}, the input line is assigned the complement of the output and
backward implication continues. In case of an {\em exclusive-OR}, if one
input is specified, backward implication continues with the free input. If both
inputs are free, the output line is placed on the j-frontier. All line 
assignments and placements on the j-frontier are also recorded on the 
implication list.

If all backward implication returned {\em success}, a recursive call to the 
D algorithm
is made. If it returns {\em success}, the calling level also returns 
{\em success}. If backward implication failed or if the recursive call returns 
{\em fail}, the decision is reversed, i.e. all
implied actions are cancelled and the line assignment is complemented (with
the appropriate backward implications carried out). If another decision can
be made to justify the output, the process continues as before. If all options
were tried and failed, the line is placed back on the j-frontier and 
backtracking occurs ({\em fail} is returned).

If the D algorithm decision was to drive a fault, we first set all free
gate inputs to the non controlling value and carry out backward implications.
If all backward implications return {\em success}, we imply the fault through
the gate. If forward implication returned {\em success}, we make a recursive 
call to the 
D algorithm. If this call returns {\em success}, the current level returns
{\em success}. If forward implication returned {\em fail} or if the recursive 
call returned {\em fail}, the gate is
{\em marked} and a call is made to the D algorithm. If this call succeeds, the
current level returns {\em success}. If the call fails, the gate is 
{\em unmarked} and we return {\em fail}.

During the {\em D drive}, the initial gate is taken off the d-frontier and
all the gates, on whose inputs the drive ended with faulty values, are added
to the front. The d-front counter and the faulty output counter are changed
accordingly.

Whenever backtracking occurs, we must cancel actions. All the actions due to
a decision were recorded in the implication list of the level in which the 
decision was made. Each element in the list is an action (imply or justify)
and a line name. If the action is imply, the line value is changed to $x$.
If the action is justify, the line is taken off the j-frontier (there is no
more need to justify its value, since the assignment was cancelled). 
When cancelling a line assignment, if the source gate has erroneous inputs,
then it is added to the d-frontier. 
If the cancelled assignment had an erroneous value and the destination gate 
has no other erroneous inputs, the gate is taken off the
d-frontier. This will restore the state of the 
d-frontier to its state before the decision was made. 

One last remark on the treatment of the j-frontier.
A line is placed on the front when the inputs to its source gate do not imply
its value. From the time the line was put on the front, to the time it is
taken off for justification, forward implications may have already justified
its value. Thus, before taking any action a check is made if the line value is
implied by the source gate inputs. If so, the D algorithm is called again.
If not, we proceed with the justification.

\subsubsection{D algorithm functions}

\begin{verbatim}
int add_to_d_front(gate)
int gate ;
\end{verbatim}
\begin{quotation}
If the gate is {\em marked}, the function returns {\em fail}. If the gate is a
primary output, the function increments the {\em d\_out\_count} counter and
returns {\em success}. Otherwise, the {\em d\_front\_count} counter is 
incremented, the gate is added to the d-frontier and the function returns
{\em success}.
\end{quotation}

\begin{verbatim}
add_to_imply_list(line,val,action)
int line , val , action ;
\end{verbatim}
\begin{quotation}
The function adds a new element to the implication list, stating that action
{\em action} was performed on line {\em line}. If the action is {\em imply},
the function changes the {\em value} field of the line structure in 
{\em line\_list[]} and changes the {\em logic\_count[]} of the destination gate
in {\em gate\_list[]}. If the action was {\em justify}, the function adds the
line to the j-frontier.
\end{quotation}

\begin{verbatim}
add_to_j_front(site)
int site ;
\end{verbatim}
\begin{quotation}
The function adds line {\em site} to the j-frontier, placing it at the end of
the list.
\end{quotation}

\begin{verbatim}
imply_rec choose_next_action()
\end{verbatim}
\begin{quotation}
The function returns a structure with two fields. The first is the {\em action}
field, which takes the value of either {\em justify} or {\em drive}. The second
is the {\em site} field which is an integer representing either a line or a 
gate, depending on whether the action is justify or drive. These fields are
the decision for the next D algorithm action. The selection strategy is that as 
long as there is no fault at a primary output, we drive. Once a fault reaches
a primary output, we start justifying. Whether we take an action from the
d-frontier or from the j-frontier, it is always the element at the end of the
list, thus it is assumed that any heuristic used to order the drives or
justifications is implemented by the insertion routines to these lists.
\end{quotation}

\begin{verbatim}
int compute_val(gate)
int gate ;
\end{verbatim}
\begin{quotation}
The function receives the name of a gate and returns the output value implied
by the input values. The computation is done by the count of each logic value
at the input.
\end{quotation}

\begin{verbatim}
d_alg()
\end{verbatim}
\begin{quotation}
The D algorithm function call. It checks the conditions for immediate success
or failure and if none of them are in effect, it initializes the implication 
list, selects an action and calls the function that carries out the selected
action. The function steps are as follows
\begin{enumerate}
\item If $d\_out\_count > 0$ and $j\_front\_count == 0$, return {\em success}.
\item If $d\_front\_count + d\_out\_count == 0$, return {\em fail}.
\item If $d\_error\_flag == true$, return {\em fail}.
\item Initialize the implication list with the local pointer {\em imply\_list}
and the global pointer {\em imply\_ptr} pointing to the first element.
\item Call {\em choose\_next\_action()} for the action and site of the next
decision.
\item If the decision was {\em justify}, call 
{\em just\_act(imply\_list,action.site)} and return its returned value.
\item If the action was {\em drive}, call
{\em drive\_act(imply\_list,action.site)} and return its returned value.
\end{enumerate}
\end{quotation}

\begin{verbatim}
int drive_act(imply_list,gate)
imply_rec *imply_list ;
int gate ;
\end{verbatim}
\begin{quotation}
In the current circuit state, i.e. line values, the function tries to drive a
fault through gate {\em gate}. If the drive succeeds, we make a recursive call
to {\em d\_alg()}. If this call returns {\em fail} or if the drive does not 
succeed (backward or
forward implication fail), we cancel all implied values, take the gate off
the d-frontier, and mark the gate. This mark will mean that in subsequent calls 
to {\em d\_alg()}, further down in the recursion hierarchy, any search path
driving a fault through {\em gate} is guaranteed failure, therefore there is no
reason to continue the path. After marking the gate we make a call to 
{\em d\_alg()}. If this call succeeds, we return {\em success}, if it fails,
we put {\em gate} back on the d-frontier, unmark it and backtrack.
The function steps are
\begin{enumerate}
\item According to the gate type, find $\bar{c}$ and $i$. If the gate is an 
{\em XOR} gate, arbitrarily set $\bar{c}$ and $i$ to $0$. 
\item First-level-justify setting all free inputs of {\em gate} to $\bar{c}$.
\item If successful, call {\em d\_alg()}.
\item If successful, imply the faulty output.
\item If successful, return {\em success}.
\item Undo all implications.
\item If the gate is of type {\em XOR}
\begin{enumerate}
\item Try the drive with $\bar{c}$ and $i$ set to $1$.
\item If successful, call {\em d\_alg()}.
\item If successful, return {\em success}.
\item Undo all implications.
\end{enumerate}
\item Take {\em gate} off the d-frontier and {\em mark} it.
\item Call {\em d\_alg()}.
\item If successful, return {\em success}.
\item {\em Unmark} the gate, place back on the d-frontier and return {\em fail}.
\end{enumerate}
\end{quotation}

\begin{verbatim}
int drive_fault(gate,dval,c,i)
int gate , dval , c , i ;
\end{verbatim}
\begin{quotation}
To drive a fault through a gate we have to set all free inputs to the 
non-controlling gate value (the $c$ parameter) and first-level-justify these
assignments. If they all succeed, we have to imply the resulting output
($dval \oplus i$). If this forwrd implication succeeds, we make a recursive call
to {\em d\_alg()} and return its result. The function steps are
\begin{enumerate}
\item Set all free inputs to the non-controlling value of the gate and
first-level-justify.
\item If all backward implications succeed
\begin{enumerate}
\item Remove the gate from the d-frontier.
\item Forward imply the gate output.
\item If successful
\begin{enumerate}
\item Call {\em d\_alg()}.
\item If successful, return {\em success}.
\end{enumerate}
\end{enumerate}
\item Return {\em fail}.
\end{enumerate}
\end{quotation}

\begin{verbatim}
imply_and_check(line,val,action)
int line , val , action ;
\end{verbatim}
\begin{quotation}
This function does forward and backward implications and checks for conflicts
that might result from these implications. If the {\em action} parameter is
{\em imply}, we do forward implication. If it is {\em justify}, we do
backward implication.

The function is called when a line value is either decided on or implied by
existing values. First thing we do is add the value to the circuit and to the
implication list. In forward implication we compute the value of the destination
gate as a result of the assignment. If the value is $x$, we do nothing. If the
current output is $x$ and the new value is not $x$, we make a recursive call
to {\em imply\_and\_check()} with the output line, the computed value and
{\em imply} as the {\em action} parameter. If the new value and the current
value are both not $x$ and they disagree, we detect a conflict (this can only
happen if the output line is on the j-frontier). If, during forward implication,
faults are either propagated or cancelled, we update the d-frontier. When
forward implication reaches a {\em buffer} input, we continue forward 
implication on all output lines. If forward implication reaches a gate where
all input lines but one are set, and the 
output needs justification, the value of the free input is implied, hence we
continue with backward implication on this line.

In backward implication we check whether we need a controlling or 
non-controlling value at the input. If we need a controlling value and if more
than one input is free, a decision must be made as to which input to set to the
controlling value. Therefore, we add the line to the j-frontier and we add the
line to the implication list with the {\em action} parameter set to 
{\em justify}. If we need a non-controlling value, we check whether one of
the inputs has a fault value. If not, we set all free inputs to the 
non-controlling value and continue with backward implication on these lines
(if there's a fault on one of the input lines, setting the free inputs to the
non-controlling value will propagate the fault, resulting in a conflict, since
all justification values are either $0$ or $1$). If backward implication is
done on a {\em buffer} branch, we continue with backward implication on the 
input line and forward implication on all other branches.

The procedure steps are as follows

\begin{enumerate}
\item Call {\em add\_to\_imply\_list(line,val,imply)}.
\item If $action == justify$
\begin{enumerate}
\item If the source gate is a primary input, return {\em success}.
\item If the source gate is a {\em buffer}
\begin{enumerate}
\item Continue backward implication on the input line.
\item If successful, do forward implication on all other output lines, otherwise
return {\em fail}.
\item If all forward implication succeed, return {\em success}, otherwise, 
return {\em fail}.
\end{enumerate}
\item If the source gate is an {\em inverter}, continue with backward
implication on the input line.
\item If the source gate is of type {\em AND, OR, NAND} or {\em NOR}
\begin{enumerate}
\item If the required input is $c$ and there is more than one free input line, 
add the line to the j-frontier and the implication list and return 
{\em success}.
\item If the required input is $c$ and there is just one free input, continue
backward implication on this input.
\item If there are faults on any of the input lines, return {\em fail}.
\item Set all free inputs to $\bar{c}$ and continue with backward implications.
\end{enumerate}
\item If the source gate is of type {\em XOR}
\begin{enumerate}
\item If both inputs are free, add the line to the j-frontier and implication
list and return {\em success}.
\item If there is a fault on one of the inputs, return {\em fail}.
\item Continue with backward implication on the one free input.
\end{enumerate}
\end{enumerate}
\item $action == imply$
\begin{enumerate}
\item If the destination gate is a {\em primary output}, return {\em success}.
\item If the destination gate is a {\em buffer}
\begin{enumerate}
\item Call {\em imply\_and\_check()} on all output branches.
\item If all return {\em success}, return {\em success}, else return {\em fail}.
\end{enumerate}
\item Compute the new output value for the destination gate.
\item If the value is $x$
\begin{enumerate}
\item If the new input was a fault, and there are no other faulty inputs, add
the gate to the d-frontier.
\item If the output is specified and there is only one free input left, 
continue with backward implication on the free input, and return the result.
\item Return {\em success}.
\end{enumerate}
\item The current output is not $x$
\begin{enumerate}
\item If the current output and the implied output agree, return {\em success}.
\item If the current output is a fault, it means that the output line is the
fault site. Therefore, if the implied value is the excitation value, i.e.
$1-fault$, return {\em success}.
\end{enumerate}
\item If the current output is $x$
\begin{enumerate}
\item If the gate was on the d-frontier, take it off.
\item Continue with forward implication on the output line.
\end{enumerate}
\item Return {\em fail} (both implied and current output values are not $x$ and 
they disagree).
\end{enumerate}
\end{enumerate}
\end{quotation}

\begin{verbatim}
imply_free_input(gate)
int gate ;
\end{verbatim}
\begin{quotation}
This function is called to check whether the output of {\em gate} is specified
and {\em gate} has just one free input. If both conditions do not exist, i.e.
either the output is free or more than one input is free, the function returns
{\em success}. If {\em gate} is not an {\em XOR} gate, than the free input is
set to $c$ and the function returns whatever value the backward implication
returns. If {\em gate} is an {\em XOR} gate, then if it has a fault on an
input, the function returns {\em fail}, otherwise it returns the value returned
by the backward implication.
\end{quotation}

\begin{verbatim}
int just_act(imply_list,line)
imply_rec *imply_list ;
int line ; 
\end{verbatim}
\begin{quotation}
The function receives a pointer to the first element of the implication list
and the name of the line needing justification. It first checks whether the line
value is already implied by the destination gate inputs. If so, it takes the
line off the j-frontier, recursively
calls {\em d\_alg()} again and returns the returned value. If the line value
is not implied by the gate inputs, it distinguishes between two cases. The first
is when the destination gate type is {\em AND, OR, NAND} or {\em NOR}, the
second is when the type is {\em XOR}. For the first case it calls
{\em just\_act\_gate(imply\_list,line,val)} and for the second case it calls
{\em just\_act\_xor(imply\_list,line,val)}, where {\em val} is the line value
(if that value is $d$ or $dbar$, val is $1$ or $0$ respectively). In both
cases the function returns the value returned by the called function.
\end{quotation}

\begin{verbatim}
int just_act_gate(imply_list,line,val)
imply_rec *imply_list ;
int line , val ;
\end{verbatim}
\begin{quotation}
The function receives the pointer to the implied actions list, a line name and 
a value that needs justification for that line. It chooses which of the free
inputs to set to the controlling value and does backward implications. If
successful, it calls {\em d\_alg()}. If {\em d\_alg()} returns {\em success},
the function also returns {\em success}. If backward implication failed, or if
{\em d\_alg()} failed, all implications are cancelled, the line is placed back
on the j-frontier, the chosen input line is
complemented and backward implication is carried out. If successful, a recursive
call to {\em d\_alg()} is made. If {\em d\_alg()} returns {\em success}, the
function returns success. If either backward implication or {\em d\_alg()}
return {\em fail}, we cancel implications, set the chosen input line to $x$
and return {\em fail}. The function steps are
\begin{enumerate}
\item Take the line off the j-frontier.
\item Depending on the gate type, find the controlling value $c$.
\item Choose a free input to set to $c$.
\item Set and first-level-justify this input.
\item If successful 
\begin{enumerate}
\item Call {\em d\_alg()}.
\item If successful, return {\em success}.
\end{enumerate}
\item Undo all implications.
\item Place the line back on the j-frontier.
\item Set and first-level-justify the chosen input to $\bar{c}$.
\item If successful
\begin{enumerate}
\item Call {\em d\_alg()}.
\item If successful, return {\em success}.
\end{enumerate}
\item Undo all implications and return {\em fail}.
\end{enumerate}
\end{quotation}

\begin{verbatim}
int just_act_xor(imply_list,line,val)
imply_rec *imply_list ;
int line , val ;
\end{verbatim}
\begin{quotation}
This function justifies the output of an {\em exclusive-OR} gate. Since we 
allow only two-input {\em XOR} gates in our circuits, if both inputs are free
we have two options with which to justify the output. If only one input is free,
we have just one way in which to justify the output. The function steps are
\begin{enumerate}
\item Take the line off the j-frontier.
\item If both inputs are free
\begin{enumerate}
\item Choose an assignment pair.
\item First-level-justify the pair.
\item If successful, call {\em d\_alg()}.
\item If successful, return {\em success}.
\item Undo all implications.
\item Change the assignment pair and first-level-justify.
\item If successful, call {\em d\_alg()}.
\item If successful, return {\em success}.
\item Undo all implications.
\item Add the line to the j-frontier and return {\em fail}.
\end{enumerate}
\item If one input is free
\begin{enumerate}
\item Assign the free input the required value and first-level-justify.
\item If successful, call {\em d\_alg()}.
\item If successful, return {\em success}.
\item Undo all implications.
\item Add the line to the j-frontier and return {\em fail}.
\end{enumerate}
\end{enumerate}
\end{quotation}

\begin{verbatim}
int just_and(gate)
int gate ;
\end{verbatim}
\begin{quotation}
The function receives the name of an {\em AND} gate and returns the name of
the line chosen to be set to the controlling value of the gate. The selection
process is done by going over the input lines as they appear in the fan table
and selecting the first input line with an $x$ value.
\end{quotation}

\begin{verbatim}
int just_nand(gate)
int gate ;
\end{verbatim}
\begin{quotation}
Same as above, for a {\em NAND} gate.
\end{quotation}

\begin{verbatim}
int just_nor(gate)
int gate ;
\end{verbatim}
\begin{quotation}
Same as above, for a {\em NOR} gate.
\end{quotation}

\begin{verbatim}
int just_or(gate)
int gate ;
\end{verbatim}
\begin{quotation}
Same as above, for an {\em OR} gate.
\end{quotation}

\begin{verbatim}
int just_xor(gate,val,t)
int gate , val , t ;
\end{verbatim}
\begin{quotation}
When trying to justify the output of a two-input {\em XOR} gate with two free
inputs, for each output value we have two possible input assignments. Our
strategy is to first try $(0,0)$ and then try $(1,1)$ when the output is $0$
and to first try $(0,1)$ and then $(1,0)$ when the output is $1$. Depending
on the value of $t$ (for {\em try}), we try to first-level-justify the $t-$th
option. If successful we return {\em success}, otherwise we return {\em fail}.
The function steps are
\begin{enumerate}
\item If $t == 1$
\begin{enumerate}
\item If $val == 0$
\begin{enumerate}
\item {\em imply\_and\_check()} $(0,0)$ as the input pair.
\item If successful return {\em success}, else return {\em fail}.
\end{enumerate}
\item $val == 1$
\begin{enumerate}
\item {\em imply\_and\_check()} $(0,1)$ as the input pair.
\item If successful return {\em success}, else return {\em fail}.
\end{enumerate}
\end{enumerate}
\item $t == 2$
\begin{enumerate}
\item If $val == 0$
\begin{enumerate}
\item {\em imply\_and\_check()} $(1,1)$ as the input pair.
\item If successful return {\em success}, else return {\em fail}.
\end{enumerate}
\item $val == 1$
\begin{enumerate}
\item {\em imply\_and\_check()} $(1,0)$ as the input pair.
\item If successful return {\em success}, else return {\em fail}.
\end{enumerate}
\end{enumerate}
\end{enumerate}
\end{quotation}

\begin{verbatim}
remove_from_d_front(gate)
int gate ;
\end{verbatim}
\begin{quotation}
If {\em gate} is a primary output, {\em d\_out\_count} is decremented. 
Otherwise, {\em d\_front\_count} is decremented and the d-frontier list is
scanned from the end backwards, until {\em gate} is found. It is then removed
from the list.
\end{quotation}

\begin{verbatim}
remove_from_j_front(line)
int line ;
\end{verbatim}
\begin{quotation}
The function receives the name of a line and removes it from the j-frontier.
It follows the list from the last element towards the first until it finds
the given line.
\end{quotation}

\begin{verbatim}
undo(imply_list)
imply_rec *imply_list ;
\end{verbatim}
\begin{quotation}
The purpose of this function is to undo all implication due to a cancelled
decision. This include setting all implied line values back to $x$, taking
all the implied line justifications off the j-frontier and restoring the state
of the d-frontier. At any one time, because there are many levels of recursion
and every level has its own implication list, there exists several such lists.
When adding implications to the list, we use a global variable that points to 
the end of the list of the current level. When backtracking is done, the
{\em current} level changes, and the global pointer no longer points to the
end of the {\em new} current list. Therefore we first assign the global pointer 
the 
value of the pointer to the first element, which is a local variable of the 
level. We then traverse the list to the last element, so that the {\em undoing}
is in the reverse order of the {\em doing}. Every element in the list has a
name of a line and the action performed on the line. If the action is 
{\em imply}, we reset the line value to $x$ and update the {\em logic\_count[]} 
of
the destination gate. If the assignment was a fault value, we add the source
gate to the d-frontier. If the destination gate has no other faulty inputs, 
we take it off the d-frontier. If the action is {\em justify}, we take the line
off the j-frontier. The function steps are
\begin{enumerate}
\item Set a pointer to the end of the implication list.
\item While the pointer points to a structure
\begin{enumerate}
\item If the action is {\em justify}, remove the line from the j-frontier.
\item Otherwise (the action is {\em imply})
\begin{enumerate}
\item Change the line value to $x$ and update the {\em logic\_count[]} of the 
destination gate.
\item If the value was $d$ or $dbar$
\begin{enumerate}
\item Add the source gate to the d-frontier.
\item If there is no other faulty input to the destination gate, take it off
the d-frontier.
\end{enumerate}
\end{enumerate}
\item Set the global pointer {\em imply\_ptr} to point to {\em imply\_list} and 
initialize this first structure.
\end{enumerate}
\end{enumerate}
\end{quotation}

Through most of the functions there are calls to special message routines.
These messages print either error messages, output messages or, if the 
{\em trace} or {\em step} flags are {\em true}, a step by step account of
all actions. For a description of these messages, see Appendix.

\subsubsection{An example program}

The example program is in the file {\em gen\_tests.c} in the {\em d\_alg}
directory.

\begin{verbatim}
#include <stdio.h>

#include "d_alg.h"
#include "d_alg.e"
#include "/home/poisson3/ee658/global.g"

main(argc,argv)
int argc ;
char *argv[] ;
{ FILE *circuit , *fault_list ;
  int ok ;

  circuit = fopen(argv[1],"r") ;
  fault_list = fopen(argv[2],"r") ;
  if (argc == 3) 
    { trace = false ;
      step = false ;
    }
  else 
    { if (strcmp(argv[3],"step") == 0) 
        { step = true ;
          trace = true ;
        }
      else
        if (strcmp(argv[3],"trace") == 0) trace = true ;
    }

  ok = parse(circuit) ;

  if (ok == success) gen_tests(fault_list) ;
}
\end{verbatim}

The program is called with two or three parameters. The first is the circuit
description file. The second contains a list of faults we want to generate tests
for. The third is optional. When it is used, it is either the {\em trace} or
{\em step} parameters, which cause the program to work in the selected mode.
After openeing both files in read mode and checking the third parameter, the
program parses the description file. If successful, it calls {\em gen\_tests()}
which generates tests for the faults in the fault list file.


