ATPG for Cancer Therapy - Logic Synthesis for Genetic Diseases - page 80

solver by assigning weights to the output states. For example, in the GF network
used in our experiments, the fault-free output Z 0 is assigned the highest weight (80)
and remaining output states are assigned decreasing weights (70, 60, 50, etc.) based
on increasing Hamming distance (1, 2, 3, etc.) from the fault-free output. We assume
that faulty states that have a larger Hamming-distance have a more pronounced cancer
proliferative effect.
Additionally, the selection of drugs to achieve the best output should use the least
number of drugs to minimize the side-effects on the patient. To incorporate this in the
WPMS solver, each drug that is not selected is given a weight of 1. The GF network
example has 6 drugs, thus if no drugs are selected, then the cumulative drug weight is
6. Likewise, if all drugs are selected, the drug weight is 0. Hence the highest weight
possible in our example is 86, corresponding to a fault free output using no drugs
(for an untestable fault).
Note that the output and drug weights are assigned in such a way as to avoid
the situation where a less-desirable output (with few drugs) is chosen over a higher
weight output (with more drugs). We assume that from a clinical standpoint, the
priority is to first produce the best possible output, and secondarily to use the fewest
drugs required for that output.
All faulty circuits with non-redundant faults from Case 1 are augmented with
the output and drug weights and simulated using WPMS. The WPMS solver will
implicitly and deterministically find the assignment of drugs that achieves the best
possible output and with the fewest drugs. The output values, selected drugs, and
highest weight of the fault+drug circuits are recorded and compared with the drug-
free circuits. An immediate result from this method is that a fault where the fault+drug
circuit which obtains its best output with zero drugs is in fact an untestable fault ,
wherein no drug combination can improve the output.
In general, several stuck-at faults can be simultaneously present in the circuit. A
circuit with n lines can have 3 n

1 possible stuck line combinations. This is because
each line can be in one of the three states: s-a-1, s-a-0, or fault-free. All combinations
(except one which has all lines in their fault-free state) are counted as faulty. In our
implementation, multiple stuck-at faults can easily be modeled for rectification, by
setting one or more lines to their faulty state.

−

5.3.4.3 Case 3: Fault Rectification with Minimal Drug Cost

In the previous case, all drugs are equal in terms of their weight. However, there may
be a situation where we would want to differentiate the drugs based on some cost
function based on characteristics such as price, number of side-effects, or ease of
availability. For example, two drugs with few side-effects may be more desirable than
one drug with many side-effects, if both drug selections produce the same output. As
such, in the presence of a particular faulty circuit and desired output, the problem is
determining a selection of drugs with lowest total cost.
Each drug that is not selected is given a weight proportional to its cost. In our
example, we use the number of side-effects as the drug's cost. All faulty circuits with