D Algorithm Notes
D Algorithm Notes
Let us assume that we choose the fault g node which has got stuck at
0.
Assign the inputs to gate 2 to generate the fault i.e d=0 and e=0
Terminologies in D Algorithm
1. Singular cover
2. D intersection
3. Primitive D cube for a fault ( pdcf)
4. Propagation D cubes ( pdc)
Singular cover: It is actually nothing but a truth table which is written in a
slightly compact form.
A
SC of a NOR gate
A
We consider that one of each nodes will take one of the above values
X is dont care
D is fault ( under the faulty condition it has one value and under non faulty
condition it has a different value)
1 under faulty and 0 under non faulty
D is the compliment.
The way the D intersection works is we can derive the value of a node by
looking at , so one value might be coming , columns corresponds to one
value and rows corresponds to the other value.
0 0 is 0
1 0 D
Intersection
0 n0=0nx=xn0=0
1n1=1nx=xn1=1
Xnx=x
1n0=D
0n1=D
Find out the true condition value for the nor gate and that would be XX0
and intersec that to a false condition value for the nor gate where it
becomes 1 since it has stuck at 1 so 001 and when we do intersection for
both we get it as 00D
Similarly for the output stuck at 1 we get the pdcf as
Propagation D cubes:
PDC consists of a table for each circuit element which has entries for
propagating faults on any one of its input to the output.
To generate PDC entry corresponding to any one column, D intersect any
two rows of SC which have opposite values (0 and 1) in that column.
There can be multiple rows for one column
Expalination
Take a singular cover of an AND gate which is shown below, What I need
is, if there is a fault appears at input a, then I should be able to propagate to
the output. Take the D intersection of the 1st row and the last row and if
there is a fault appears at input b then take 2nd row and last row.
Choose a fault say g s-a-0. Choose pdcf of gate 2 for generating this fault
There are 9 nodes which defines certain values.
Choose pdcf for gate 2
We get 00D
Now I have to do D drive , the path could be 2, 3 and then 4.
As far as this particular d cube is considered all the remaining values are
dont care.
Pdc 3 ( XXX001DDX)
PDC for or gate is
0DD
D0D
Since the value of h is D I can write the first row from the above as 0 DD
I get the value as shown below
Pdc4 (0XX001DDD)
Looking at the output I will be coming to know whether the fault is present
or not.
I still dont have the values of b and c so we need to consider the values of b
and c as well. There is an inconsistency, so we need to do backtracing.
Perform Consistency:
(0XX001DDX)---Actual pdc4
(X11XX1XXX) after backtracing
The whole algorithm is all about propagating D to the output and we need
to sense it.