1、 本科毕业论文 (科研训练、毕业设计 ) 题 目： 基于 March 算法的内存异常检测 分析 TBA 算法分析 姓 名： 学 院：软件学院 系：软件工程 专 业：软件工程 年 级： 学 号： 指导教师： 职称： 年 月厦门大学本科毕业论文 I 摘 要 在当今工业，由于生产技术和产品设计提高等 原因，每个晶体管的制造成本呈持续下降的趋势，而每个晶体管的测试成本却基本保持不变。因而测试成本在快速追上制造成本，并且将很快超过其制造成本。原因很简单，因为先进的测试设备的 价格非常昂贵使得测试成本居高不下。因此，对测试方法和测试算法的改进就成了重中之重。 本文从研究系统芯片的可测试性设计理论出发，对可
2、测性设计中的内建自测试方法作了更为深入的研究，并对该领域的研究情况进行了介绍。在此基础之上，本文分析了嵌入式存储器内建自测试技术的相关理论和方法，包括其故障模型与测试算法，重点剖析了 March 测试算法，并在己有算法 (March-TB)的基础上 分析 了一种改进型的 March 测试算法 March-TBA算法 。该算法通过增加六步读 (写 )操作，不但覆盖了更多的测试过程中可区分的故障类型，增强 了故障诊断能力，而且减少了测试所需要的时间。改进后的算法的故障覆盖率更高，从而验证了该算法的有效性。 关键词 ： 可测性设计 (DFT) 内建自测试 (BIST) 嵌入式存储器 March 算法
3、 厦门大学本科毕业论文 II Abstract In todays industry, due to production of technology and improve of product design, and other reasons, the manufacturing cost of transistor continues down, but the basic cost of the test of transistor remains unchanged. Thus the tests cost is rapidly catching up with the manuf
4、acturing cost, and will exceed its manufacturing costs. The reason is very simple, because of the high price of advanced test equipment makes the cost high. Therefore, the test methods and test algorithm has become the top priority of improving. First of all， the thesis researches the testing design
5、 theory of system chips. Then， the thesis gives a deeper discussion of BIST in design-for-test and illuminates the research situation of this area. Besides， the thesis explains the related theories and methods of embedded memory BIST including the fault model of memory and the test algorithms of emb
6、edded memory， Particularly analyzes the March algorithm. and the thesis puts forward an improved March algorithm March-TBA based on the existent algorithm. The algorithm not only covers more distinguishable fault kinds in the testing process and intensifies the fault 一 diagnosed capability， but also
7、 shortens the testing time. And the result shows that the improved algorithm can cover most faults. Accordingly， it testifies the validity of the algorithm. Keyword: Design-For-Test (DFT) Built-In Self-Test(BIST) Embedded Memory March Algorithm 厦门大学本科毕业论文 III 目 录 引 言 - 1 第一章 存储器测试的发展 - 2 1.1 存储器测试发展
8、动态 - 2 1.2 BIST 的测试方法 - 4 第二章 存储器的故障模型 - 8 2.1 存储器故障分类 - 8 2.2 存储单元的简化功能故障 - 9 2.3 基于嵌入式存储器的故障模型 - 10 2.4 存储器故障诊断算法分析 -11 2.4.1 Checkerboard 算法（棋盘法） -11 2.4.2 Gallop 算法（奔跳法） - 12 2.4.3 March 算法（进行法） - 13 2.4.4 基于棋盘算法的改进 - 13 第三章 March 算法介绍 - 16 3.1 March 算法简介 - 16 3.2 March 算法演变 - 18 3.2.1 ATS 和改进的
9、ATS 算法 （ MATS） - 18 3.2.2 March A 和 March B 算法 - 18 3.2.3 March C 算法 - 18 3.2.4 March C+算法 - 19 3.2.5 March C-算法 - 19 3.3 March 算法处理的故障类型 - 19 3.3.1 单一内存单元故障（ Stuck-At Fault， SAF） - 20 3.3.2 单一内存单元转换故障（ Transition Fault， TF） - 20 3.3.3 耦合故障（ Coupling Fault， CF） - 20 3.3.4 相邻内存单元敏化故障（ Neighborhood Pa
10、ttern Sensitive Fault， NPSF） - 20 3.3.5 数据保留故障（ Data Retention Fault， DRF） - 20 第四章 March -TBA 算法分析 - 21 4.1 March-TBA 算法的前身 - 21 4.2 March-TBA 算法的主要内容 - 23 4.3 March-TBA 算法的检验成果 - 24 4.3.1 March-TBA 算法对固定故障（ SAF）的检测情况 - 25 4.3.2 March -TBA 算法对状态转换故障（ TF）的检测 - 26 4.3.3 March C-算法对翻转耦合故障（ CFin）的检测 -
11、27 4.3.4 March C-算法对幂耦合故障（ CFid）的检测 - 30 4.3.5 March C-算法对状态耦合故障（ CFst）的检测 - 36 4.4 March-TBA 算法的故障覆盖率 - 42 第五章 结论 - 44 致谢 - 45 参考文献 - 46 厦门大学本科毕业论文 IV Contents Introduction- 1 Charpter 1 Developments Of Memory Testing - 2 1.1 Developments Of Memory Testing - 2 1.2 Testing Methods Of BIST - 4 Charpt
12、er 2 The Fault Mode Of The Memory - 8 2.1 The Kinds of Fault Mode Of The Memory - 8 2.2 Simplified Fault Of Storage Unit - 9 2.3 The Fault Mode Of The SoC Memory - 10 2.4 The Analysis Of Memory Testing Algorithm -11 2.4.1 Checkerboard Algorithm（ Chessboard） -11 2.4.2 Gallop Algorithm - 12 2.4.3 Marc
13、h Algorithm - 13 2.4.4 The Improve Base On The Chessboard - 13 Charpter 3 The Introductio Of March Algorithm - 16 3.1 Brief Introduction Of March Algorithm - 16 3.2 Evolvement Of March Algorithm- 18 3.2.1 ATS And Improved ATS Algorithm (MATS) - 18 3.2.2 March A 和 March B Algorithm - 18 3.2.3 March C
14、 Algorithm - 18 3.2.4 March C+ Algorithm- 19 3.2.5 March C- Algorithm- 19 3.3 The Fault Mode For March Algorithm- 19 3.3.1 Stuck-At Fault - 20 3.3.2 Transition Fault - 20 3.3.3 Coupling Fault - 20 3.3.4 Neighborhood Pattern Sensitive Fault - 20 3.3.5 Data Retention Fault - 20 Charpter 4 Analysis Of
15、March -TBA Algorithm - 21 4.1 Preexistence Of March-TBA Algorithm - 21 4.2 Detail Of March-TBA Algorithm- 23 4.3 March-TBA Fault Analysis- 24 4.3.1 March TBA Algorithm For Stuck-At Fault - 25 4.3.2 March TBA Algorithm For Transition Fault - 26 4.3.3 March TBA Algorithm For Coupling Fault - 27 4.3.4
16、March -TBA Algorithm For Neighborhood Pattern Sensitive Fault - 30 4.3.5 March -TBA Algorithm For Data Retention Fault - 36 4.4 The Fault Cover Of March-TBA Algorithm - 42 Charpter 5 Summarize - 44 Acknowledgements - 45 References - 46 厦门大学本科毕业论文 1 引 言 随着深亚微米 VLSI 技术的发展，大量的不同厂家的电路设计 被 核集成到一个芯片上。存储器密
17、度的增长使存储器的测试面临着更大的挑战。嵌入 式 RAM 存储器是最难测试的电路，因为存储器的测试通常需要大量的测试模式来激活存储器并将存储器的单元内容读出来与标准值进行比较。在可以接受的测试费用和测试时间的限制下，准确的故障模型和有效的测试算法是至关重要的。而为了保证测试时间和故障覆盖率，测试的好坏大大的依赖于所选的功能故障模型。 随着集成电路设计方法与工艺技术的不断进步，集成电路的可测性己经成为提高产品可靠性和成品率 的一个不可忽视的因素。在近的二十多年中，尤其是最近十年来，电路测试方法的研究日益受到重视，测试问题己经成为了集成电路产品开发的流程中关键问题之一。 伴随着电子设备功能和结构日
18、益复杂，“暗箱”方法越来越难以满足需求，因此要求测试人员以更积极的方式介入测试过程，不仅要承担传统测试中激励生成者和响应分析者的角色，而且要作为整个测试过程的主导者和设计者。通过改善被测试对象的设计来提高被测对象的可测试性，从而能更容易找到测试码，并使测试和测试码的生成问题大大简化，这就是可测性设计 (DFT)1。 厦门大学本科毕业论文 2 第一章 存储器测试的发展 1.1 存储器测试发展动态 自集成电路诞生之日起，设计方法、制造方法和测试方法始终是集成电路发展不可分割的 3 个组成部分。但在集成电路发展的早期，人们更多的注意力集中在设计和制造领域，而且早期的集成电路逻辑设计与工艺技术相对简单
19、，因此测试方法学的研究曾一度处于不被重视的地位，在当时人们认为可测性设计是可有可无的，是否采用完全由成本预算来决定。 可测性设计是在 1970 年 Cherry Hill 测试会议上提出的，然而可测性设计的必要性直至上个世纪 70 年代中期随着集成电路设计的发 展才逐渐被人们认识。随后关于可测性设计设计方面的论文和研究成果越来越多，目前在一些重要的国际会议上，如国际测试会议 (ITC),国际设计自动化会议 (DAC)等都有专门的分组会。此外，一些可测性设计的规则已经成为集成电路设计的工业标准，如 IEEE1149. 1 标准等。可测性设计己经成为集成电路设计领域一个极其重要的组成部分 21。
20、在过去的 20 年乃至更长的时间里，可测性设计方法的研究主要集中在如何协调测试性能与其所带来的额外代价的折衷关系上。而在整个可测性设计方法学的发展道路上，对于额外代价的考虑也经历了几个 不同的阶段，各个阶段都有其不同的研究侧重点，由此也出现了相应的各类可测性设计方法。 在集成电路发展的早期，面积是所有产品设计的关键因素，同时由于可测性设计方法始终是集成电路设计方法的一种补充，因此在那一时期，面积代价成为了研究可测性设计方法学的核心，增加尽可能少的额外面积也就成为了选择可测性设计方法的主导因素。在此期间出现的可测性设计方法多以非扫描方法为主， 所谓 非扫描方法主要是区别于后来出现的扫描方法而言的
21、。这类方法在写入测试数据时仍然保持电路正常工作时的模式，即所有的测试数据都是通过 功能 I/0 并行 写入，一电路内部的工作状态也与正常的工作状态相同。这样的方法必然会导致电路内部的某些节点难以控制或者难以观测，因此需要增加适当的结构，在不改变电路逻辑的前提下，提高这些节点的可控性和可观性，例如插入测试点技术、初始化技术、冗余逻辑等等 2。 非扫描可测性设计方法在发展的早期具有突出的优点 :它的面积代价小，测试模式与正常厦门大学本科毕业论文 3 功能模式接近，易于被设计人员理解和接受。但是其设计思想也决定了它具有不可避免的先天不足。 第一，设计复杂，为了将电路的测试性能提高到所需的范围，经常需
22、要搜索整个设计空间，并且搜索空间随着电路 规模的增加呈级数递增。 第二，需要复杂的自动测试生 成 (Auto Test Pattern Generation, ATPG)技 术，在非扫描可测性设计方法中， ATPG 算法的优劣对最终能够达到的故障覆盖率有至关重要的影响。 第三，非扫描可测性设计方法在处理复杂时序电路时，其测试向量的效率很难得到保证。原因是在时序电路中，非扫描方法经常需要采用一组特定的测试向量序列 才 能控制或观测某个特定的节点，测试向量序列的长度与节点本身的可测性及可观性密切相关，也就是说与电路的结构密切相关。因此非扫描方法本身并不能保证其效率。 非扫描可测性方法的这些不足在集
23、成电路规模不大、复杂度不是很高的情况下，由于其面积代价上的优势，通常比较容易被设计工程师所接受。直接采用功能测试向量进行产品测试实际上就是非扫描测试方法的雏形。但是随着集成电路规模和复杂度的不断提高，非扫描可测性技术逐渐无法再满足设计的需要。同时随着集成电路工艺技术的发展，面积代价的比重也逐渐降低，此时另一种更适于处理复杂电路的可测性设计方法 基于扫描的可测性设计方法逐渐成为了可测性设计方法的主流。 所谓基于扫描的可测性设计方法，其基本的设计思想是将电路内部的存储单 元 (触发器、锁存器等时序单元 )全部或部分地构建成链式结构，并采用扫描寄存器 (Scan Register)来代替原有的存储单
24、元，由此组成串行的扫描链 3。外部的测试数据可以通过指定的测试端口，在测试控制信号的控制下，串行写入存储单元内。 在基于扫描的可测性设计方法中，全扫描方法，即将所有存储单元都替换为扫描寄存器的方法，是优点最突出的一种方法。因为如果采用全扫描结构，整个时序电路实际上被转换成了一个单纯的组合电路来进行测试。而对于组合电路来说，它的可测性问题相对时序电路要容易分析得多，而且在逻辑设计中也完全 有可能避免使用某些难测的组合电路。经过多年的研究与探索，目前对于一般的组合电路，现有的 ATPG 算法都可以轻而易举地获得接近百分之百的故障覆盖率，而这些组合电路 ATPG 算法的复杂性也要远远低于时序电路的
25、ATPG算法。同时由于全扫描方法具有很好的结构化，因此采用全扫描的可测性设计方法，可以以比较低的测试设计代价完成复杂时序电路的处理，并获得满意的故障覆盖率。 基于扫描的测试方法同样也有其不足之处。扫描设计需要增加一定的硬件资源来完成扫描寄存器的插入。同时串行的扫描链结构也是缩短测试时间的瓶颈。这些因素对于扫描方 法厦门大学本科毕业论文 4 的应用造成了一些负面影响。 上述所讨论的基于扫描的可测性设计方法和非扫描方法都是通过对电路施加特定的测试向量，使得电路内部节点上的故障，例如固定为 0/1(Stack-At-0/1)故障，可以体现在测试结果向量的逻辑值中，从而可以判断电路是否存在故障。因此可
26、以称之为逻辑响应方法。这类方法是目前最为成熟 、 适用范围最广的一类可测性设计方法。在它们的基础上又根据不同系统对测试性能要求衍生出众多的可测性设计方法。如基于扫描的全扫描设计、部分扫描设计、以及内建自测试等等。 除了传统的通过电路的逻辑响应来判断电路故障情 况的方法外，还有一些其他的测试方法可以用来检测电路内部是否存在故障。 IDDQ 测试方法就是另一类较为常见集成电路测试方法。它通过检测电路在特定状态下的静态工作电流来检测电路的内部故障。它可以有效地检测到非固定故障，如桥接故障等。但是当集成电路工艺技术进入深亚微米阶段后，由于亚阈值电流的干扰，通过检测 IDDQ 电流判断晶体管是否存在故障
27、变得越来越困难。 1.2 BIST 的测试方法 可测性设计中的内建自测试方法 (Built-In Self-Test，简称 BIST)通过在芯片内部集成少量的逻辑电路实现对整个电路的测试 ，被认为是解决电路测试问题的有效方法之一。随着芯片集成度的提高，集成电路工程师已不太在乎 BIST 逻辑所占用的少量的芯片面积，因此 BIST已被广泛应用于现代的集成电路中。 现代芯片的规模增长迅速，但是管脚数量并没有按比例增长，造成测试的可控制性(Controllability)和可观测性 (Observability)不高。同时芯片密度增高，频率提升，也造成测试困难，在测试领域，全速率测试一向是比较困难的
28、，更何况是一块复杂的 SoC 芯片。规模巨大的芯片即使是采用 DFT 的扫描方法进行测试，由于扫描链的长度很长并且扫 描链的数量也很多，还是需要很长的单芯片测试时间。高级测试仪器的价格急速攀升，即使是租用的，租金也非常昂贵。 在芯片的设计流程中，经常发生的事情是，前端设计人员与测试人员的交流甚少，前端设计人员对功能很清楚，但是并不是很了解测试的领域，造成测试的困难，这也是一个障碍。另外，工业界中高级测试工程师比较短缺，然而测试的地位却变得越来越重要。所以必须要有新的测试技术，目的为了简化测试方法、提高测试效率。 BIST 即片内自测试的方法便应运而生。这是一种在芯片中增加一些专门为满足测试的电
29、路和结构，由芯片内部产生测试的激 励并且分析被测电路的响应，绝大部分的测试工作可以厦门大学本科毕业论文 5 在芯片内部自动地完成。另外也有的 BIST 方法需要外界进行控制来半自动的进行，但是最主要的工作还是由芯片内部的 BIST 电路完成测试。 BIST 的好处在于极大的减小了对测试仪器的依赖性。前面我们分析过，高端的测试仪的成本激增，以至于测试成本占芯片的总体成本越来越大，大规模芯片的设计者和生产者都难以承受如此高昂的开销。 BIST 的使用，可以减少单芯片的测试时间，简化了测试向量生成的成本，减少了测试向量的存储空间和成本。这样可以使用低中档的测试仪来完成大规模 SoC芯片的 测试。另外， BIST 技术还被用在系统的自动检测、自动诊断、自动恢复这些方面，比如卫星、地下探测等领域。 除了以上一些好处之外， BIST 还能够提供以往测试的方法难以达到的目的，比如能够更方便做全速测试。以往的全速测试一种是用功能验证的向量，在不同的测试机上用不同的频率来不断地测试芯片，直到该芯片的工作速度不能达到某个频率为止。另一种方法是用静态时序分析工具和 ATPG 工具共同产生基于延迟模型的测试向
