文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 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

3. Test Generation Algorithm

Figure 2 SSBDD based Test Generation Flow

The idea of test generation on SSBDDs is based on the follow-ing special property of the model. By testing stuck-at 0 and stuck-at 1 faults in all the nodes of an SSBDD, 100 % of the gate-level stuck-at faults in the corresponding fanout-free region (FFR) will be covered. The SSBDD model synthesis can be regarded as a certain type of fault collapsing. However, different from traditional fault collapsing, not only the number of faults to be considered is minimized but the circuit model itself is com-pacted as well.

Figure 2 shows the basic flow of the SSBDD based algorithm. The algorithm would be an exact equivalent of PODEM [8] if SSBDD models consisted of a system where for each logic gate an elementary BDD corresponded. In order to compare test gen-eration on structurally synthesized BDD and gate level models, we have implemented two types of SSBDD synthesis: one, where BDDs are synthesized for each FFR and the other, where they are synthesized for each gate, respectively. In order to clar-ify the description, some additional definitions are added below. Fault node is the SSBDD node under test.

Fault variable is the variable labeling the fault node.

Fault graph is the SSBDD that contains the fault node.

2. Experimental Results

Table 1 presents experimental results, which were measured on a 233 MHz Pentium II PC under Windows 95 operating system. In the table, comparative test generation results on SSBDD and gate levels are given for two different timeout values. The achieved fault coverages were calculated by simulating faults of the test patterns on the noncollapsed gate-level model. There-fore, the coverages differ slightly from the ones of the ‘classi-cal’, collapsed, fault model. Test generation times were 2.1 – 4.5 times faster on the SSBDD level than on the gate-level.

Basing on the results obtained in current paper, SSBDD de-scriptions appear to be an efficient model for test generation purposes. In the future, a powerful structural level test pattern generator can be implemented by applying more sophisticated methods and algorithms to the proposed model.

circuit fault coverage, % Time, s

Table 1 Test Generation Results

References

[1] S.B.Akers, “Binary Decision Diagrams”, IEEE Trans. on Computers, Vol. 27, pp.509-516, 1978.

[2] R.Ubar, “Test Generation for Digital Circuits Using Alter-native Graphs”, Proc. Tallinn Tech. Univ., Estonia, 1976. [3] K.J.Antreich, M.H.Schulz, “Fast Fault Simulation for

Feasibility of Structurally Synthesized BDD Models for Test Generation

Scan-Based VLSI-Logic”, Proc. of the European Conference on Circuit Theory and Design, 1987.

[4] M.H.Schulz, E.Auth, “Improved Deterministic Test Pattern Generation with Application to Redundancy Identification”, IEEE Trans. on CAD, Vol. 8, No. 7, pp. 811-816, 1989. [5] J.Giraldi, M.L.Bushnell, “Search State Equivalence for Redundancy Identification and Test Generation”, ITC91, 1991.

[6] R.K.Gaede, M.R.Mercer, K.M.Butler, D.E.Ross, “CATA-PULT: Concurrent Automatic Testing Allowing Paralleliza-tion and Using Limited Topology”, Proc. of the 25th DAC, 1988.

[7] K.Cho, R.E.Bryant, “Test Pattern Generation for Sequen-tial MOS Circuits by Symbolic Fault Simulation”, DAC 1989. [8] P.Goel, “An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits”, IEEE Trans. Com-put., pp. 215-222, March 1981.

上一页第2页

你可能喜欢

热门文档

相关文档

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