文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Feasibility of Structurally Synthesized BDD Models for Test Generation
侵权投诉

Feasibility of Structurally Synthesized BDD Models for Test Generation

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.

Feasibility of Structurally Synthesized BDD Models for Test Generation

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email