数字电路的位级并行atpg研究-秦李青.pdf

《数字电路的位级并行atpg研究-秦李青.pdf》由会员分享，可在线阅读，更多相关《数字电路的位级并行atpg研究-秦李青.pdf（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 密 级 桂林电子 科 技大学 硕 士 学 位 论 文 题 目 数 字电路 的位级并 行 ATPG 研究 （英文 ） A bit-level Parallel ATPG Research of the Digital Circuit 研 究 生 学 号: 122081803 研 究 生 姓 名: 秦李青 指 导教 师姓 名、 职务: 颜学龙 教授 申 请 学 科 门 类: 工学硕士 学 科、专 业: 仪器科学与技术 提 交 论 文 日 期: 2015 年 4 月 论 文 答 辩 日 期: 2015 年 6 月 _ _ 摘 要 I I 摘 要 随着半导体存储器工业技术、深亚微米工艺技术及芯片生产

2、工艺技术的快速发 展， 电路的工艺尺寸不断减小， 电路的集成度、 复杂度与日俱增， 使 得高集成度电路 的测试变得尤为困难。 显然传统的测试生成算法对于目前的集成电路来说已经不再充 分有效甚至适用， 因此测试生成的研究具有十分重要的理论价值和实际意义， 它的主 要目的就是找到新颖、高效的测试生成算法。 早在六十年代单固定型故障的测试生成问题就已经得到解决了。 但是， 理论分析 证明，自动测试生成所涉及的问题及其相关的子问题几乎都是 NP 完全问题，所以， 加速测试生成，提高测试生成质量一直是人们关注的问题。 论文专注于组合电路中建立模型为单固定故障的测试向量生成。 为了减小测试向 量生成时间和

3、提高故障覆盖率的目的， 重点研究了以下内容： 数字电路测试的基本理 论、 故障模型及建模、 测试向量质量的评价指标、 可测性度量方法及自 动测试向量生 成的一些主要算法， 尤其详细介绍了一种确定性测试生成 位级并行的自动测试向量生 成算法 SWK 测试生成算法，并将该算法与可测性测度结合起来，对该算法进行改 进。在原型算法和改进型 SWK 测试生成算法 的基础上，设计了一个在 Windows 操 作系统下运行的用来研究组合电路测试向量 的生成平台。 该平台首先读入基准电路网 表文件对其进行分析， 然后用改进前后的 SWK 测试生成算法为电路生成测试向量并 且进行故障模拟， 最终给出测试向量生成

4、时间及测试集的故障覆盖率， 通过对所得的 实验数据进行比较分析可知改进后的算法具有可行性和实用性。 关 键词 ： 集成电路 ，单 固定型故障，测试生成 ，SWK 测试生成算法 _Abstract II Abstract With the rapid development of technology of semi-conductor memory industry, deep sub-micron process and chip production process, the size of the circuit decreases and the integration and com

5、plexity of the circuit grows, so the test becomes particularly difficult in the high integrated circuit. Obviously, the traditional test generation algorithm is no longer effective or even suitable for the current IC. Consequently, the research of test generation is of great importance theoretically

6、 and practically. In fact, its main purpose is to find a novel and efficient test generation algorithm. In the early sixties, the problem of test generation has been solved for single stuck-at fault. However, theoretical analysis shows that almost all of the problems as well as the relevant sub prob

7、lem involved in the automatic test generation are belong to NP complete problem. Therefore, it has always been an issue of concern to speed up the test generation and improve the quality of test generation. This paper focuses on test vector generation in the combinational circuit for single stuck-at

8、 fault model. In order to reduce the time of test pattern generation and improve the purpose of the fault coverage, it mainly presents that the basic theory of the digital circuit test, fault model and modeling, the evaluation index of test quality, the method of the testability measure and some mai

9、n algorithm of automatic test pattern generation, and it especially introduces the automatic test pattern generation algorithm, which is a deterministic and bit-level parallel test generation SWK test generation algorithm, which is improved by combining with the testability measure. Based on the pro

10、totype algorithm and improved SWK test generation algorithm, the platform, which runs on the Windows operating system, is designed to study the test pattern generation in combinational circuit. It firstly reads and analyzes the benchmark circuit, and then applies the improved SWK test generation alg

11、orithm to the circuit to generate test pattern and performs fault simulation, and finally gives the test pattern generation and fault coverage of a test set. It shows that the improved algorithm is feasible and practicality by comparing and analyzing the experimental data. Keywords: the integrated c

