Backtracking
Backtracking is a technique for a sequence of alternatives to achieve a desired solution.
The goal of backtracking is to consider every possible combination to solve an optimization problem.
If a decision in the circuit causes an inconsistency, we need to backtrack to solve the circuit.
Backtracking means undoing the last decision and selecting another possibility to solve the problem. In this algorithm, every decision can be made only once in exactly that order.
This means either selecting another gate from one of the frontiers or deciding on inputs in another way.
Implications
The implication of the D algorithm is that unknown values in the input lines are determined with a well-known set of values.
Foward Implication
A determination of the output by known inputs values is implied.
Backward Implication
A determination of the input by known output value is implied.
In the D algorithm, we have two essential components:
By taking a look at the following part of a combinational circuit for which automatic test pattern generator is to be performed.
The blue gates are D-frontier while green gates are J-frontier.
D-frontier:
A set of gates whose output values is currently unknown, but have one or more D (or D’) as their inputs.
J-frontier:
A set of gates whose output values is assigned in this case the input values have not been decided yet.