基于MARCH算法的内存异常检测研究——MARCH-SS算法分析-毕业论文

本科毕业论文(科研训练、毕业设计)题 目：基于MARCH算法的内存异常检测研究 MARCH-SS算法分析姓 名：学 院：软件学院系：软件工程专 业：软件工程年 级：学 号：指导教师：邱明 职称： 年 月基于MARCH算法的内存异常检测研究摘 要在当今工业，由于生产技术和产品设计提高等的原因，每个晶体管的制造成本呈持续下降的趋势，而每个晶体管的测试成本却基本保持不变。因而测试成本在快速追上制造成本，并且将很快超过其制造成本。原因很简单，因为先进的测试设备的价格非常昂贵使得测试成本居高不下。因此，对测试方法和测试算法的改进就成了重中之重。本文从研究系统芯片可测试性设计理论出发，从对可测试性设计的内建自测试方法的研究中找寻对内存测试方法的有益论点。然后，分析存储器和存储单元的故障类型，思考他们的特点，进而比较各种当前较常用的算法，详细分析MARCH算法的特性，探寻对MARCH算法的改进。在文章的下半部份以便于学者及研究人员对MARCH算法的研究和改进为目标，分析设计了一个以MARCH算法为基础的内存检测系统，并对系统的重点和难点进行了详细分析。关键词：MARCH算法 存储器 内存异常检测 BISTAbstractIn 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 manufacturing 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.This article start from can be tested on system-on-chip design theory, from the design to test the built-in self-testing methods in the study of memory testing methods to find a useful argument. Then, memory and storage unit of the fault type, thinking their characteristics and then compare the more commonly used method, detailed analysis of the characteristics of MARCH algorithm, to explore the MARCH algorithm improvements. In the article, in the second half to scholars and researchers in MARCH to study and improve the algorithm as the goal, the design of a MARCH algorithm-based detection system memory and system of priorities and carried out a detailed analysis of difficult.Keywords: MARCH Algorithm Memory Memory Anomaly Detection BIST目 录第一章 存储器测试的发展11.1存储器测试发展动态11.2 BIST的测试方法31.3本章小结8第二章 存储器的故障模型92.1存储器故障分类92.1.1地址解码器故障92.1.2读写逻辑模块故障102.1.3存储单元阵列故障102.2存储单元的简化功能故障102.2.1固定故障（Stuck-At Fault，SAF）112.2.2转换故障（Transition Fault，TF）112.2.3耦合故障（Coupling Fault，CF）112.2.4相邻矢量敏化故障（Neighborhood Pattern Sensitive Fault，NPSF）122.3本章小结12第三章 存储器故障诊断算法分析133.1 存储器的三种故障诊断算法133.1.1 Checkerboard算法（棋盘法）133.1.2Gallop算法（奔跳法）143.1.3 MARCH算法（进行法）153.2基于棋盘算法的改进153.3本章小结17第四章 MARCH算法概要184.1 MARCH概要叙述184.2 MARCH算法演变204.2.1 ATS和改进的ATS算法(MATS)204.2.2 MARCH A和MARCH B算法214.2.3 MARCH C算法224.2.4 MARCH C+算法224.2.5 MARCH C-算法234.2.6 MARCH X和MARCH Y算法234.2.8 MARCH-TB算法244.2.9 MARCH-TBA算法244.2.10 MARCH-SS算法254.3本章小结26第五章 MARCH-SS算法故障分析275.1 MARCH-SS算法分析275.2 MARCH-SS算法故障分析285.2.1 MARCH-SS 算法对固定故障（SAF）的检测295.2.2 MARCH-SS 算法对转换故障（TF）的检测295.2.3 MARCH-SS 算法对倒置耦合故障（CFin）的检测305.2.4 MARCH-SS 算法对固化耦合故障（CFid）的检测315.2.5 MARCH-SS 算法对状态耦合故障（CFst）的检测335.3 MARCH-SS算法适用的静态故障和固态故障355.3.1单个单元静态故障365.3.2静态耦合故障365.3.3单个单元的动态故障375.3.4动态耦合故障375.4 MARCH-SS算法及其改进型比较385.5本章小结43第六章 结论44致谢语45参考文献46ContentsCharpter 1 The Development of Memory Test11.1Developments In Memory Test11.2 Testing Method of BIST31.3 Summary8Charpter 2 Memory Fault Model92.1 Memory Fault Classicification92.1.1 Address Decoder Fault92.1.2 Read And Write Lgic Fault102.1.3 Memory Array Fault102.2 Memory Predigestion Function Fault102.2.1 Stuck-At Fault112.2.2 Transition Fault112.2.3 Coupling Fault112.2.4Neighborhood Pattern Sensitive Fault122.3 Summary12Charpter 3 Memory Fault Diagnosis Algorithm Analysis133.1 Three Kinds of Memory Fault Diagnosis Algorithms133.1.1 Checkerboard Algorithm133.1.2 Gallop Algorithm143.1.3 MARCH Algorithm153.2 Improvement based on Checkerboard Algorithm153.3 Summary17Charpter 4 MARCH Algorithm Summary184.1 MARCH Algorithm Summary Depiction184.2 MARCH Algorithm Evolvement204.2.1 ATS And Improved ATS Algorithm (MATS)204.2.2 MARCH A和MARCH B Algorithm214.2.3 MARCH C Algorithm224.2.4 MARCH C+ Algorithm224.2.5 MARCH C- Algorithm234.2.6 MARCH X和MARCH Y Algorithm234.2.8 MARCH-TB Algorithm244.2.9 MARCH-TBA Algorithm244.2.10 MARCH-SS Algorithm254.3 Summary26 Charpter 5 MARCH-SS Algorithm Fault Analysis275.1 MARCH-SS Algorithm Analysis275.2 MARCH-SS Algorithm Fault Analysis285.2.1 MARCH-SS Check-Up To Stuck-At Fault295.2.2 MARCH-SS Check-Up To Transition Fault295.2.3 MARCH-SS Check-Up To Inversion Coupling Fault305.2.4 MARCH-SS Check-Up To Idempotent Coupling Fault315.2.5 MARCH-SS Check-Up To State Coupling Fault335.3 MARCH-SS Algorithm Applied To Static Fault And Dymamic Fault355.3.1 Single Unit Static Fault365.3.2 Static Coupling Fault365.3.3 Single Unit Dynamic Fault375.3.4 Dynamic Coupling Fault375.4 Comparision of MARCH-SS Algorithm And Its Improvement385.5 Summary43 Charpter 6 Conclusion44Acknowledgement45References46VII第一章 存储器测试的发展随着深亚微米VLSI技术的发展，大量的不同厂家的电路设计或核集成到一个芯片上。存储器密度的增长使存储器的测试面临着更大的挑战。嵌入式RAM存储器是最难测试的电路，因为存储器的测试通常需要大量的测试模式来激活存储器并将存储器的单元内容读出来与标准值进行比较。在可以接受的测试费用和测试时间的限制下，准确的故障模型和有效的测试算法是至关重要的。而为了保证测试时间和故障覆盖率，测试的好坏大大的依赖于所选的功能故障模型。随着集成电路设计方法与工艺技术的不断进步，集成电路的可测性己经成为提高产品可靠性和成品率的一个不可忽视的因素。在近的二十多年中，尤其是最近十年来，电路测试方法的研究日益受到重视，测试问题己经成为了集成电路产品开发的流程中关键问题之一。伴随着电子设备功能和结构日益复杂，“暗箱”方法越来越难以满足需求，因此要求测试人员以更积极的方式介入测试过程，不仅要承担传统测试中激励生成者和响应分析者的角色，而且要作为整个测试过程的主导者和设计者。通过改善被测试对象的设计来提高被测对象的可测试性，从而能更容易找到测试码，并使测试和测试码的生成问题大大简化，这就是可测性设计(DFT)1。1.1存储器测试发展动态自集成电路诞生之日起，设计方法、制造方法和测试方法始终是集成电路发展不可分割的3个组成部分。但在集成电路发展的早期，人们更多的注意力集中在设计和制造领域，而且早期的集成电路逻辑设计与工艺技术相对简单，因此测试方法学的研究曾一度处于不被重视的地位，在当时人们认为可测性设计是可有可无的，是否采用完全由成本预算来决定。可测性设计是在1970年Cherry Hill测试会议上提出的，然而可测性设计的必要性直至上个世纪70年代中期随着集成电路设计的发展才逐渐被人们认识。随后关于可测性设计设计方面的论文和研究成果越来越多，目前在一些重要的国际会议上，如国际测试会议(ITC),国际设计自动化会议(DAC)等都有专门的分组会。此外，一些可测性设计的规则已经成为集成电路设计的工业标准，如IEEE1149. 1标准等。可测性设计己经成为集成电路设计领域一个极其重要的组成部分1。在过去的20年乃至更长的时间里，可测性设计方法的研究主要集中在如何协调测试性能与其所带来的额外代价的折衷关系上。而在整个可测性设计方法学的发展道路上，对于额外代价的考虑也经历了几个不同的阶段，各个阶段都有其不同的研究侧重点，由此也出现了相应的各类可测性设计方法。 在集成电路发展的早期，面积是所有产品设计的关键因素，同时由于可测性设计方法始终是集成电路设计方法的一种补充，因此在那一时期，面积代价成为了研究可测性设计方法学的核心，增加尽可能少的额外面积也就成为了选择可测性设计方法的主导因素。在此期间出现的可测性设计方法多以非扫描方法为主，所谓非扫描方法主要是区别于后来出现的扫描方法而言的。这类方法在写入测试数据时仍然保持电路正常工作时的模式，即所有的测试数据都是通过功能I/0并行写入，电路内部的工作状态也与正常的工作状态相同。这样的方法必然会导致电路内部的某些节点难以控制或者难以观测，因此需要增加适当的结构，在不改变电路逻辑的前提下，提高这些节点的可控性和可观性，例如插入测试点技术、初始化技术、冗余逻辑等等2。非扫描可测性设计方法在发展的早期具有突出的优点:它的面积代价小，测试模式与正常功能模式接近，易于被设计人员理解和接受。但是其设计思想也决定了它具有不可避免的先天不足。第一，设计复杂，为了将电路的测试性能提高到所需的范围，经常需要搜索整个设计空间，并且搜索空间随着电路规模的增加呈级数递增。第二，需要复杂的自动测试生成(Auto Test Pattern Generation, ATPG)技术，在非扫描可测性设计方法中，ATPG算法的优劣对最终能够达到的故障覆盖率有至关重要的影响。第三，非扫描可测性设计方法在处理复杂时序电路时，其测试向量的效率很难得到保证。原因是在时序电路中，非扫描方法经常需要采用一组特定的测试向量序列才能控制或观测某个特定的节点，测试向量序列的长度与节点本身的可测性及可观性密切相关，也就是说与电路的结构密切相关。因此非扫描方法本身并不能保证其效率。非扫描可测性方法的这些不足在集成电路规模不大、复杂度不是很高的情况下，由于其面积代价上的优势，通常比较容易被设计工程师所接受。直接采用功能测试向量进行产品测试实际上就是非扫描测试方法的雏形。但是随着集成电路规模和复杂度的不断提高，非扫描可测性技术逐渐无法再满足设计的需要。同时随着集成电路工艺技术的发展，面积代价的比重也逐渐降低，此时另一种更适于处理复杂电路的可测性设计方法基于扫描的可测性设计方法逐渐成为了可测性设计方法的主流。 所谓基于扫描的可测性设计方法，其基本的设计思想是将电路内部的存储单元(触发器、锁存器等时序单元)全部或部分地构建成链式结构，并采用扫描寄存器(Scan Register)来代替原有的存储单元，由此组成串行的扫描链3。外部的测试数据可以通过指定的测试端口，在测试控制信号的控制下，串行写入存储单元内。在基于扫描的可测性设计方法中，全扫描方法，即将所有存储单元都替换为扫描寄存器的方法，是优点最突出的一种方法。因为如果采用全扫描结构，整个时序电路实际上被转换成了一个单纯的组合电路来进行测试。而对于组合电路来说，它的可测性问题相对时序电路要容易分析得多，而且在逻辑设计中也完全有可能避免使用某些难测的组合电路。经过多年的研究与探索，目前对于一般的组合电路，现有的ATPG算法都可以轻而易举地获得接近百分之百的故障覆盖率，而这些组合电路ATPG算法的复杂性也要远远低于时序电路的ATPG算法。同时由于全扫描方法具有很好的结构化，因此采用全扫描的可测性设计方法，可以以比较低的测试设计代价完成复杂时序电路的处理，并获得满意的故障覆盖率。基于扫描的测试方法同样也有其不足之处。扫描设计需要增加一定的硬件资源来完成扫描寄存器的插入。同时串行的扫描链结构也是缩短测试时间的瓶颈。这些因素对于扫描方法的应用造成了一些负面影响。上述所讨论的基于扫描的可测性设计方法和非扫描方法都是通过对电路施加特定的测试向量，使得电路内部节点上的故障，例如固定为0/1(stack-at-0/1)故障，可以体现在测试结果向量的逻辑值中，从而可以判断电路是否存在故障。因此可以称之为逻辑响应方法。这类方法是目前最为成熟、适用范围最广的一类可测性设计方法。在它们的基础上又根据不同系统对测试性能要求衍生出众多的可测性设计方法。如基于扫描的全扫描设计、部分扫描设计、以及内建自测试等等。除了传统的通过电路的逻辑响应来判断电路故障情况的方法外，还有一些其他的测试方法可以用来检测电路内部是否存在故障。IDDQ测试方法就是另一类较为常见集成电路测试方法。它通过检测电路在特定状态下的静态工作电流来检测电路的内部故障。它可以有效地检测到非固定故障，如桥接故障等。但是当集成电路工艺技术进入深亚微米阶段后，由于亚阈值电流的干扰，通过检测IDDQ电流判断晶体管是否存在故障变得越来越困难。1.2 BIST的测试方法可测性设计中的内建自测试方法(Built-In Self-Test，简称BIST)通过在芯片内部集成少量的逻辑电路实现对整个电路的测试，被认为是解决电路测试问题的有效方法之一。随着芯片集成度的提高，集成电路工程师已不太在乎BIST逻辑所占用的少量的芯片面积，因此BIST已被广泛应用于现代的集成电路中。现代芯片的规模增长迅速，但是管脚数量并没有按比例增长，造成测试的可控制性(controllability)和可观测性(observability)不高。同时芯片密度增高，频率提升，也造成测试困难，在测试领域，全速率测试一向是比较困难的，更何况是一块复杂的SOC芯片。规模巨大的芯片即使是采用DFT的扫描方法进行测试，由于扫描链的长度很长并且扫描链的数量也很多，还是需要很长的单芯片测试时间。高级测试仪器的价格急速攀升，即使是租用的，租金也非常昂贵。在芯片的设计流程中，经常发生的事情是，前端设计人员与测试人员的交流甚少，前端设计人员对功能很清楚，但是并不是很了解测试的领域，造成测试的困难，这也是一个障碍。另外，工业界中高级测试工程师比较短缺，然而测试的地位却变得越来越重要。所以必须要有新的测试技术，目的为了简化测试方法、提高测试效率。BIST即片内自测试的方法便应运而生。这是一种在芯片中增加一些专门为满足测试的电路和结构，由芯片内部产生测试的激励并且分析被测电路的响应，绝大部分的测试工作可以在芯片内部自动地完成。另外也有的BIST方法需要外界进行控制来半自动的进行，但是最主要的工作还是由芯片内部的BIST电路完成测试。BIST的好处在于极大的减小了对测试仪器的依赖性。前面我们分析过，高端的测试仪的成本激增，以至于测试成本占芯片的总体成本越来越大，大规模芯片的设计者和生产者都难以承受如此高昂的开销。BIST的使用，可以减少单芯片的测试时间，简化了测试向量生成的成本，减少了测试向量的存储空间和成本。这样可以使用低中档的测试仪来完成大规模SoC芯片的测试。另外，BIST技术还被用在系统的自动检测、自动诊断、自动恢复这些方面，比如卫星、地下探测等领域。除了以上一些好处之外，BIST还能够提供以往测试的方法难以达到的目的，比如能够更方便做全速测试。以往的全速测试一种是用功能验证的向量，在不同的测试机上用不同的频率来不断地测试芯片，直到该芯片的工作速度不能达到某个频率为止。另一种方法是用静态时序分析工具和ATPG工具共同产生基于延迟模型的测试向量，方法是用时序分析工具选择一些关键的时延路径，并对其产生多种不同的延迟模型，然后用ATPG的工具依据模型产生多套测试向量，在测试的时候，依次从低到高地测试芯片的这些被选择出的关键路径，挑选出能够通过某些级别测试的芯片，那么能够运行在高速的芯片卖到高的价钱。这里看到，以往的全速测试中，芯片的时钟一般是由测试仪加给芯片的，也有的测试可以利用芯片内部的时钟生成电路如PLL的时钟，但必须要有精准的对PLL的控制。高速的测试仪更是价格不菲。所以，全速测试的代价是昂贵的，只有在某几个特殊的对频率非常敏感的领域才需要去做，比如CPU, DSP等。但是如果运用BIST的方法，其内部的被测电路的时钟可以由内部时钟产生电路供给，并且可以由内部控制，被测电路输入输出也是在内部控制的，这样可以简单地实现全速测试，这里需要指出的是，利用BIST方法做全速测试依然是比较复杂的，难点还是在于内部时钟的产生和精确的控制上面，但是只是其好处在于极大地减小了对高级测试仪的依赖。目前虽然基于扫描和ATPG的方法进行测试还是比较主流的方法，但是它已经逐渐不能适应SoC芯片的领域了，由于SoC芯片规模巨大，内部的寄存器数量极多，如果用扫描方法，需要既多又长的扫描链，同时测试向量集也非常庞大，这样测试时间就很长，同时必须要使用大型的测试仪才能存储下那么多的测试向量。与此相比，BIST方法在芯片自测试、现场测试、延迟故障测试、全速测试、非入侵性测试等方面具有很多优点。图1. 1 SCAN/ATPG的方法和BIST方法的区别图1.14分析了以往SCAN/ATPG的方法和BIST方法的区别，通过此表可以看出在现代SoC芯片的测试领域，BIST测试方法占有绝对优势。图1. 2 典型的存储器BIST结构框图图1.24给出了存储器BIST的典型结构。其中，测试向量生成器可以由线性反馈移位寄存器或计数器来实现，根据测试的类型产生地址序列，测试控制单元通常是一个有限状态机，根据测试算法初始化一些命令和数据等输入作用到被测存储器上，存储器的测试输出结果传送到数据压缩器，经压缩后生成测试特征值，它连同一个预先定义的基准特征值一起送入比较器中进行一致性比较5。 20世纪80年代，BIST开始应用于嵌入式存储器当中，早期工作主要侧重于测试算法的改进方面。例如1986年Jai n等人在分析了测试向量需求、数据压缩比较及测试生成算法后，提出了嵌入式存储器的两种自测试方案。它们都是用二进制计数器来产生地址码、数据输入及控制信号。但计数器设置不同。方案一是用计数器产生的地址作为写存储器该地址的数据，结果输出到并行向量特征值寄存器进行观测比较;方案二是针对藕合故障的改进，用棋盘算法，结果输出到比较器进行压缩比较6。早期嵌入式存储器BIST用的较多的是伪随机测试向量。例如，1984年Sun等提出用伪随机向量生成器产生地址序列，1989年David等人提出了RAM的伪随机测试方案。但它们都不能检测模式敏感故障，而且硬件开销大，因为存储器的所有输入数据都要送到输出端进行比较7。伪随机测试向量对逻辑电路的测试很有效，但存储器规则的结构特征需要规则的测试向量。当今存储器GIST主要采用确定性测试向量，如MARCH测试。有限状态机和微代码是产生确定性测试向量的两项主要技术。但有限状态机只能产生预先确定的测试向量，即使是可编程有限状态机的灵活性也很有限，修改测试向量就需要重新设计BIST电路。微代码BIST是一种可编程BIST，可以容易地修改测试向量。例如，1998年Dreibelbis等人提出的基于微处理器的嵌入式DRAMBIST方案，1999年Huang等人提出嵌入式DRAM的可编程BIST方案，用户可以通过编程更改测试向量。2003年Appello等人将可编程BIST方法应用到P1500compliant核的工业设计流程中，并由STMicroelectronics公司加以实现。通过处理器控制嵌入式SRAM的测试向量，不仅支持检测还支持诊断近年研究热点集中在减小故障检测延迟、在线并发测试、全速测试及可靠性改进等方面。BISD(Built-In Self-Diagnosis，内建自诊断)、BIRA(Built-In Redundancy Analysis，内建冗余分析)、BISR(Built-In Self-Repair，内建自修复)等高性能设计技术被用到了存储器的BIST之中8。随着半导体工艺尺寸不断缩小，嵌入式存储器可能存在的故障类型越来越多，使得测试时间和测试成本都急剧增长。合理的故障模型对于存储器的测试至关重要，一种测试方法的故障覆盖率、测试长度等质量指标与所用的故障模型有很大的关系。1.3本章小结可测性设计即调整电路的内部结构，使电路变得易测。由于电路集成度越来越大造成了测试费用巨大和测试访问困难，而内建自测试(BIST)技术被认为是解决这些问题的最有希望的方法，因此本章首先对测试技术中的关键概念进行了介绍，并总结阐述了BIST技术面临的挑战。第二章 存储器的故障模型2.1存储器故障分类研究存储器的检测方法，就必须先建立存储器单元的故障模型，也就是要求把物理故障模型化为逻辑故障，通常可以用功能模型或灰匣子模型将存储器故障模型化，典型RAM功能模型如图2.1所示，该模型是由Vande Goor提出的简化功能DRAM模型2。图2.1 DRAM功能模型对于图2.1的功能模型，存储器的故障主要表现有3类：2.1.1地址解码器故障 主要表现为4种形式（如图2.22所示）。图2.2 地址解码器的常见故障2.1.2读写逻辑模块故障主要表现为在读写电路中，某些检测放大器的出或者写入驱动器的逻辑部分，可能产生开路、短路或者I/O固定的故障，在读写电路的数据线之间存在交叉耦合的干扰。2.1.3存储单元阵列故障由于存储单元阵列是存储器内规模最为复杂的一个模块，因此出现故障的概率最大，故障的类型也最为复杂，主要是由于存储器单元内的数据线开路、短路以及串扰所引起的。对于上述的功能模型去掉其中的某些逻辑模块，就可用于ROM的测试。2.2存储单元的简化功能故障基于以上各模块的故障表现形式，又由于地址译码故障和读写逻辑故障可以等效的功能映射为存储器单元阵列故障，故可把存储器故障简化为下列四种功能故障9：2.2.1固定故障（Stuck-At Fault，SAF）单元或连线的逻辑值总为0或总为1的故障，单元/连线总是处于有故障的状态，并且故障的逻辑值不变。2.2.2转换故障（Transition Fault，TF）转换故障是SAF的一种特殊情况，当写数据时，某一存储单元失效使得01转变或10转变不能发生，表现为固定故障的形式。2.2.3耦合故障（Coupling Fault，CF）耦合故障（Coupling Fault，CF），某一内存单元的状态或其状态的变化将会影响另一内存单元的状态，CF故障又可以细分为三种故障类型：（1）倒置耦合故障（Inversion Coupling Fault，CFin），一个内存单元的写0或写1操作将使另一内存单元的逻辑值倒置，即由0变为1，或者由1变为0。有两种倒置耦合故障：CFin(/)，CFin(/)，其中CFin(/)表示内存单元的值倒置。（2）固化耦合故障（Idempotent Coupling Fault，CFid），一个内存单元的写0或者写1操作将使另一内存单元的值固定在一个确定值，这个值可能是0，也可能是1。有四种固化耦合故障：CFid(;0)，CFid(;1)，CFid(;0)，CFid(;1)。（3）状态耦合故障（State Coupling Fault，CFst），一个内存单元i的值决定了另一内存单元j的值。有四种状态耦合故障：（0；0），（0；1），（1；0），（1；1）。2.2.4相邻矢量敏化故障（Neighborhood Pattern Sensitive Fault，NPSF）一个单元因相邻单元的活动导致状态不正确，一个单元的相邻单元可能有5个，也可能有9个，如图2.32的(a)、(b)所示。图2.3 相邻图形敏感故障2.3本章小结本章在第一章的基础上，介绍了存储器测试领域的故障模型，因为合理的测试模型对于存储器的测试至关重要，一种测试方法的故障覆盖率、测试长度等质量指标均与所用的故障模型有很大关系。具体诊断算法将在下一章叙述。第三章 存储器故障诊断算法分析3.1 存储器的三种故障诊断算法针对存储器故障模型中的各种故障，人们提出了各种诊断算法，目前主要使用的算法有：Checkerboard算法（棋盘法）、Gallop算法（奔跳法）、MARCH算法（进行法）等10。3.1.1 Checkerboard算法（棋盘法）棋盘法的测试过程是首先对每一个存储单元赋值，使得每一个单元与其紧相邻的各个单元的值都不同，如图3.111所示，即把整个存储阵列分为两块a、b，然后采用如下过程对a、b进行读写；（1）对分块a（b）中的单元写0（1）；（2）读所有单元；（3）对分块a（b）中的单元写1（0）；（4）读所有单元；（5）该算法理论上操作的次数是O（N），其中N为存储器容量，可以检测SAF故障和相邻单元的桥接故障，其故障覆盖率较低。图3.1 棋盘法3.1.2Gallop算法（奔跳法）Gallop算法也称为1（0）漫游或乒乓测试，测试过程12如下：（1）部分地址单元清0（1）；（2）A0写1（0），然后A1读0（1），A0读1（0），然后A2读0（1），A0读1（0），接着A3读0（1），A0读1（0），直到全部单元；（3）将A0改写为0（1），写A1为1（0），重复以上步骤。整个过程就像1（0）在整个阵列中漫游一样，图3.213表示1漫游的情况，该算法具有较高的故障覆盖率，能检测SAF故障、TF故障以及CF故障，单位该算法操作次数是O（N2）需要较长的测试时间。图3.2 奔跳法3.1.3 MARCH算法（进行法）（1）全部单元中写0；（2）读A0单元的0，然后再改写为1，然后读A1的0，再改写A1为1，直到An-1。这样所有单元均为1；（3）然后从An-1到A0作读1写0再读0的操作。该算法的操作次数为O（N），能检测全部的SAF故障、AF故障以及TF故障14。3.2基于棋盘算法的改进通过研究和对比上述3个算法发现，Checkerboard（棋盘）算法和MARCH算法以线性方式进行读写，因此存储器操作次数与存储器容量N成正比，Gallop算法虽然有较高的故障覆盖率，但由于其对存储器刺激次数过多，因此，在实际测试中不是一种经济的测试算法，Checkerboard算法只实现了01或10的读写，所以不能测试变迁故障。而MARCH算法恰恰实现了这两个状态的转换，但MARCH算法操作次数（6N）要多于Checkerboard算法的操作次数（4N），对于大容量存储器的测试，MARCH算法将需要比Checkerboard算法更多的测试时间来完成整个测试过程，因此结合MARCH算法的特点，对Checkerboard算法进行如下改进15。 （1）对分块a（b）中单元写1（0）；（2）对分块a（b）中的单元写0（1）；（3）读所有单元；（4）对分块a（b）中的单元写1（0）；（5）读所有单元。这样整个存储器就同时经历了由01和10两个读写状态，就可以测试出变迁故障，写改进后Checkerboard算法对存储器的操作次数为5N次，而MARCH算法对存储器的操作次数则需要6N次，大大地节省了测试时间。以一个X（行地址）、Y（列地址）地址复用的128128的存储器矩阵为例，按改进后的算法编写的测试图形片断如图3.36。图3.3 按改进后算法编写的图形片断实际的算法图形要配合读写的时序，因此图形更为复杂，但对存储器的操作次数与理论是一致的，改进的Checkerboard算法虽然使用了较少的存储器操作次数，但其只能诊断出部分AF故障，与MARCH算法相比，是以牺牲故障覆盖率为代价来提高测试速度的。在实际的生产型测试中，地址译码模块由于结构较存储矩阵要简单得多，因此出现故障的概率远远小于存储矩阵，且改进的Checkerboard算法也能诊断部分的AF故障，是一种经济的测试算法16。3.3本章小结本章在第二章的基础上，概括总结了存储器内建自测试(MBIST)的3种常用诊断算法，并提出了基于棋盘算法的改进，着重介绍了MARCH算法的优劣。关于MARCH算法的详细内容将在下一章讲述。第四章 MARCH算法概要4.1 MARCH概要叙述图4.1 各种MARCH算法的描述传统的存储器测试算法的算法复杂度为0 (n)或0 (n) (n表示存储单元数目)，对于大容量的SRAM，将导致很长的测试时间17。 MARCH测试由于其算法复杂度为0 (n)而成为目前广泛使用的存储器测试算法。该算法的基本原理是利用有限状态机，对所有的地址逐个进行读写操作。算法的指令比较简单，只有读写0/1和地址变化的指令，通过对存储器不断地读写，能够检测几乎所有的存储器故障。MARCH算法系列有很多种，各种不同的算法描述如下表:其中“”表示内存地址递增操作，“”表示内存地址递减操作，“”表示与地址顺序无关，(w0)表示按地址增加的顺序对所有的内存单元写“0”操作，(r0, w1 )表示按地址增加的顺序对每个内存单元读期望值读“0”操作和写“1”操作。18由于各种算法步骤不同，因此，运行的时间也不尽相同。图4.2列举了各种MARCH算法的时间复杂度。图4.2 各种MARCH算法的复杂度 在各种测试方案中，首先对单个单元进行一系列的操作，然后才进行下个单元的操作。操作序列称为MARCH单元(MARCH element)，一个MARCH单元可能包括一组简单的MSCAN序列，也可能包括一组复杂的，带有多个读/写操作的操作序列。基本的MARCH算法如上表所示。由于是对单个单元进行读/写操作，因此其读/写操作的复杂度为0 (mn)。这里m为步进单元中的读/写操作数目。这种算法的故障覆盖率相当好，可以包括单元固定、状图4.3 各种MARCH算法能够检测到的故障类型态跳变以及大量的NPSF和耦合故障。由于存储器的故障类型及其多样，某种算法并不是都能够测到所有的故障。图4.3列举了不同的算法能够检测到的故障类型。194.2 MARCH算法演变4.2.1 ATS和改进的ATS算法(MATS)这些算法能够检测存储器中的卡住故障。ATS (Algorism Test Sequence)由Kanizuk在1977年提出，后来Nair在1979年对其进行了改进，并更名为MATS。此算法对卡住故障能提供最短的齐步测试。后来Abadir又做了进一步改进，称为MATS+算法。在后来，又发明了MATS+算法。算法流程图如图4.4所示图4.4 MATS,MATS+,MATS+算法流程图4.2.2 MARCH A和MARCH B算法MARCH A和MARCH B算法能覆盖一些复合故障，例如:固化耦合故障和转换故障的复合故障;倒置耦合故障和固化耦合故障的复合故障等。图4.5 MARCH A算法流程图图4.6 MARCH B算法流程图4.2.3 MARCH C算法1982年在ITC (International Test Conference)上被提出的MARCH C算法，以及它的一些衍生算法目前已成为存储器测试中最流行的算法20。算法包括11步操作:先按地址递增的顺序进行以下操作: 写“0”(初始化); 读“0”，写“1”; 读“1”，写“0 ”; 读“0”。再按地址递减的顺序进行以下操作: 读“0”，写“1”; 读“1”，写“0”; 读“0”。MARCH C算法可以检测固定故障，跳变故障以及大部分的藕合故障。4.2.4 MARCH C+算法MARCH C+算法是改进后的MARCH C算法，在齐步的每一级增加了一次读操作，使它能够覆盖Stuck-open故障，即前面提到的开路故障是由于MOS管的缺陷等原因造成在某个特定向量输入时，逻辑门的输出端为不期望发生的高阻态。通常发生在控制或译码电路中，对此种故障的覆盖率与输入向量的先后次序有很大关系，因此在每步增加一次读操作可大大提高对此种故障的覆盖率。另外MARCH C+算法同样可检测固定型故障、转换故障以及耦合故障。可见，它是一种很适合检测存储器的算法。4.2.5 MARCH C-算法MARCH C-算法是对MARCH C算法的修正，去掉了第四步的读“0”操作，使总的操作步骤减少到10步，同时并没有降低错误覆盖率，可检测和MARCH C相同的故障类型。MARCH C-测试算法是其它算法的基础，各单元均得到执行，同时单元地址按递增或递减方式提供。19MARCH C-算法测试流程图如图4.7所示：图4.7 MARCH C-算法的流程图MARCH C-算法包括M0、M1、M2、M3、M4和M5六个MARCH单元，该算法能探测到AF，SAF，TF和CF故障，但它不能探测到DRF故障。4.2.6 MARCH X和MARCH Y算法MARCH X和MARCH Y算法能覆盖一些复合故障，例如:固化耦合故障和转换故障的复合故障;倒置耦合故障和固化耦合故障的复合故障等。图4.8 MARCH X算法的流程图图4.9 MARCH Y算法的流程图4.2.8 MARCH-TB算法正如上节分析，MARCH C-算法的诊断能力比较差，并且它不能检测DRF故障。为了改善算法的故障诊断能力并探测DRF故障，有人提出了MARCH-TB算法，此算法的测试流程如图4.10所示。比较MARCH C-算法和MARCH-TB算法，在MARCH-TB算法中增加了四个读操作(M2, M4, M6和M10)，一个写操作(M9)和两个“delay”延迟操作;其中M2为了在诊断时区别SAF (0)和(CFst(0; 0) L)故障类型;M4是为了区别(CFid (; 1) H)和(CFst(1; 1) H)故障类型;M6是区别(CFid(; 0)L)和(Cfid(; 0) H)故障类型;M9, M10和“delay”延迟操作是为了探测和诊断DRF故障。图4.10 MARCH-TB算法测试流程4.2.9 MARCH-TBA算法正如上述分析，MARCH-TB算法虽然提高了故障诊断能力，但是仍有它不能区分的故障类型，为了进一步改善MARCH-TB算法，我们提出了MARCH-TBA算法。算法中区分故障类型的思想如下:l、SAF(0)与TF(/0)。因为SAF(0)是固定0故障，而TF(/0)是发生在0到1转变时，不能转换，并且一旦出现0就不可能改变，之后就等同于SAF(0)故障，所以应该在开始就有读操作才能区分。2、CFst(1;0)L与CFst(1;0)H。它们的区别在前者(L)低位为1将固定高位为0，而后者(H)高位为1固定低位为0，反之，L低位为0，H高位为0将不影响其他位，所以，可以采取地址上升顺序，改变L的低位，最后操作是w0，则前一操作是r1，如果只是r1w0，并不能区分L和H(都为l)，因为在L低位为0后，高位仍为0，所以要有一个w1操作使高位变为1，而H是高位影响低位，写操作改变不了位值(固定位0)，在这种情况下L的r1正确，而H不正确。3、CFst(0;1)L与CFst(0;1)H同上道理，想办法使两者前一状态是高为1低为0和高为0低为1。MARCH-TBA算法的改进测试流程如图4.11所示。图4.11 MARCH-TBA算法测试流程4.2.10 MARCH-SS算法在文章21中提到的MARCH-SS算法如图4.12所示，MARCH-SS算法是MARCH C-算法的改进型，MARCH-SS-算法也包括M0、M1、M2、M3、M4和M5六个MARCH单元，该算法能