12、ircuit, single stuck-at fault, test generation, SWK test generation algorithm _目 录 III 目 录 摘 要 . I Abstract . II 第一章 绪论 . 1 1.1 课题研究背景及意义 . 1 1.1.1 课题研究背景 . 1 1.1.2 课题研究目的及意义 . 2 1.2 测试基本原理 . 2 1.3 ATPG 算法发展现状 . 4 1.4 论文的研究内容及章节安排 . 6 第二章 数字电路测试生成的基本理论 . 7 2.1 测试生成的相关概念 . 7 2.1.1 基本概念 . 7 2.1.2 缺陷、失

13、效、故障 . 8 2.1.3 基本故障模型 . 8 2.1.4 故障等价和压缩 . 10 2.1.5 测试生成算法评价 . 11 2.2 故障模拟 . 11 2.3 主要的测试向量生成算法 . 14 2.3.1 生成算法的分类 . 14 2.3.2 测试生成中主要的算法 . 15 2.4 本章小结 . 17 第三章 SWK 测试生 成算法 . 18 3.1 引言 . 18 3.2 相关定义 . 19 3.3 SWK 测试生成算 法实现 . 19 3.3.1 模拟 . 20 3.3.2 回溯 . 21 3.4 本章小结 . 23 第四章 可测试性分析与 SWK 测试生成算法 . 24 4.1 可

14、测性测度 SCOAP . 24 4.1.1 可测性定义及相关计算公式 . 24 4.1.2 SCOAP 算法的实 现 . 26 _目 录 IV 4.2 SWK 测试生成算 法及其改进 . 28 4.3 测试生成涉及的有关文件和数据 . 30 4.3.1 解析网表 . 30 4.3.2 测试生成中的相关数据结构 . 34 4.4 测试生成的总体框架及流程 . 35 4.4.1 生成平台的总体框架 . 35 4.4.2 测试生成流程 . 36 4.5 实验结果 . 42 4.6 本章小结 . 44 第五章 总结与展望 . 45 5.1 总 结 . 45 5.2 展 望 . 45 参考文献 . 47

15、 致 谢 . 50 作者在攻读硕士期间主要研究成果 . 51 _第一章 绪论 1 第 一章 绪论 1.1 课题研 究背景 及意义 随着半导体存储器工业技术、深亚微 米 工 艺 技 术 及 芯 片 生 产 工 艺 技 术 的 快 速 发 展， 电路的工艺尺寸不断减小， 然而电路的集成度、 复杂度突飞猛进。 因此， 测试难 度的增加及对电路可靠性的要求已成为日益尖锐的矛盾问题， 其中最为突出的即是数 字电路的测试问题，因此测试已经成为迫切需要解决的问题。 1.1.1 课 题研究 背 景 美国贝尔实验室在 1947 年发明了世界上第一个晶体管，这使人类进入微电子世 界成为了可能。1958 年，德州仪

16、器公司（Texas Instruments ）的 Jack Kilby 和仙童公 司（Fairchild Semiconductor ） 的 Robert Noyce 等人设计并创造出第一款集成电路 （Integrated Circuits ，IC ）以后，世界由此进入一个属于集成电路的时代。采用某种 制造工艺， 将集成在半导体晶片上所需要的元器件用布线互连使其成为能实现某种特 定用途的微型电子器件就是集成电路。 集成电路经历半个多世纪的发展， 它已经从过 去的小规模集成电路（SSI ） ， 发 展 到 如 今 的 特 大 规 模 ， 其 中 经 历 了 中 规 模 （MSI）、 大规模 （L

17、SI ） 、 超大规 模 （VLSI ） 、 巨大规模 （ULSI ） 集成电路的时 代， 电路中集成 在单个芯片的元件数也从最初的十几个发展到现在的几亿个甚至几 十亿个 1 。 集成电 路不但具有质量轻、 体积小的特征， 还具有寿命长、 速度快、 集成度 高和可靠度高等 优点， 所以它从问世到现在便得到突飞猛进的发展。 从早期半导体工业开始以来， 迄 今为止，由 Gordon Moore 提出的摩尔定律依 然符合如今集成电路的发展规律，那就 是集成电路每经过一至两年的发展， 它表面上所集成的元件数量和它的性能指标都将 会增加一倍 234 。 现代电子产品的核心部件是集成电路， 并且集成电路也

