DECISION DIAGRAMS AND DIGITAL TEST
Raimund Ubar
Tallinn University of Technology, Tallinn, Estonia
INVITED PAPER MIDEM 2005 CONFERENCE 14.09.2005 - 16.09.20045, Bled, Slovenia
Key words: testing, testing of digital systems, decision diagrams, hierarciiical modeling, iiigh level decision diagrams, vector descision diagrams
Abstract: The most important question in testing today's compiex digitai systems is: how to improve the testing quality at continuously increasing complexities of systems? Two main trends can be observed: defect-orientation to increase the quality of testing, and high-level modelling to reduce the complexity problems of diagnostic analysis. Both trends can be joined in the hierarchical approach. Decision Diagrams (DD) serve as a good tool for hierarchical modelling and diagnostic analysis of digital systems. Traditional Binary Decision Diagrams are well known for worl<ing with logic level. New generalizations of BDDs in a form of High-Level DDs and Vector DDs as efficient tools for test generation and fault simulation of complex digital systems are discussed in the paper Finally, two examples of hierarchical test generation tools based on DDs together with corresponding experimental results are given.
Odločitveni diagrami in digitalno testiranje
Kjučne besede: testiranje, testiranje digitalnih sistemov, odločitveni diagrami, hierarhično modeliranje, odločitveni diagrami na višjem nivoju, vektorski odločitveni diagrami
Izvleček: Eno najpomembnejših današnjih vprašanj pri testiranju digitalnih sistemov je, kako izboljšati zanesljivost testiranja ob stalnem naraščanju kompleksnosti sistemov ? Opažamo dvae glavni smeri : eno, ki je usmerjena k odkrivanju napak in drugo, ki obsega modeliranje na višjem nivoju, kar zmanjša zapletenost diagnostične analize. Obe smeri lahko združimo v hierarhični pristop. Odločitveni diagrami ( DD ) služijo kot dobro orodje za hierarhično modeliranje in diagnostično analizo digitalnih sistemov. Tradicionalni binarni odločitveni diagrami ( BDD ) so dobro poznani pri delu z logičnimi nivoji. V prispevku obravnavamo nove posplošitve BDD v obliki DO na višjem nivoju in vektorske DD kot učinkovita orodja za tvorbo testov in simulacijo napak pri kompleksnih digitalnih sistemih. Na koncu podamo dva primera orodja za tvorbo hierarhičnih testov na osnovi DD skupaj z ustreznimi eksperimentalnimi rezultati
1. Introduction
Test generation for digital systems encompasses three activities: selecting a description method, developing a fault model and generating tests to detect the faults covered by the fault model. The efficiency of test generation (quality, speed) is highly depending on the description method and fault models which have been chosen.
As the complexity of digital systems continues to increase, the gate level test generation methods have become obsolete. other approaches based mainly on higher level functional and behavioral methods are gaining more popularity/1-3/. However, the trend towards higher level modelling moves us even more away from the real life of defects and, hence, from accuracy of testing. To handle adequately defects in deep-submicron technologies, new fault models and defect-oriented test methods should be used. On the other hand, the defect-orientation is increasing even more the complexity. To get out from the deadlock, the two opposite trends - high-level modelling and defect-ori-entation - should be combined into hierarchical approaches. The advantage of hierarchical approaches compared to high-level functional modelling lies in the possibility of constructing test plans on higher levels, and modelling faults on more detailed lower levels.
The drawback of traditional multi-level and hierarchical approaches to digital test lies in the need of different dedicated languages and models for different levels. Uniform methods for hierarchical diagnostic modelling of digital systems can be developed by using Decision Diagrams (DD) /4-9/. Binary DDs (BDD) have found already very broad applications in design and test on the logic level /4-5/. A special class of BDDs, Structurally Synthesized BDDs (SSBDD) can be used to represent gate-level structural faults directly in the graph model /6,7/. Recent research has shown that generalization of BDDs for higher levels provides a uniform model for both gate and RT level or even behavioral level test generation /8,9/.
The disadvantage of the traditional hierarchical test approaches is the use of gate-level stuck-at fault (SAF) model. It has been shown that high SAF coverage cannot quar-antee, high quality of testing /10/. The types of faults that can be observed in a real gate depend not only on the logic function of the gate, but also on its physical design. These facts are well known but usually, they have been ignored in engineering practice. In earlier works on layout-based test techniques /11,12/ a whole circuit having hundreds of gates was analysed as a single block. Such an approach is computationally expensive and highly impractical as a method of generating tests for real VLSI designs.
In this paper, we present, first, in Section 2 a method for mapping faults from lower levels to higher levels. For this purpose the concept of functional fault model is used. Thereafter, for hierarchical diagnostic modelling of digital systems, DDs are presented. In Section 3 SSBDDs are described for logic level test generation, and in Section 4 the use of higher level DDs fortest generation is discussed. Some experimental data are presented in Section 5 to illustrate the efficiency of the described hierarchical approach. Section 6 concludes the paper.
2. Functional fault model in hierarchical test
Consider a Boolean function y = / (x?, X2,..., Xn) implemented by an embedded component C in a digital circuit. Introduce a Boolean variable d for representing a given physical defect in the component, which may affect the value y by converting the Boolean function f into another faulty function y = f' (xt, X2, ..., Xn). Introduce for the block C a generic parametric function
y* = f*{x„x„...,x„d) = dfvdr
(1)
as a function of the defect variable d, which describes the behavior of the component simultaneously for both possible fault-free and faulty cases. The solutions of the Boolean differential equation
dd
(2)
describe the conditions which activate the defect d on a line y. The parametric modeling of a given defect d by equations (1) and (2) allows us to use the constraints W^ = 1, either in defect-oriented fault simulation to check if the condition (2) is fulfilled (i.e. if the defect d is tested by the given pattern), or in defect-oriented test generation to solve the equation (2) for testing the defect d. The conditions W^ allow to map physical defects to logic level. The constraint Vf' = 1 defines how a lower level fault d should be activated at a higher level to a given node y.
Table 1: Activating conditions for different defects
No	Defect	Conditions W
1	SAF Xk = 0	Xk=l
2	SAF Xk^ 1	Xk==0
3	Short between Xk and xi	xk=l,xi = 0
4	Exchange of lines Xk and xi	Xk= l,xi = 0, or Xk = 0, Xi = 1
5	Delay fault on the line Xk	Xk= l,x'k^O, or xk = 0,x'k = 1
Tabie 2: Library defect table for a complex gate AND2,2/N0R2
i	Fault di	Erroneous function	Input patterns tj															
			0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	B/C	not((B*C)*(A+D))				1								1	1	1		
