D algorithm - Combinational ATPG in DFT (VLSI)

As the size of circuits is growing, the complexity of test pattern generation also increases. Hence manual test generation (being too cumbersome) is not a feasible method anymore. Therefore, we need the help of automatic test pattern generation (ATPG). But methods studied earlier in this DFT course like the path sensitization method is a very intuitive approach and can’t be developed into an algorithm for computer software. The D algorithm is just a derivative of the path sensitization method in a more systematic approach that is suitable for computer acceleration.

The D algorithm was developed by Roth at IBM in 1966 and was the first complete test pattern algorithm designed to be programmable on a computer. The D algorithm is a deterministic ATPG method for combinational circuits, guaranteed to find a test vector if one exists for detecting a fault. It uses cubical algebra for the automatic generation of tests.

Three types of cubes are considered:

Singular cube
Propagation D-cube (PDC)
Primitive D-cube of a fault (PDCF)

Before continuing into cubes, let us focus on an important topic, i.e. D-Algebra.

Contents

The D algebra

The D-algebra is a 5-value logic consisting of logic: 1, 0, D, D', X. The D stands for Discrepancy, as discussed in the path sensitization method.

Following algebraic rules are applicable in D algorithm for intersection:

0 ∩ 0 = 0 ∩ x = x ∩ 0 = 0

1 ∩ 1 = 1 ∩ x = x ∩ 1 = 1

x ∩ x = x

1 ∩ 0 = D

0 ∩ 1 = D’

Note that intersection in D-algebra is quite different to what we are familiar with sets and relations in mathematics. They do not follow properties like commutativity or associativity.

Cubes

Singular Cover

Singular Cover (SC) of any logic gate is the compact form of truth-table. This is done using don’t cares (x). Following reduced truth table is the singular cover of an AND gate.

We know that, for an AND gate, the output is logic-1 only when both of its inputs are high. At the same time, the output is logic-0 for all the other cases where any of its input is low. The output of the AND gate is low for most of the cases. Hence, specifying separate columns for every possible input combinations becomes redundant. Therefore we merge the rows of AND gate and define the truth-table using don’t cares in a more condensed form.

Each row of a singular cover is termed as Singular Cube. The above singular cover of the AND gate has three singular cubes.

Primitive D-cube of a Fault

D-cubes represent the input-output behavior of the good and faulty circuits.

Primitive D-cube of a Fault (PDCF) is used to specify the minimum input conditions required at inputs of a gate to produce an error at its output. This is used for fault activation. PDCF can be derived from the intersection of singular covers of gates in faulty and non-faulty conditions having different outputs.

Example:

Here is an AND gate with s-a-0 fault at the output. To generate the PDCF, we first draw the truth table of the faulty and non-faulty circuit. Next, we derive the singular cover for faulty as well as non-faulty circuits.

For faulty AND gate, the output is always stuck-at-0 independent of its input; hence its singular cover has only one row with inputs (a, b) as don’t cares.

Now, we intersect the singular cubes of the non-faulty and faulty circuits. For PDCF we need to intersect only those columns for which output is different for non-faulty and faulty circuits. Since for faulty circuits, we only have one singular cube {x, x, 0}; we need to intersect it with a singular cube of the non-faulty circuit having the opposite output value (i.e. logic-1). The singular cube {1, 1, 1} perfectly fits this criterion.

{x, x, 0} ∩ {1, 1, 1} = {1 ∩ x, 1 ∩ x, 1 ∩ 0} = {1, 1, D}

Finally, PDCF of this faulty AND gate is {a, b, out} = {1, 1, D}. This is similar to fault excitation we did in the path sensitization method, albeit in a more structured approach.

Here, D is interpreted as being logic-1 if the circuit is fault-free and logic-0 if the fault is present. Notice the order in which the intersection is done! Always intersect as ⇒ singular-cube (non-faulty circuit) ∩ singular-cube (faulty circuit). The reverse will yield different results since the intersection is not commutative and hence will hamper the above interpretation we are trying to opt for.

Propagation D-cube

Propagation D-cubes (PDCs) of a gate causes the output of the gate to depend upon the minimum number of its specified inputs. It is used to propagate D or D’ from a specified input to the output. Propagation D-Cubes can be derived from the intersection of singular cubes of gates of opposite output values.

Example:

Here’s the truth table of an OR gate. To generate the PDC, we find the singular cover for the OR gate.

Now, we intersect the singular cubes of every possible combination(s) with opposite output values. Intersecting the singular cubes of row2 and row1, also row3 and row1 serves the purpose.

{1, x, 1} ∩ {0, 0, 0} = {1 ∩ 0, x ∩ 0, 1 ∩ 0} = {D’, 0, D’}

{x, 1, 1} ∩ {0, 0, 0} = {x ∩ 0, 1 ∩ 0, 1 ∩ 0} = {0, D’, D’}

a	b	out
D’	0	D’
0	D’	D’

In this case, the intersection doesn’t need any specific order. If we intersect in the other way, we obtain PDCs as {D, 0, D} and {0, D, D}.

Moreover, there is another option in which we intersect {1, 1, 1} with {0, 0, 0} of the truth table. This yields another possible PDC as {D, D, D} or {D', D', D'}. The following are the complete PDCs of an OR gate.

a	b	out
0	D	D
D	0	D
D	D	D
0	D’	D’
D’	0	D’
D’	D’	D’

This is very similar to forward propagation we did in the path sensitization method.

But then why are we learning it? These D-cubes tend to be much more inconvenient and tiresome for us as compared to path sensitization method. The answer is that we human beings have IQ, and hence we can solve methods like path sensitization intuitively. A computer doesn’t the necessary intelligence (yet). The D algorithm takes the creativity out of test generation and allows a computer to do it.