Scribd
Upload
3K views

D Algorithm Notes

The document describes the D-algorithm for fault diagnosis in digital circuits. It has three main steps: 1) generate a fault at a node by assigning inputs to produce the complement of the fault value, 2) propagate the fault to an output by choosing a path and assigning non-dominating input values at each gate, 3) backpropagate to determine a consistent set of input values. The key concepts are the primitive D-cube, which generates a fault, propagation D-cubes which propagate faults through gates, and the singular cover truth table. An example walks through applying the D-algorithm to generate a test vector to detect a stuck-at-0 fault at node g.

Uploaded by

mujju433
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3K views

D Algorithm Notes

The document describes the D-algorithm for fault diagnosis in digital circuits. It has three main steps: 1) generate a fault at a node by assigning inputs to produce the complement of the fault value, 2) propagate the fault to an output by choosing a path and assigning non-dominating input values at each gate, 3) backpropagate to determine a consistent set of input values. The key concepts are the primitive D-cube, which generates a fault, propagation D-cubes which propagate faults through gates, and the singular cover truth table. An example walks through applying the D-algorithm to generate a test vector to detect a stuck-at-0 fault at node g.

Uploaded by

mujju433
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 12

D- Algorithm

The D denotes discrepancy signal. The node which is used to generate or


propagate the fault is D
There are three main steps in the D Algorithm
1. To Generate the fault
2. Propagate the fault to one of the outputs ( called as Forward Drive or
D drive)
3. Back propagate to get consistent assignment for inputs and that is
called Backward drive or propagation)
We will see how it works
Step 1: We have to choose a node , not only node , we need to choose
the fault

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

We need to choose the inputs in such a manner so that it generates


the output which is complementary of the fault itself which is called
fault generation
We say that g is stuck at 0 so I need the output to be 1 in true
condition so in NOR gate what are the conditions
We will see here
Nor gate has an output of 1 only in one condition and that is both the
inputs should be 0 so d=0 and e=0
I will call the output g as D ,If the fault is present the output is 0 and
if the fault is not present it will be 1 so such a node I will call it as D
which is faulty.
Second step: Now I have to choose a path to be propagated to the
output.
The path I can choose is from gate 2, 3, 4
To propagate the path I need to choose the non dominating values
for the other inputs of a gate
I need to assign the input f as 1 so that the output will be D at the
output of gate 3.
At the output if we get D or D doesnt matter, what we need is
output to be sensitive to the fault.
F=1, a=0
3rd step: Consistency assignment or check. What happens is wherever
the gates for which I have assigned the output values but the input
value is not assigned, in this case for b and c I have not assigned the
value.
This is something called backtracing, where we have assigned the
value of f to be 1 but for b and c we have not assigned. The values
which satisfied for f to be 1 is only when b and c are 1
Now I know all the values, so the test vector could be (01100)

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

Once we know the truth table we can apply a D algorithm

SC of a NOR gate
A

D Intersection: When we are doing D algorithm we look at each of its


circuit nodes to be capable of taking 0,1,x,d,d

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

Primitive D cube of Fault (pdcf)


For generating a s-a-0 fault at node c, choose a SC row which gives an
output of 1 for the nor gate and intersect with (X,X,0), pdcf is (0,0,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.

So to illustrate what happens in D and D compliment , If we take a NAND


gate , we have
Again if I want to generate my PDC then for the fault a to be considered
then D 1 D( we need to take 1s 1st row and last row)
For b fault 1 D D

PDC for AND and NOR gate is shown below

Similarly we can do it for 3 input gate as well.


D Algorithm steps:
Choose a stuck at fault any of the nodes
Choose a pdcf for generating the fault
Choose an output and a path to the output and propagate the fault to the
output by choosing pdc for all circuit elements on the path ( D drive)
Use the SC of all unassigned circuit elements to arrive at a consistent set of
inputs ( back propagate or consistency check)

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.

So pdc for 3 i.e NAND gate is

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

Sc1( do the intersection for the above 2 values)


SC1 (011001DDD)
The values will be 01100, this is the test vector for the fault to be tested.

The whole algorithm is all about propagating D to the output and we need
to sense it.

You might also like