2	B/D	not((B*D)''(A+C))				1								1	1		1	
3	B/N9	B*(not(A))	1	1	1					1	1	1	1					
4	B/Q	B*(not(C*D))	1	1	1						1	1	1		1	1	1	
5	B/VDD	not(A+(C*D))									1	1	1					
6	BA/SS	not(C*D)													1	1	1	
7	A/C	not((A*C)*(B+D))				1				1					1	1		
8	A/D	not((A*D)*(B+C))				1				1					1		1	
9	A/N9	A''(not(B))	1	1	1			1	1					1				
10	A/Q	A*(not(C*D))	1	1	1			1	1						1	1	1	
11	AA/DD	not(B+(C*D))						1	1									
12	C/N9	not(A+B+D)+(C*(not((A''B)+D)))		1				1			1	1						
13	C/Q	C*(not(A*B))	1	1		1		1		1	1	1		1				
14	CA/SS	not(A*B)				1				1				1				
15	D/N9	not(A+B+C)+(D*(not((A*B)+C)))			1				1		1		1					
16	D/Q	D*(not(A*B))	1		1	1			1	1	1		1	1				
17	N9/Q	not((A*B)+(B*C*D)+(A*C*D))				1												
18	N9A/DD	not((C*D)+(A*B*D)+(A*B*C))													1			
19	QA/DD	SA1 at Q				1				1				1	1	1	1	1
20	QA/SS	SAO at Q	1	1	1		1	1	1 1		1	1	1					
Some examples of the conditions V^ for different type of defects (wliere SAF is a particular extreme case) are given in Table 1 (here Xk is the observable variable, and x'k is the variable observed at the previous time moment).
The event of erroneous value of y can be described as dy = 1, where dy means Boolean differential. Afunctional fault representing a defect d can be described as a couple {dy, lA/^): at the presence of the physical level defect d, we will have an higher level erroneous signal tfy = 1 if the condition W^ = 1 is fulfilled.
The functional fault model {dy, W^) allows to use for test generation for any physical defect d traditional stuck-at fault test generators. To generate a test for a defect d, a test pattern should be generated for the stuck-at fault y = (1 © y{W^)) at the additional condition VW = 1. Here y(lA^) Is the expected value of y determined by the condition W^ = 1.
High level 1 j			
	-^	Component Low level	\k T-► 1
n			1 1
		1 Bridging jfault	
p	Environment f		1 1 1
			
Figure 1:
Mapping fauits from iower ievei to higiier ievei
In the described approach we have to characterize all possible defects in all library cells, and represent the results as defect tables or as optimized sets of defect activating
conditions V/ = [V/'-'}. The defect characterization may be computationally expensive, but it is performed only once for every library cell. An example of the fault table for the complex gate AND2,2/NOR2 with a function y = -i(AB Ü CD) is presented in Table 2/13/.
The defect lists W''^ of library components C/c embedded in the circuit can be extended by additional physical defect lists W^k in the close network environment of the component Ck to take into account also the wrong behaviour of Ck influenced by the outside environment (bridging faults, crosstalkings etc.). For these defects additional characterization should be carried out by a similar way as for the library cells.
3. Diagnostic modelling of digital systems by BDDs
Decision Diagrams (DD) can serve as a basis for a uniform approach to test generation for mixed-level representations of systems, similarly as we use the Boolean algebra forthe plain logic level. In the following it is shown how the traditional logic level test methods can be implemented on Binary Decision Diagrams(BDD) /6,7,14/ asa special class of DDs, and then we generalize the procedures developed for BDDs for a general class of DDs /6,16,17/ to handle the test generation problems at higher levels of systems.
Structuraiiy syntiiesized BDDs. In 1959 C.Y.Lee introduced a method for representing digital circuits by Binary Decision Programs/18/. In 1976 /14/ and in 1977 /15/ independently the BDDs were introduced for test generation purposes. Today the theory of BDDs is developing quickly /4,5,19/.
In /7,14/ structurally synthesized BDDs (SSBDD) as a special class of BDDs was introduced to represent the topology of gate-level circuits in terms of signal paths. Unlike "traditional" BDDs /4,18/, SSBDDs directly support test generation for gate-level structural faults without explicitly representing the faults. The advantage of SSBDDs is that the library of D-cubes for components is not needed for structural path activization. That's why SSBDD based test generation procedures do not depend on whether the circuit
->1
Figure 2: Combinationai macro and Iiis SSBDD
is represented on the gate level or on the higher macro-level whereas the macro means an arbitrary single-output subcircuit of the whole circuit. Moreover, the test generation procedures developed for SSBDDs can be easily generalized for higher level DDs to handle digital systems represented at higher levels /6,16,17/.
The BDD that represents a Boolean function is a directed noncyclic graph with a single root node, where all nonterminal nodes are labelled by Boolean variables (arguments of the function) and have always exactly two successor-nodes whereas the terminal nodes are labelled by constants 0 or 1. For all nonterminal nodes, a one-to-one correspondence exists between the values of the label variable of the node and the successors of the node. The correspondence is determined by the Boolean function to be represented by the graph.
Denote the variable which labels a node m in a BDD by x{m). We say that a value of the node variable activates the node output edge. According to the value of x(m), one of two output edges of m will be activated. If x(m) = 1 we say 1-edge is activated, or if x(m) =0 we say 0-edge is activated. A path is activated if all the edges that form this path are activated. The BDD is activated to 0 (or 1) if there exists an activated path which includes both the root node and the terminal node labelled by the constant 0 (or 1).
Definition 3.1. A BDD Gy with nodes labelled by variables xi, X2,..., Xn, represents a Boolean function y = f(X) = f(xi, X2.....Xn), if for each pattern of X, the BDD will be activated to the value which is equal to y for the same pattern.
Important property of SSBDDs. SSBDDs differently from traditional BDDs have the following property: each node m in a Gy which describes a tree-lil<e subnetwork Ny of the gate-level circuit N, represents a signal path l(m) in Ny. There is an one-to-one correspondence between the nodes m in a Gy and the paths i(m) in the corresponding circuit A/y.
An example of a combinational circuit with a tree-like macro and SSBDD for the macro is presented in Figure 2. For simplicity, the values of variables on edges of the SSBDD are omitted (by convention, the 1-edge is always directed to the right, and the 0-edge is always directed downwards). Also, terminal nodes with constants 0 and 1 are omitted (leaving the SSBDD to the right corresponds always to y = 1, and down - to y = 0). Each node is marked by an input variable of the macro. A node with the label Xm in the SSBDD represents the signal path through the macro which begins with the input variable Xm- The node variable is inverted when the path consists of odd number of inverters, and not inverted when the number of inverters is even. For example, the node xy.i of SSBDD represents the signal path with even number of inverters starting with the line X7,i through the nodes a,d,e to the output y in the macro
(the bold lines in the circuit). The node S in the SSBDD has inverted variable since the corresponding path xi ,d,e,y consists of odd number of inverters. The fan-out node xj
in the circuit has three branches, and each branch xjj (; = 1,2,3) is the beginning of a path which is represented by the node X7,/in the SSBDD.
From the above described property of the SSBDD, automatic fault collapsing results. Assume a node m with label variable x(m) represents a signal path i(m) in a circuit. Suppose the path l(m) goes through n gates. Then, instead of 2n faults of the path i(nn) in the circuit, only 2 faults related to the node variable x(m) should be tested when using the SSBDD model.
Test generation with SSBDDs. Consider a combinational circuit as a network of gates, which is partitioned into interconnected tree-like subcircuits (macros). This is a new higher level (macro-level) representation of the same circuit. Each macro is represented by a SSBDD where each node corresponds to an input of the macro. In the tree-like subcircuits only the stuck-at faults at inputs should be tested. This corresponds to testing all the nodes in each SSBDD. Test generation for a node m in SSBDD, which represents a function y = f(X) of a macro, is carried out by the following procedure /19,23/.
Algorithm 1.
1)	A path Im from the root node of SSBDD to the node m is activated.
2)	Two paths/m,e consistent with Im, where ee{0,1}, from the neighborsim® of m to the corresponding terminal nodes m^-® are activated.
3)	For generatijng ^ test for a particular stuck-at-e fault x(m) = e, ee {0,1}, the opposite assignment for x{m) is needed: x{m) = e.
4)	All the values assigned to node variables build the local test pattern T(X,y) (input pattern of the macro) for testing the node m in Gy.
The paths in the SSBDD activated by Algorithm 1 are illustrated in Figure 3.
Root node
Figure 3: Test generation for the node m with SSBDD
To create the final test pattern in terms of primary inputs of the circuit (network of macros) for the given fault in an
embedded macro, fault propagation and line justification through the network of macros are needed. The fault propagation through a macro from the input x to its output y is carried out similarly to the test generation for the node m labelled by x in the corresponding SSBDD Gy as explained in Algorithm 1. Line justification for the task y = e is carried out by activating a path in the graph Gy from the root node to the terminal node m^®.
Example 1. Consider test generation for the bridging defect between lines xe and x/ of the circuit in Figure 2. This defect can be described by a functional fault model {dxj,
xf^x^ =1), which corresponds to the AND-type bridging model. To generate a test for the short we can generate a test for the stuck-at-1 fault (X7,i = 1) of the internal line x/.i (input of the macro) in the circuit at aditional conditions Xe = 0, X7 = 1. Using SSBDD we have to generate by Algorithm 1 a test for the node x/.i in the SSBDD in Figure 2 at the preconditions xe = 0, x/ = 1. Activating the path Im
through the nodes xe, x^, and xg gives new additional as-signmentsxi = 1,andX2= 1. Activating the path/m,i through
the node Xj gives xs = 0. The path Im,o is activated "automatically", since the 0-edge from the node Xy.i is connected directly to the terminal node The paths, activated by the generated test pattern X1X2X5X6X7 = 11001, are shown by bold lines in Figure 2.
4. Using high-level DDs for diagnostic modelling
Test generation and fault simulation methods developed for SSBDDs have the advantage compared to other logic level methods that they can be easily generalized to handle the test generation and fault simulation problems at higher system levels/6,16,17/.
In general case (beyond the Boolean algebra and BDDs) a decision diagram can be defined as a non-cyclic directed graph G = {M, r,X) with a set of nodes M, a set of variables
X, and a relation Tin M /6/. The nodes m e M are labelled by variables x(m) e X (constants or algebraic expressions of X e X). For each value from a set of predefined values of a non-terminal node variable x(m), there exists a corresponding output edge from the node m into a successor node m' e Um). Consider a situation where all variables are fixed to some value. By these values, for each non-terminal node m a certain output edge is chosen, which is connected to a successor node. Let us call these connections between nodes - activated edges, and the chains of them - activated paths. For each combination of values of variables of X, there exists always a full activated path from the root node to a terminal node. This relation describes a mapping from a Cartesian product of the sets of values for variables in all nodes to the joint set of values for variables (or expressions) in terminal nodes. Therefore, by DDs it is possible to represent arbitrary digital functions Y=F{X), where Y is the variable whose value will be calculated by the DD and X is the vector of all variables in nodes of the DD.
Depending on the class of the system (or its representation level), we may have DDs, where nodes have different interpretations and relationships to the system structure. In register transfer level (RTL) descriptions, we usually partition the system into control and data parts. State and output variables of the control part serve as addresses and control words, the variables in the data part serve as data words. High-level data word variables allow to describe RTL functions in data parts. When using DDs for describing complex digital systems, first we have to represent the system by a suitable set of interconnected components (combinational or sequential subcircuits). Then, we have to describe the components by their functions which can be represented as DDs.
As an example, in Figure 4 a RTL data-path and his compressed DD is presented /20/. The DD is created by superposition/6,21 / of elementary DDs for the components of the circuit. The word variables R;,/?2 andRs represent
yi y2
Ri