18、是信息技术 （Information Technology ，IT ） 产业 的重点。 各个行业里的作业及相互之间的洽谈合作均通过使用 数字计算机来进行开展， 于是大规模数字集成电路已经普遍应用到我们日常工作生活 中的各个领域范围内。 比如集成电路的不断发展对计算机领域比较突出 的、 明显的影 响是： 计算机从原来体积庞大笨重且运行速度极慢的第一代巨型机发展到如今体积小 而便捷的第四代计算机， 而它们拥有每秒几百万次甚至上亿次的运算速度 5 。 集成电 路在通信方面上也存在着广泛的应用， 例如通信卫星、 手机、 雷达等 等， 我国自主研 发的 “北斗 ” 导航系统 就是其中比较典型的例子， 同

19、时医疗产品中也广泛应用到集成 电路， 像电子助听器、 电子血压计、 便携血糖仪、 临时心脏起搏器、 磁振造影仪等医 疗设备 6 。 _数字电 路的 位级 并 行 ATPG 研究 2 1.1.2 课 题研究 目 的及意义 生活在集成电路飞速发展的时代， 电子产品几乎遍及我们工作生活周围的各个角 落， 它 给我们的工作、 学习及生活带来了极大便利和乐趣， 但同时也出现了一些不可 避免的问题。 由于半导体存储器工业技术、 深亚微米工艺技术及芯片生产工艺技术的 快速发展，使得电路的集成度、复杂度与日俱增，集成电路拥有集成度高、体积小、 专用性强等优点。 但集成电路的高集成度让所有元器件相互之间都有联系

20、， 作为一个 整体不可分割。有时这个整体中的一个小部件出现问题，或许会对整体产生副作用、 甚至正常功能无法执行。 近些年， 集成电路的发展虽然带给人们舒适的工作生活环境 但同时还给人们带来了一些事故， 而这多部分是由于元器件的故障而引发的。 一旦出 现事故， 不仅造成巨大的经济损失， 更可怕的是带来的人员伤亡事件 7 ， 例如，1986 年， “挑 战者号 ” 航天 飞机因为 一个助 推火箭 的密封装 置出现 故障而 导致的事 故；1 996 年，由于数字转换错误而造成的阿丽亚娜五型火箭爆炸，还有 2003 年，由于飞 机外部燃料箱表面泡沫材料安装过程中存在的缺陷导致了美国 “ 哥伦比亚” 号

21、航天飞 机坠毁的悲剧等等。由此可知，保证器件的安全性和可靠性是迫切需要解决的难题。 集成电路的蓬勃发展， 相当程度上加大了芯片 的测试难度， 与此同时相应的测试费用 和测试时 间也在 日益增 加。如今 芯片测 试费用 甚至达到 整个开 发费用 的 50%-70% 。 产品的测试关系到产品的生产成本、 产品的品质及产品上市时间 8 。 因此测试已经成 为迫切需要解决的问题。 集成电路故障测试旨在故障检测和故障定位， 从不同层次检测相同的故障时， 检 测的代价也会有很大差异。从客观上讲，数字电路的测试贯穿门级、芯片级、PCB 板 级 和 系统 级 ，而 要 分别 在 门 级、 芯 片级 、PCB

22、板 级 、 系统 级 检测同 一 故 障， 测 试 成本在高一个层次上是低一个层次数量级的十倍， 以此类推， 逐渐递 增， 并且测试成 本还与电路输入管脚数及时钟频率的增加成指数增长， 一般认为在产品设计周期内用 时最长的是测试生成的阶段 9 。 对于当代大规模集成电路甚至超大规模集成电路来讲， 传统的测试手段的缺点非 常明显的暴露出来， 它测试的速度相当慢、 需要修复的时间非常长， 测试结果的可靠 性和准确性受到人为、 环境及设备等诸多外部因素的影响， 因此测试结果具有不稳定 性和不可靠 性 10 。 于是 ， 测试手段与当代集成电路规模之间的这种矛盾日益尖锐， 迫 使人们研究新颖的技术和可

23、行的方法来完成电路测试这项复杂而艰巨的任务。 1.2 测试基 本原理 集成电路的测试包括两个方面： 一是对成品通过使用专用的测试仪器来对它的质 量进行评估；二是指在设计产品的过程中为让产品达标而执行一系列的操作步骤 11 。 测试电路的目的是为 了确定电路是否运行正常并能实现预期的功能要求， 若有故障则 _第一章 绪论 3 能确定故障所处的位置即故障定位。 依靠设计的一定电路产生测试向量的过程称为测 试生成， 测试生成怎样能生成高故障覆盖率、 用时短、 测试集小的测试集成为当代专 家学者研究的焦点。 把测试向量施加到被测电路的过程称为测试施加， 施加激励是自 动测试系统软件技术和硬件技术相结合

