An ATPG algorithm based on a special class of BDD models, called Structurally Synthesized BDDs (SSBDD), is presented. Experimental results show that the novel test generation approach provides a remarkable speed-up in comparison with classical gate-oriente
Feasibility of Structurally Synthesized BDD Models for Test Generation
Jaan Raik Raimund Ubar Tallinn Technical University Department of Computer Engineering
EE0026 Tallinn, Estonia
Abstract
An ATPG algorithm based on a special class of BDD models, called Structurally Synthesized BDDs (SSBDD), is presented. Experimental results show that the novel test generation ap-proach provides a remarkable speed-up in comparison with classical gate-oriented methods. In addition, SSBDDs offer a more generalized view to the test generation problem.
1. Introduction
Most of the known test generation algorithms are implementing procedures that operate on the model of logic gates. On one hand, the use of logic gates as a design model seems intuitive, on the other hand, however, the approach has some drawbacks. One of the drawbacks is the lack of generality . While operating with gate-level models it is necessary to distinguish between different types of gates. In most of the procedures of test genera-tion an activity corresponding to a specific gate type is taken. This results in increasing complexity of the procedure descrip-tions and the loss of operation speed. The other drawback of using gate-level representations lies in large number of model primitives (gates) in the model.
In current paper, a novel approach that is aimed at overcoming the above drawbacks is presented. The approach is based on a model of a special class of Binary Decision Diagrams (BDD) [1], called Structurally Synthesized BDDs (SSBDD). SSBDDs were introduced for test generation for the first time in 1976 in [2] (originally referred to as structural alternative graphs). Un-like in traditional BDDs, which represent the circuit function only, in SSBDDs the structural information is preserved. This feature makes SSBDD models suitable for test generation. In addition, SSBDDs represent the circuit in a more compact form than do logic gates.
In previous approaches, fault collapsing techniques have been proposed to minimize the number of targeted faults. Fault simu-lation for fanout stems has been used in [3,4]. Giraldi et al. [5] implement BDDs for identifying equivalent search states during test generation. However, none of the above mentioned methods have neglected the basic gate-level representat-ion. In [6, 7], complete BDDs are computed for the good and faulty machines and test patterns are generated by traversing or composing the BDDs. In our approach, BDDs are synthesized once and for the fault-free circuit only. Furthermore, the worst case complexity for generat-ing SSBDDs is linear in respect to the number of logic gates, while it is exponential for BDDs.
2. SSBDD Representations
Figure 1 Combinational Circuit and Its SSBDD An SSBDD that represents a Boolean function is a directed noncyclic graph with a single root node, where all nonterminal nodes are labeled by (inverted or non-inverted) Boolean vari-ables and always have exactly two successor-nodes, whereas terminal nodes are labeled by constants 0 or 1. For all nonter-minal nodes, a one-to-one correspondence exists between values of the node variable and successors of the node. This correspondence is determined by the Boolean function repre-sented by the graph.
Let us denote the variable, which labels node m by x(m). We say that a value of the node variable activates the node output branch. According to the value of x(m), one of two output branches of m will be activated. A path in an SSBDD is sayed to be activated if all the branches that form this path are acti-vated. An SSBDD is called activated to value 0 (or 1) if there exists an activated path that includes both the root node and a terminal node labeled by constant 0 (or 1), respectively. SSBDD Gy with nodes labeled by variables x1, x2, ..., xn, repre-sents the Boolean function y = f(X) = f(x1, x2, ..., xn), if for each pattern of X, Gy will be activated to the value which is equal to y. We can consider a digital circuit as a netlist of fan-out-free regions (FFR), each of them represented by an SSBDD.
As an example, Figure 1 shows an SSBDD representation of a combinational circuit. For simplicity, values of variables on branches are omitted (by convention, the rightward branch corresponds to 1 and the downward branch to 0). In addition, terminal nodes with constants 0 and 1 are omitted (exiting the SSBDD rightwards corresponds to y = 1, and downwards to y = 0). The diagram contains 6 nodes whereas each of them represents a signal path in a circuit. The node variables in the SSBDD correspond to input branches of the circuit shown in Figure 1.

DECIDER A System for Hierarchical Test Pattern Generation_专业资料。A ...the netlists are converted into Structurally Synthesized BDD (SSBDD) models. ...
Test generation approaches that rely on functional fault models only do not ...datapath modules are transformed into Structurally Synthesized BDD 124 a Y 2...
current hierarchical test generation approach, gate-level descriptions of the datapath modules are transformed into Structurally Synthesized BDD (SSBDD) models. ...
current hierarchical test generation approach, gate-level descriptions of the datapath modules are transformed into Structurally Synthesized BDD (SSBDD) models. ...
Measures on Structurally Synthesized Binary Decision ...Test generation requires 1 Currently on the leave...models for macros are needed; 3) a generic ...
(DD) including traditional Binary DDs (BDD), Structurally Synthesized BDDs ...Ubar. Sequential Circuit Test Generation Using Decision Diagram Models. IEEE ...
Test generation approaches [5, 6] that rely on functional fault models ...circuit we use structurally synthesized BDDs (SSBDD) or alternative graphs [...
热门文档