Automatic pattern generation or ATPG enables user to identify DFT faults faster. The speed of an ATPG process depends on the availability of suitable algorithm which can generate test patterns to identify faults. There are a few methods like Boolean difference & path sensitization as test pattern generator, but none of them are optimum enough to generate test patterns fast & accurate manner. One more parameter becomes very important when we consider the coverage of different types of faults; a good algorithm should provide not only accurate test patterns, but also should be able to target different types of faults with ease. So that is where we need specialized algorithms to enable user generate test patterns fast, accurate & with good coverage with different types of faults.
Introduction
D algorithm is based on the principle of path sensitization, where it is broadly carried out by following the 3 steps: Fault injection, Fault propagation & Backward propagation. In developing the algorithm, we can define a certain fault, which can be denoted by D, may take the value 1 during fault & 0 without a fault (or vice versa). Here, D’ is complement of the above-mentioned fault. so, naturally the injection, sensitization & observation of fault D, is the goal of D algorithm. But, D algorithm uses some equivalent steps to fault injection, fault propagation & Backward propagation:
D algorithm requires the understanding of some crucial terms before we go into actual steps of it. Now here we first understand them and then will apply them in some basic logic gates (like AOI, NAND, NOR). It is fundamental that these terms will be frequently used in the subsequent sections.
Algebraic rules, the D-algebra:
A variable in the world of D algorithm can hold 5 states namely, {0,1, D, D’,X}, we already have known first 4, and last one 'X' denotes a non-specified state. The following shows the allowed logical operations associated with a variable (D):
Please note here, the intersection in D-algebra is quite different to what we are familiar with sets and relations in mathematics also, they do not follow properties like commutativity or associativity.
Singular Cover:
Singular Cover (SC) of any logic gate is a compact representation of truth-table (TT), which is done using don’t cares (x). For example, consider the TT of an AND gate, which can be write in a form as:
Primitive D-cube of a Fault:
Primitive D-cube of a Fault (PDCF) is used to specify the minimum input conditions required at the inputs of a logic gate which can produce an error (can be considered as a fault) at the output of the gate, the fault site. It means that, for a given output to be defective, what are the input combinations can be given at the logic gate input. Which also can be implied as the required input to a logic which activates a fault a required site. Good thing is that a PDCF can be derived from the intersection of singular covers of the concerned logic gates based on the faulty and non-faulty conditions. Let's try to understand with an example, consider an OR gate and a SA0 fault at its output:
Propagation D-cube:
Propagation D-cubes (PDCs) of a logic gate causes the output of the gate to depend upon the minimum number of its specified inputs. It is used to propagate a certain D (or D’) from one of the specified input to the output of a logic gate. The propagation D-Cubes can be derived from the intersection of singular cubes of gates of opposite output values. The below example explains the concept of
PDC of a logical gate.
Test Cubes:
A test cube represents partially specified signal values at various nodes in the circuit during each step of the test generation process, it contain primary inputs as well as internal nodes. A test cube at ATPG step n is denoted by TC(n) and it states the logical values in different nodes of the circuit including inputs when a D algorithm ATPG process runs through various steps. After every successive step in ATPG, we need to intersect test- cubes to obtain the unified test cube which are useful for forward & backward propagation. Here the intersection is a little different from the former one we seen in PDC & PDCF section; In this intersection, two bits can be only intersected if their logic values are not conflicting. Intersection rule: 0 ∩ 0 = 0, 1 ∩ x = 1, x ∩ D’ = D’, x ∩ D = D, 1 ∩
0 = # (conflicting & can’t be written)
Frontiers:
Frontiers denotes some section of a given circuit. Based on where exactly the section was made, we divide them in the following types.
• D-frontier: A set of gates whose output value is currently unknown, but have one or more D (or D’) at their inputs, if it contains multiple gates the algorithm branches into multiple lines
• J-frontier: A set of gates whose output value is assigned, but input values have not been decided yet.
The below image depicts the idea of D & J frontiers.
D-Algorithm steps:
Step 1:
Generate a PDCF for the given fault for a certain Gate under test, this is also known as fault activation.
Step 2:
Drive the D (or D’) from the output of the gate under test to an output of the circuit by successively intersecting the current test cube (TC(n)) with the propagation D-cubes (PDC) of successive gates. The intersection of a test cube with the propagation D-cube of a successor gate results in another test cube TC(n+1). This process is also known as D-drive or forward propagation or D-frontier
Step 3:
Justify the internal line values by driving back towards the inputs of the circuit, assigning input values to the gates so that a consistent set of circuit input values may be obtained, this process is known as justification of J-frontiers or backpropagation, intersecting the current test cube (TC(n)) with the appropriate singular cube of Singular cover (PDC) of previous gates
Step 4:
If any conflict occurs in justification, backtrack to previous steps
The following flowchart gives a detailed view of D-algorithm steps:
Example of D-algorithm for a Fan out free circuit:
Let us consider the following circuit & apply D-algorithm to find out the pattern to detect a SA0 fault in the designated position:
Note: The faulty node doesn’t fall at the Fan out of any previous circuit, if it is not a fanout Free circuit we have to incorporate additional step of satisfying logical value at the fanout gate also
Step -1 to 3
Step - 4 to 6
Step - 7 to 10
Now we have found that the pattern required to observe the response at primary output x of a fault D (g/SA0) is:
{a, b, c, d, e, f} = {1,1,1,1,x,x}
Note that the f input doesn’t influence x output and hence it is assigned a don’t care x
Summary :
The D algorithm was the first complete test pattern algorithm designed to be programmable on a computer, it uses cubical algebra for the automatic generation of tests in every step, it is deterministic ATPG method for combinational circuits.
D algorithm is a complete ATPG algorithm; hence it guarantees to generate a pattern for a testable fault, this is one of the advantages. All the internal signals need to be assigned in the D algorithm, thus it has a huge search space. Therefore, it is a time-consuming and slow algorithm. Backtracking is required for consistency checks. Backtracking becomes much more difficult, especially for re-convergence fanout circuits. The algorithm heavily uses the PDCF, PDC & SC of logical gates, the reader is encouraged to calculate these for each of the below mentioned logic gates after learning the concepts and before trying out the algorithm: – AND, OR, NOT, NAND, NOR