24、的重点， 测试向量的数据格式要和实际的测试 系统的硬件设备环境相兼容， 标准化测试向量数据的格式， 对独立设计和使用测试系 统中的软硬件有益， 那么硬件系统的任务就是驱动加载标准数据并且根据测试任务的 配置要求生成 符合被测电路的激励。 被测电路在施加激励之后的原始输出端的输出称 为测试响应， 测试响应数据格式的重要性和测试向量数据格式的重要性同等重要， 在 格式上两者应该保存一致， 这样有利于后面的数据分析进而对故障进行定位。 判断测 试结果的过程称为测试分析， 测试分析是通过对测试向量和输出响应的全面分析， 分 析电路的特征给故障定位。测试分析主要有下面两种：一是通过对数据的人工分析； 二

25、是利用全自动化算法软件进行自动分析来完成故障定位等一系列操作， 该方法可以 和生成测试向量这一环节在一起使用， 在自动测试向量生成算法研究时就要考虑故障 的定位 分析， 编写一个完备的自动测试系统， 也可以开发成自主的软件模块进行使用， 不过分析电路故障时要使用到测试向量数据 12 。 建模、 测试生成、 测 试施加、 测试响 应的比较等过程组成了电路的测试分析过程 13 ，图 1.1 表示了电路测试的基本过程。 建模 测试 向量生 成 测试 施加 被 测 电 路 建 模 理 想 结 果 测 试 响 应 合 格/ 不 合格图 1.1 电 路测试 基本过 程 电路测试中关键和 核心的内容是测试生

26、成这一部分， 其中自动测试生成是进行电 路测试的重要前提条件。 结构测试和功能测试是测试的两大类型测试。 功能测试顾名 思义可知该测试方法仅针对产品的全部功能进行验证， 看该产品是否符合设计时的要 求， 该测试方法一般来说使用于设计验证电路的阶段。 穷举测试是功能测试中最简单 测试方法， 但该测试方法在 针对于具有非常多的原始输入端的电路时， 该算法很难付 诸于实际的应用之中。 结构测试运用一个具有清晰明确的故障覆盖率的测试向量来测 试产品是否存在有缺陷， 电路里面的原始输入端、 基本逻辑门及原始输出端的验证都 是通过该 测试方法使用不一样的算法进行的， 该测试经常应用到产品制造中。 结构测

27、试的优点在于允许我们开发一些算法， 而这些测试向量生成算法具有一套完善的理论 体系，各种不同生成算法相互之间在技术上有 交汇融合之处而每一种都有其优缺点， 建立故障模型是使用这些算法的 关键和核心的一步， 为故障建立模型是进行测试生成 和故障模拟的基础条件 13 。 在实际应用中， 芯 片的物理故障是 千变万化 的。 一方面的 _数字电 路的 位级 并 行 ATPG 研究 4 原因是故障拥有很多的种类。 另一方面 是 不同系统中的故障数目有很大区别， 然而出 现多故障组合就更复杂 ， 所以为了探索故障的影响和对故障进行定位， 需要对故障进 行分类并且构造特别典型的故障， 该过程称为故障建模。

28、总的来说， 用两种方式来描 述故障模型： 第一种故障模型用来描述元器件之间的连接； 第二种故障模型用来描述 改变元器件真值表 。 元器件完好是研究前一种故障模型的基础， 它常见于 PCB 级测 试中， 桥接、 固定型和 开路故障是前者比较有代表性的 故障模型， 后者故障模型拒绝 RTL 操作，它与电路的 功能模型有关，开路和桥接故障等是后者代表性的 故障模型， 它们受到电路的版图结构和制造工艺的影响 9 。 不论元器件本身还是它们之间的连接 在集成电路测试中都必须要进行测试。 1.3 ATPG 算法发展 现状 按集成电路功能、 结构的不同， 可以将其划分为三种： 数字集成电路、 数模混合 型集