M,
y3 y4
-F
M,
R2
#0
Ri
«I 1
3
Ri +R2
► IN + R2
Ri

Ri* Rj
^ IN* R2
Figure 4: Register-transfer level data-path system
registers, IN representss the input bus, the integer variables yj,/2, ys, and y4 represent the control signals. Mi, M2 and M3 are multiplexers, and the functions Ri + R2 and Ri* R2 represent the adder and multiplier, correspondingly. The whole DD describes the behaviour of the input logic of the register R2.
In test pattern simulation, a path is traced in the graph, guided by the values of input variables until a terminal node is reached, similarly as in the case of SSBDDs. In this example, the result of simulating the vector y^, y2, ys, Va, Ri, R2, IN = 0,0,3,2,10,6,12 is R2 = R^*R2 = 60 (bold arrows mark the path activated by the control pattern). Instead of simulating all the components in the circuit, on the DD only 3 control variables are visited during simulation, and only a single data manipulation R2 = fli *R2 is carried out.
Each node in DD represents a subcircuit of the system. To test a node means to test the corresponding subcircuit. The paths to be activated during test generation in high-level DDs are illustrated in Figure 5.
inequality	where /= 1,2.....n,
and x(m^') are the algebraic expressions of the terminal nodes.
To generate a scanning test for the node f?i * R2 of the DD in Figure 4, a path l(Ri*R2) = (y4, ya, y2, R^*R2) is to be activated, and the data vetors (local test patterns) DATA = {R^^,R^^', ^1,2,^2,2; ... Ri,m,ff2,m) for testing the multiplier are to be generated at low level by any ATPG. The scanning test consists in cyclically run sequence; FOR all (a,b)eDATA\ /Load: fli = a; Load: R2 = b: Apply: y2 = 0, ya = 3, y4 = 2; Read R2/.
To generate a conformity test for the node m = ys, the following paths are activated l{m) = (y4, ys), l(m, 1) = {ys, yi, R^+R2). Km,2) = (ys, IN). I{m,3) = (ys, R,), l{m,4) = (ys, y2, R-\*R2) that produces a test control vector yi, y2, ys, y4 = 0,0,D, 2. The test data vector D/AM = {R*^, R*2, /A/*) is found by solving the inequality (Ri +R2) i=IN i^R^^ (f?i *R2). The conformity test consists in cyclically run sequence: FOR all De {0,1,2,3}:/Load: = R*v, Load: R2 = Apply: yi = 0, y2 = 0, ys = D, y4 = 2; IN = IN*\ Read R2/.
Root node


Figure 5:

Test generation with high-level Decision Diagrams
We differentiate two testing types used for systems: scanning test {for testing terminal nodes in DDs, i.e. fortesting the data path), and conformity test (for testing nonterminal nodes, i.e. fortesting the control path).
Procedure 1. Scanning test. To generate a scanning test for a terminal node m^-' in the DD Gy, the path l{m^'') from the root node to m^' is to be activated, and the test patterns for testing the function z(m^') should be generated (according to the hierarchical approach, these patterns can be generated on the lower level representation of z{m), and they can be regarded as a set of additional conditions W'' according to the functional fault model to map the faults from logic level to RT level).
Procedure 2. Conformity test. To generate a conformity test for a node /77 in Gy, the following paths are to be activated: 1) /(m), and 2) for all the values of / = 1,2,...,n: l{m,i), and the proper data are to be found by solving the
/1: /2: /3: /4: /5: h. It-
Is-/9: /10:
MVIA,D A=1N MOVR,A R=A MOV M,R OUT=R MOV M,A OUT = A MOV R,M Ä = /W MOVA,M/(=/W ADDR A=A+R ORAR A=AvR ANAR A=AaR CMAA,D A = -vl
O
1,6
OUT
R-<r>
2,3,4,5
IN
Ha-^RI
A V R
AaR
10
z A
Figure 6: Decision Diagrams for a hypothetical microprocessor
An example of a hypothetical microprocessor is presented in Figure 5 given by a instruction set and three DDs Ga, Gr, Gout, for representing the behaviour, correspondingly, of accumulator^, register Rand output logic. Since the model consists of several DDs representing a network of modules, the following tasks are solved for test generation: fault manifestation, fault propagation and line justification.
To generate a scanning test for the node/\+flin Ga, a path l{A+R) = {I, A+R) in Ga is activated, which produces a test pattern / = /7. The test data vector DATA =(/^1,1,^2,1; ^1,2,^2,2; ■■■ A^,m,R2.m) fortesting the adder are generated by a low level ATPG. These operations correspond to the fault manifestation procedure, i.e. for solving a set of conditions H^ =1 to map the low-level defects of the adder to the behavior level errors in the register/A. For propagating the faults from A to OUT, a scanning test for the node A in Gout is generated. As the result, the path l{A) = {I, A) in Gout is activated, which produces a test pattern I = /4. For justification of the data variables A and R, the paths /(/A/) =
Data Path
M
MUXi
MUX2
COND
A			ADR
			
B			
			
C			
			
CC
Control Path
5ix
S4-
Begin
A=B + C
0 1 .Xa

B = B + C
Xa
FF
B = ^B	C=-C		C=--.C
0 1			
[A = A+ B + C ]		C = A + B A = -,C + B	
1		1 1	

-So ■S1
"S2
■ S5
END
Figure 7: A digital system with a behavioral description
(/, IN), correspondingly, in Ga and Gr are to be activated which produce symbolic test vectors {I = h, IN = a) and (/ = /5, IN = r). The scanning test consists in cyclically run sequence: FOR all (a/) g DATA: //5: MOV R,M (Load R = r); /1: MVI A,D (Load = a); /7: ADD R{A = a + b)] U: MOV M,A(Read/^)/.
Consider a digital system with a behavioral description in Figure 6. The system consists of control and data parts. The FSM of the control part of the system is given by the output function y = A (q', x) and the next-state function q = 5 (q', x), where y is an integer output vector variable, which represents a microinstruction with four control fields y = (Ym, Vz, Yz.h yz,2), x = (xa, xc) is a Boolean input vector variable, and q is the integer state variable. The value / of the state variable corresponds to the state s/ of the FSM. The apostrophe refers to the value from the previous clock cycle.
The data path consists of the memory block M with three registers/!; B, C together with the addressing block ADA, represented by three DDs: A = Ga (ym, z), B = Gb (ym, z), C Gc (Ym, z)\ of the data manipulation block CC where
z = Gz (Yz, zi, Z2); and of two multiplexers zj = Gz,i (Yz,i, M) and Z2 = Gz,2 (yz,2, M). The block COND performs the calculation of the condition function x = Gx (A, C).
By superpositioning the DDs /21/ we can represent the system by only four DDs Gq, Ga, Gb, and Gc in Figure 7a.
Consider now the possibility of joining a set of DDs into a single DD. In Figure 7b the DDs Ga, Gb, Gc and Gq are joined into a single Vector Decision Diagram (VDD) M = A.B.C.q = Gm (q', A, B, C, I) which produces a new concise model of the system. For calculating the values to different components of the vector variable M, we introduce a new type of node in VDD called addressing node labeled by an addressing variable I. The VDDs offer the capability to efficiently represent the array variables (corresponding to register blocks and memories) for calculating and updating their values. VDDs are particularly efficient for representing functional memories with complex input logic - with shared and dedicated parts for different memory locations. In general case, all the registers of the data path can be combined in the model as a single memory block.
T ^^^

—[#5]
—{#3

	1
	#3|
	

JzCi
#5
-'S'
L#5j
zBL
#5^
Figure 8. Representing the digital system in Figure 7 by high-level Decision Diagrams
Using VDDs allows significally to increase the speed of simulation, For example, in Gm in Figure 7b for tine input vector q'= 4,xa = 0, xc = 0, the nodes q'andx/\, are traversed for calculating both new/values of-4 and B only once, whereas in case of separate DDs in Figure 7a the nodes c/'and should be traversed for all the graphs: for calculating separately/A, B, C, and q.
5. Experimental results
Table 3 presents the results of investigating the defect-oriented hierarchical test generation based on using of physical defect tables for library cells and logic macro level test generation. Experiments were carried out with a new defect-oriented Automated Test Pattern Generator (ATPG) DOT /22/ for detecting the AND-short defects in the 0.8|jm CMOS technology. We used circuits resynthe-sized from the Verilog versions of the ISCAS85 suite as benchmarks for tests. The circuits were synthesised by SYNOPSYS Design Compiler. Column 2 in Table 3 shows the total number of defects in the defect tables summed over all the gates belonging to the netlist. Column 3 reflects the number of gate level redundant defects. These are defects that cannot be covered by any gate input (Gl) vector of the gate. In column 4 circuit level redundant defects are counted. These are defects that cannot be tested as the circuit structure does not allow to generate a test for any of the Gl vectors covering the defect. This redundancy is proved by the DOT tool. Column 8 shows the percentage of defects covered by DOT, while column 5 shows the ability of logic level SAP-oriented ATPG to cover the physical defects. The next coverage measure shows the SAF-oriented test efficiency. In this value, both, gate level redundancy of defects (column 6) and circuit level redundancy of defects (column 7) are taken into account.
The experiments prove that relying on 100 % SAFtest coverage would not necessarily guarantee a good coverage of physical defects. In many situations the achieved coverage remained well below what can be achievable with the defect-oriented tool. For example, for circuit c2670 the defect coverage 98,29% obtained by SAF tests was more
than 1.7 % lower than the result of the proposed tool. An interesting remark is, that up to nearly 25% of the defects were proved redundant by the DOT and can therefore not be detected by any voltage test. 75% defect coverage for c880 by 100% SAF-test gives not much confidence for this test. Only using DOT allows to prove that most of the undetected defects are redundant, and that the real test efficiency of this SAF-test is actually 99,66%) giving finally a good confidence to the test.
Table 4: Comparison of ATPGs
Circuit	Faults	HITEC [1]		GATEST [3]		DECIDER [9,23]	
		F.C. %	Time s	F.C. %	Time s	F.C., %	Time, s
gcd	454	81.1	170	91.0	75	89.9	14
sosq	1938	77.3	728	79.9	739	80.0	79
mult	2036	65.9	1243	69.2	822	74.1	50
ellipf	5388	87.9	2090	94.7	6229	95.0	1198
rise	6434	52.8	49020	96.0	2459	96,5	151
diffeq	10008	96.2	13320	96.4	3000	96.5	296
average F.C.:		76.9		87.9		88.6	
The experiments of the hierarchical DD-based ATPG DECIDER /9,23/ developed at the Tallinn Technical University were run on a 366 MHz SUN UltraSPARC 60 server with 512 MB RAM under SOUVRIS 2.8 operating system. At present, DECIDER contains gate-level EDIF interface which is capable of reading designs of CAD systems CADENCE, MENTOR GRAPHICS, VIEWLOGIC, SYNOPSYS, etc. In Table 4, comparison of test generation results of three ATPG tools are presented on six hierarchical benchmarks. The tools used for comparison include HITEC /1 /, which is a logic-level deterministic ATPG and GATEST /3/ as a genetic-algorithm based tool.
Actual stuck-at-fault coverages of the test sequences generated by all the tools were measured by the same fault simulation software. The experimental results show the high speed of the ATPG DECIDER which is explained by the DD-based hierarchical approach used in test generation.
Table 3: Experiments of defect oriented test generation on logic level
Circuit	Number of defects			Defect coverage			
	All defects	Redundant defects		100% stuck-at fault ATPG			DOT
		Gates	System				
1	2	3	4	5	6	7	8
c432	1519	226	0	78,6	99,05	99,05	100,00
c880	3380	499	5	75,0	99,50	99,66	100,00
c2670	6090	703	61	79,1	98,29	98,29	100,00
C3540	7660	985	74	80,1	98,52	99,76	99,97
c5315	14794	1546	260	82,4	97,73	99,93	100,00
c6288	24433	4005	41	77,0	99,81	100,00	100,00
6.	Conclusions
Two main trends can be observed today in the field of digital test: defect-orientation to increase the quality of testing, and high-level modelling to reduce the complexity problems of diagnostic analysis. However, on the other hand, counting physical defects increases the complexity, and high-level modelling reduces the accuracy. Hierarchical approaches can solve this antagonism. Decision diagrams discussed in the paper contribute as a good tool for hierarchical modelling and diagnostic analysis of digital systems. The new innovative forms of DDs, structurally synthesized binary decision diagrams, high-level and vector decision diagrams have been discussed. From simulation point of view, they provide a compact and efficient representations of digital systems. High-level DDs is a new model, and there are a lot of possibilities for further research, for additional improvements and optimization.
Acknowledgements: This work has been supported by EU V Framework projects IST-2000-30193 REASON and lST-2001-37592 eVIKINGs II, as well as by the Estonian Science Foundation grants 5649 and 5910. A special thanks to my colleagues Jaan Raik and Artur Jutman from Tallinn University of Technology and Joachim Sudbrock from Darmstadt University of Technology (Germany) for developing the prototype tools of test generation and fault simulation by using DDs.
7.	References
/1/ T. M. Niermann, J. H. Patel. HITEC: Atest generation package for sequential circuits. Proc. European Cont. Design Automation (EDAC). pp.2^4-2^8, 1991 /2/ J.F. Santucci et ai. Speed up of behavioral ATPG. 30f/i ACM/
lEEEDAC, pp. 92-96, 1993. /3/ E. M. Rudnick, J. H. Patel, G, S. Greenstein, T. M. Niermann. Sequential circuit test generation in a genetic algorittim framework. Proc. Design Automation Conference, pp. 698-704, 1994.
/4/ R.E.Bryant. Graph-based algorithms for Boolean function manipulation. iEEE Trans, on Computers, Vol.C-35, No8, 1986, pp.667-690.
/5/ S. Minato. BDDs and Applications for VLSI CAD. Kiuwer Academic Publishers. 1996, 141 p. /6/ R.Ubar. Test Synthesis with Alternative Graphs. iEEE Design&Test of Computers^ Spring 1996,pp.48-57.
/7/ R.Ubar Multi-Valued Simulation of Digital Circuits with Structurally Synthesized Binary Decision Diagrams. OPA (Overseas Pubi. Ass.) N. v. Gordon and Breach Pubiishers, /Multiple Vaiued Logic, Vol.4,1998,pp.141-157. /8/ R.Ubar. Combining Functional and Structural Approaches In Test Generation for Digital Systems. fVlicroelectronics Reiiabiiity, Vol. 38, No 3, pp.317-329, 1998.
/9/ J.Raik, R.Ubar. Sequential Circuit Test Generation Using Decision Diagram Models. iEEE Proc, of Design Automation and Test in Europe, Mur\\ch, March 9-12, 1999, pp. 736-740.
/10/ L.M. Huisman. Fault Coverage and Yield Predictions: Do We Need More than 100% Coverage? Proc. of European Test Conference, 1993, pp. 180-187.
/11/ RNigh, W.Maly. Layout - Driven Test Generation. Proc. iCCAD, 1989, 154-157.
/12/ M.Jacometand W.Guggenbuhl. Layout-Dependent Fault Analysis and Test Synthesis for CMOS Circuits. iEEE Trans, on CAD, 1993, 12,888-899.
/13/ R.Ubar, W.Kuzmicz, W.PIeskacz, J.Raik. Defect-Oriented Fault Simulation and Test Generation in Digital Circuits. int. Symp. on Quality of Electronic Design, San Jose, California, March 26-28, 2001, pp.365-371.
/14/ R.Ubar. Test Generation for Digital Circuits with Alternative Graphs. Proceedings of Tallinn Technical University No 409, 1976, pp.75-81 (in Russian).
/15/ S.B.Akers. Functional Testing with Binary Decision Diagrams. J. of Design Automation and Fault-Tolerant Computing, Vol.2, Oct. 1978, pp.311-331.
/16/ R.Ubar. Vektorielle Alternative Graphen und Fehlerdiagnose für digitale Systeme. Nachrichtentechnil</Elektronik, (31) 1981, H.1, pp.25-29.
/17/ R.Ubar. Test Generation for Digital Systems on the Vector Alternative Graph Model. Proc. of the 13th Annual Int. Symp. on Fault Tolerant Computing, fvlliano, Italy 1983, pp.374-37 7
/18/ C.Y. Lee. Representation of Switching Circuits by Binary Decision Programs. The Bell System Technical Journal, July 1959, pp.985-999.
/19/ R.Drechsler, B.Becker. Binary Decision Diagrams. Kiuwer Academic Pubiishers, 1998, 200 p.
/20/ R.Ubar, A.Moraviec, J.Raik. Cycle-based Simulation with Decision Diagrams. IEEE Proc. of Design Automation and Test in Europe. Munich, March 9-12, 1999, pp.454-458.
/21/ R.Ubar, J.Raik, E. Ivask, M.Brik. Hierarchical Fault Simulation in Digital Systems. Proceedings of Int. Symp. on Signals, Circuits and Systems SCS'2001 ,\as\, Romania, July 10-11, 2001, pp.181-184.
/22/ J.Raik, R.Ubar, J.Sudbrock, W.Kuzmicz, W.PIeskacz. DOT New Deterministic Defect-Oriented ATPG Tool. Proc. of 10'" IEEE European Test Symposium, May 22-25, 2005, Tallinn, pp.96-101.
/23/ J.Raik, R.Ubar. Fast Test Pattern Generation for Sequential Circuits Using Decision Diagram Representations. Journal of Electronic Testing: Theory and Applications. Kiuwer Academic Pubiishers. Vol. 16, No. 3, pp. 213-226, 2000.
Raimund Ubar Tallinn University of Technology Raja 15, 12618 Tallinn, Estonia, raiub@pld.ttu.ee
Prispelo (Arrived): 14. 09. 2005; Sprejeto (Accepted): 28. 10. 2005