29、成电路以及模拟集成电路。 模拟集成电路主要是指由 常见元器件 组成的模拟电路 集成在一起用来处理模拟信号的集成电路。 常见的电路像运算放大器、 电源管理芯片 等， 模拟集成电路的设计和调试需要研究人员手动来完成 14 。 数字集 成电路是以布尔 代数（0 和 1）为基础而进行设计和运行的逻辑电路和系统，数字逻辑信号是其主要 的处理对象 。 数模混合电路顾名思义可知该类型的电路对于前两者电路的功能兼而有 之， 既能对数字逻辑值信号进行处理， 还能对模拟问题进行解决。 与前两种电路比较 而言， 首先数字电路在我们的生活中应用的更为普遍， 几乎所有的电路系统 中都会用 到数字电路； 另外数字电路还具

30、有很多优点， 所以许多行业主要对数字电路进行开发 研究。 自动测试向量生成 （Automation Test Pattern Generation ，ATPG ） 是依 靠计算机或 者其他设备运用某种测试生成算法为被检测电路自动的生成测试向量的过程 11 。 数字 电路测试研究的基础是组合逻辑电路，而器件测试就是从它开始的。Eldred 在 1959 年首次提出了关于它的测试报告的有关文章， 因为该方法无法对两级以上的组合逻辑 电路进行测试， 故而它是测试生成算法中相对来说十分简单的， 但是它却拉开了针对 电路系统测试的序幕 15 。一维通路敏化的算法是由外国学者 D.B.Armstrong

31、在 1966 年所宣布的，它的基本思想其实是 Eldred 的思想精髓的延续，但它与前者相比明显 的优势在于能够处理多于两级的逻辑门电路 16 ， 利用该算法确实解决了好多组合电路 测试生成的问题。 那时人们普遍认为， 组合电路中除去冗余故障以外， 任何故障都可 以从故障节点沿着电路中某一个通路传播到原始输出端。 直到 Schneider 在 1976 年举 出确凿的反例 有 些 故 障 必 须 敏 化 多 条 路 径 才 能 传 播 到 原 始 输 出 端 来 证 实 了 这 个 错误的想法，但 Schneider 并没有提出解决的 方案。由外国学者 Roth 等人在 1966 年 宣布的

32、D 算法 17 ，它 采用立方体进行运算并且引入多路径的思想，可以认为它是拓 _第一章 绪论 5 扑结构测试中最经典的算法 ，它是完备的并且最早实现自动化的测试生成 算法 18 。 布尔差分法 19 是由外国 学者 Sellers 等人在 1968 年提出的， 它求得结果的测试流 程为： 使用描述电路正常输出响应和故障输出响应的两套数学式子来进行差分运算进 而实现对该故障测试向量的求解， 在对该算法的研究上具有理论和实际意义 20 。 主路 径法 21 是布尔差分法发 展中比较具有代表性的， 布尔差分法中借鉴并引入了主路径法 的通路敏化概念， 从而提高了算法的效率。 近年来还有基于布尔差分法的

33、思想发展起 来的二元判定图（BDD ）测试生成算法 9 。 PODEM 算法 22 是由外 国学者 Goel 在 1981 年提出的， 它依然延续了 D 算法思想 的精髓， 它把寻找测试向量问题转 化为在 n 维空间搜索的过程， 即是采用逐个给原始 输入赋值的方法为给定目标故障生成测试向量 23 。 但在对数字电路进行测试时经常会 遇到扇出源的情况， 这将会明显加大测试生成的难度， 为了能缓解这些情况， 日本的 学者 Fujiwara 等人于 1983 年提出了 FAN 算法 24 ， 该算法在测试生成过程中使用了一 些策略， 因此减少了回溯次数， 降低每一次的回溯时间， 从而加速 了测试生成

34、并且具 有较高的故障覆盖率。 稍后陆陆续续出现了一些比较有效的测试生成算法， 它们均保 留了 D 算法思想的精髓，但又都各自引入其他有效的技术和策略来尽早发现可能存 在的冲突和及时 识别冗 余故障，目的是 对无解 空间及早的确定 。如 Kirkland 等人于 1987 年提出来的 Tops 算法 25 等。以后相继出 现了其它改进算法像 SOCRATES 算法 26 、EST 算法 27 、NNATPG 算法 28 和基于二 元判决图的 CATAPULT 算法 29 。 由 E.Gizdarski 等人在 2001 年提出了基于布尔满足性 （SAT） 的测试 生成算法 30 ， 该算法把电路模型用 CNF （Conjuctive Normal Form ）范式来描述， 符合布尔可满足 性原则；不久之后基于蕴涵图（IG ）的测试生 成算法被他提出，该算法是