基于MARCH算法的内存异常检测研究MARCHTB及MARCHY算法分析毕业论文.doc

《基于MARCH算法的内存异常检测研究MARCHTB及MARCHY算法分析毕业论文.doc》由会员分享，可在线阅读，更多相关《基于MARCH算法的内存异常检测研究MARCHTB及MARCHY算法分析毕业论文.doc（47页珍藏版）》请在三一文库上搜索。

1、厦门大学软件学院-毕业论文本科毕业论文(毕业设计)题 目：基于MARCH算法的内存异常检测研究 -MARCH-TB及MARCH-Y算法分析 姓 名：学 院：软件学院系：软件工程专 业：软件工程年 级： 学 号： 指导教师（校内）： 职称： 年 月40摘 要在当今工业，由于生产技术和产品设计提高等的原因，每个晶体管的制造成本呈持续下降的趋势，而每个晶体管的测试成本却基本保持不变。因而测试成本在快速追上制造成本，并且将很快超过其制造成本。原因很简单，因为先进的测试设备的价格非常昂贵使得测试成本居高不下。因此，对测试方法和测试算法的改进就成了重中之重。本文从研究系统芯片可测试性设计理论出发，从对可测

2、试性设计的内建自测试方法的研究中找寻对内存测试方法的有益论点。然后，分析存储器和存储单元的故障类型，思考他们的特点，进而比较各种当前较常用的算法，详细分析MARCH算法的特性，探寻对MARCH算法的改进。在文章的下半部份以便于学者及研究人员对MARCH算法的研究和改进为目标，分析设计了一个以MARCH算法为基础的内存检测系统，并对系统的重点和难点进行了详细分析。本文包括了对内存故障模型和内存测试算法的分析，并主要对所设计的Windows和DOS版内存检测系统进行介绍，分别列出了其详细设计，和运行效果，并就各种MARCH算法所提供的测试向量进行了分析比较。关键词：MARCH算法 存储器 内存异常

3、检测 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

4、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 t

5、heory, 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

6、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 a

7、nalysis of difficult.In this paper, including the fault of memory and memory test model algorithm analysis and design of the main Windows and DOS version of memory test system, a breakdown of its detailed design and operational effectiveness, and analyse the difficulties in achieving, to resolve.Key

8、words: MARCH Algorithm ，Memory， Memory Anomaly Detection ，BIST目 录摘要II引 言1第一章 存储器测试的发展21.1存储器测试发展动态21.2 BIST的测试方法4第二章 存储器的故障模型82.1 存储器故障分类82.2存储单元的简化功能故障92.3存储器故障诊断算法分析92.3.1 Checkerboard算法（棋盘法）102.3.2 Gallop算法（奔跳法）102.3.3 MARCH算法（进行法）112.3.4基于棋盘算法的改进11第三章MARCH算法详细叙述153.1 ATS和改进的ATS算法(MATS)153.1.1 MA

9、TS算法153.1.2 MAT S+算法153.1.3 MATS+算法163.2 MARCH A和MARCH B算法163.2.1 MARCH A算法173.2.2 MARCH B算法173.3 MARCH C算法183.3.1 MARCH C算法183.3.2 MARCH C+算法193.3.3 MARCH C-算法203.4其它MARCH算法203.4.1 MARCH X算法203.4.2 MARCH-TBA算法213.4.3 MARCH SS算法223.5小结23第四章MARCH-TB和MARCH-Y算法274.1 MARCH TB算法思想及内容274.1.1 MARCH-TB算法的故障

10、检测能力284.1.2对 SAF故障分析304.1.3 对TF 分析304.1.4 对CF故障分析314.1.5对DRF故障分析334.2 MARCH-Y算法334.2.1 MARCH-Y算法及其检测能力334.2.2 对SAF故障344.2.3对TF故障354.2.4 对CFin故障35第五章 总结37致谢38参考文献39ContentsABSTRACTIIINTRODUCTION1CHAPTER I OF THE DEVELOPMENT OF MEMORY TEST21.1 Memory test developments21.2 BIST testing methods4CHAPTER

11、II MEMORY FAULT MODEL82.1 Memory fault classification82.2 Storage units feature a simplified fault92.3 Memory fault diagnosis algorithm of92.3.1 Checkerboard algorithm (The board)102.3.2 Gallop algorithm (Ben jump)102.3.3 MARCH algorithm (a)112.3.4 based on the chessboard of the algorithm to improve

12、11CHAPTER III MARCH ALGORITHM DESCRIBED IN DETAIL153.1 ATS ATS and improve the algorithm (MATS)153.1.1 MATS algorithm153.1.2 MAT S + algorithm153.1.3 MATS + + algorithm163.2 MARCH A algorithm and MARCH B163.2.1 MARCH A algorithm173.2.2 MARCH B algorithm173.3 MARCH C algorithm183.3.1 MARCH C algorith

13、m183.3.2 MARCH C + algorithm193.3.3 MARCH C-algorithms203.4 Algorithm other MARCH203.4.1 MARCH X algorithm203.4.2 MARCH-TBA algorithm213.4.3 MARCH SS algorithm223.5 Summary23CHAPTER IV MARCH-TB ALGORITHM DETAILING274.1 MARCH TB algorithm thinking and content of274.1.1MARCH-TB capacity fault detectio

14、n algorithm284.1.2 Failure Analysis of the SAF304.1.3 Failure Analysis of the TF304.1.4 Failure Analysis of the CF314.1.5 Failure Analysis of the DRF334.2 MARCH-Y algorithm334.2.1 MARCH-Y algorithm and its ability to detect334.2.2 Failure Analysis to SAF344.2.3 Failure Analysis to TF354.2.4 Failure

15、Analysis to CFin35CHAPTER V CONCLUDED37THANKS38REFERENCES39引 言随着深亚微米VLSI技术的发展，大量的不同厂家的电路设计或核集成到一个芯片上。存储器密度的增长使存储器的测试面临着更大的挑战。嵌入式RAM存储器是最难测试的电路，因为存储器的测试通常需要大量的测试模式来激活存储器并将存储器的单元内容读出来与标准值进行比较。在可以接受的测试费用和测试时间的限制下，准确的故障模型和有效的测试算法是至关重要的。而为了保证测试时间和故障覆盖率，测试的好坏大大的依赖于所选的功能故障模型。随着集成电路设计方法与工艺技术的不断进步，集成电路的可测性己经

16、成为提高产品可靠性和成品率的一个不可忽视的因素。在近的二十多年中，尤其是最近十年来，电路测试方法的研究日益受到重视，测试问题己经成为了集成电路产品开发的流程中关键问题之一。伴随着电子设备功能和结构日益复杂，“暗箱”方法越来越难以满足需求，因此要求测试人员以更积极的方式介入测试过程，不仅要承担传统测试中激励生成者和响应分析者的角色，而且要作为整个测试过程的主导者和设计者。通过改善被测试对象的设计来提高被测对象的可测试性，从而能更容易找到测试码，并使测试和测试码的生成问题大大简化，这就是可测性设计(DFT)1。第一章 存储器测试的发展1.1存储器测试发展动态自集成电路诞生之日起，设计方法、制造方法

17、和测试方法始终是集成电路发展不可分割的3个组成部分。但在集成电路发展的早期，人们更多的注意力集中在设计和制造领域，而且早期的集成电路逻辑设计与工艺技术相对简单，因此测试方法学的研究曾一度处于不被重视的地位，在当时人们认为可测性设计是可有可无的，是否采用完全由成本预算来决定。可测性设计是在1970年Cherry Hill测试会议上提出的，然而可测性设计的必要性直至上个世纪70年代中期随着集成电路设计的发展才逐渐被人们认识。随后关于可测性设计设计方面的论文和研究成果越来越多，目前在一些重要的国际会议上，如国际测试会议(ITC),国际设计自动化会议(DAC)等都有专门的分组会。此外，一些可测性设计的

18、规则已经成为集成电路设计的工业标准，如IEEE1149. 1标准等。可测性设计己经成为集成电路设计领域一个极其重要的组成部分1。在过去的20年乃至更长的时间里，可测性设计方法的研究主要集中在如何协调测试性能与其所带来的额外代价的折衷关系上。而在整个可测性设计方法学的发展道路上，对于额外代价的考虑也经历了几个不同的阶段，各个阶段都有其不同的研究侧重点，由此也出现了相应的各类可测性设计方法。 在集成电路发展的早期，面积是所有产品设计的关键因素，同时由于可测性设计方法始终是集成电路设计方法的一种补充，因此在那一时期，面积代价成为了研究可测性设计方法学的核心，增加尽可能少的额外面积也就成为了选择可测性

19、设计方法的主导因素。在此期间出现的可测性设计方法多以非扫描方法为主，所i胃非扫描方法主要是区别于后来出现的扫描方法而言的。这类方法在写入测试数据时仍然保持电路正常工作时的模式，即所有的测试数据都是通过功能I/0并行写入，一电路内部的工作状态也与正常的工作状态相同。这样的方法必然会导致电路内部的某些节点难以控制或者难以观测，因此需要增加适当的结构，在不改变电路逻辑的前提下，提高这些节点的可控性和可观性，例如插入测试点技术、初始化技术、冗余逻辑等等2。非扫描可测性设计方法在发展的早期具有突出的优点:它的面积代价小，测试模式与正常功能模式接近，易于被设计人员理解和接受。但是其设计思想也决定了它具有不

20、可避免的先天不足。第一，设计复杂，为了将电路的测试性能提高到所需的范围，经常需要搜索整个设计空间，并且搜索空间随着电路规模的增加呈级数递增。第二，需要复杂的自动测试生成(Auto Test Pattern Generation, ATPG)技术，在非扫描可测性设计方法中，ATPG算法的优劣对最终能够达到的故障覆盖率有至关重要的影响。第三，非扫描可测性设计方法在处理复杂时序电路时，其测试向量的效率很难得到保证。原因是在时序电路中，非扫描方法经常需要采用一组特定的测试向量序列才能控制或观测某个特定的节点，测试向量序列的长度与节点本身的可测性及可观性密切相关，也就是说与电路的结构密切相关。因此非扫描

21、方法本身并不能保证其效率。非扫描可测性方法的这些不足在集成电路规模不大、复杂度不是很高的情况下，由于其面积代价上的优势，通常比较容易被设计工程师所接受。直接采用功能测试向量进行产品测试实际上就是非扫描测试方法的雏形。但是随着集成电路规模和复杂度的不断提高，非扫描可测性技术逐渐无法再满足设计的需要。同时随着集成电路工艺技术的发展，面积代价的比重也逐渐降低，此时另一种更适于处理复杂电路的可测性设计方法基于扫描的可测性设计方法逐渐成为了可测性设计方法的主流。 所谓基于扫描的可测性设计方法，其基本的设计思想是将电路内部的存储单元(触发器、锁存器等时序单元)全部或部分地构建成链式结构，并采用扫描寄存器(

22、Scan Register)来代替原有的存储单元，由此组成串行的扫描链3。外部的测试数据可以通过指定的测试端口，在测试控制信号的控制下，串行写入存储单元内。在基于扫描的可测性设计方法中，全扫描方法，即将所有存储单元都替换为扫描寄存器的方法，是优点最突出的一种方法。因为如果采用全扫描结构，整个时序电路实际上被转换成了一个单纯的组合电路来进行测试。而对于组合电路来说，它的可测性问题相对时序电路要容易分析得多，而且在逻辑设计中也完全有可能避免使用某些难测的组合电路。经过多年的研究与探索，目前对于一般的组合电路，现有的ATPG算法都可以轻而易举地获得接近百分之百的故障覆盖率，而这些组合电路ATPG算法

23、的复杂性也要远远低于时序电路的ATPG算法。同时由于全扫描方法具有很好的结构化，因此采用全扫描的可测性设计方法，可以以比较低的测试设计代价完成复杂时序电路的处理，并获得满意的故障覆盖率。基于扫描的测试方法同样也有其不足之处。扫描设计需要增加一定的硬件资源来完成扫描寄存器的插入。同时串行的扫描链结构也是缩短测试时间的瓶颈。这些因素对于扫描方法的应用造成了一些负面影响。上述所讨论的基于扫描的可测性设计方法和非扫描方法都是通过对电路施加特定的测试向量，使得电路内部节点上的故障，例如固定为0/1(stack-at-0/1)故障，可以体现在测试结果向量的逻辑值中，从而可以判断电路是否存在故障。因此可以称

24、之为逻辑响应方法。这类方法是目前最为成熟、适用范围最广的一类可测性设计方法。在它们的基础上又根据不同系统对测试性能要求衍生出众多的可测性设计方法。如基于扫描的全扫描设计、部分扫描设计、以及内建自测试等等。除了传统的通过电路的逻辑响应来判断电路故障情况的方法外，还有一些其他的测试方法可以用来检测电路内部是否存在故障。IDDQ测试方法就是另一类较为常见集成电路测试方法。它通过检测电路在特定状态下的静态工作电流来检测电路的内部故障。它可以有效地检测到非固定故障，如桥接故障等。但是当集成电路工艺技术进入深亚微米阶段后，由于亚阈值电流的干扰，通过检测IDDQ电流判断晶体管是否存在故障变得越来越困难。1.

25、2 BIST的测试方法可测性设计中的内建自测试方法(Built-In Self-Test，简称BIST)通过在芯片内部集成少量的逻辑电路实现对整个电路的测试，被认为是解决电路测试问题的有效方法之一。随着芯片集成度的提高，集成电路工程师已不太在乎BIST逻辑所占用的少量的芯片面积，因此BIST已被广泛应用于现代的集成电路中。现代芯片的规模增长迅速，但是管脚数量并没有按比例增长，造成测试的可控制性(controllability)和可观测性(observability)不高。同时芯片密度增高，频率提升，也造成测试困难，在测试领域，全速率测试一向是比较困难的，更何况是一块复杂的SOC芯片。规模巨大的

26、芯片即使是采用DFT的扫描方法进行测试，由于扫描链的长度很长并且扫描链的数量也很多，还是需要很长的单芯片测试时间。高级测试仪器的价格急速攀升，即使是租用的，租金也非常昂贵。在芯片的设计流程中，经常发生的事情是，前端设计人员与测试人员的交流甚少，前端设计人员对功能很清楚，但是并不是很了解测试的领域，造成测试的困难，这也是一个障碍。另外，工业界中高级测试工程师比较短缺，然而测试的地位却变得越来越重要。所以必须要有新的测试技术，目的为了简化测试方法、提高测试效率。BIST即片内自测试的方法便应运而生。这是一种在芯片中增加一些专门为满足测试的电路和结构，由芯片内部产生测试的激励并且分析被测电路的响应，

27、绝大部分的测试工作可以在芯片内部自动地完成。另外也有的BIST方法需要外界进行控制来半自动的进行，但是最主要的工作还是由芯片内部的BIST电路完成测试。BIST的好处在于极大的减小了对测试仪器的依赖性。前面我们分析过，高端的测试仪的成本激增，以至于测试成本占芯片的总体成本越来越大，大规模芯片的设计者和生产者都难以承受如此高昂的开销。BIST的使用，可以减少单芯片的测试时间，简化了测试向量生成的成本，减少了测试向量的存储空间和成本。这样可以使用低中档的测试仪来完成大规模SoC芯片的测试。另外，BIST技术还被用在系统的自动检测、自动诊断、自动恢复这些方面，比如卫星、地下探测等领域。除了以上一些好

28、处之外，BIST还能够提供以往测试的方法难以达到的目的，比如能够更方便做全速测试。以往的全速测试一种是用功能验证的向量，在不同的测试机上用不同的频率来不断地测试芯片，直到该芯片的工作速度不能达到某个频率为止。另一种方法是用静态时序分析工具和ATPG工具共同产生基于延迟模型的测试向量，方法是用时序分析工具选择一些关键的时延路径，并对其产生多种不同的延迟模型，然后用ATPG的工具依据模型产生多套测试向量，在测试的时候，依次从低到高地测试芯片的这些被选择出的关键路径，挑选出能够通过某些级别测试的芯片，那么能够运行在高速的芯片卖到高的价钱。这里看到，以往的全速测试中，芯片的时钟一般是由测试仪加给芯片的

29、也有的测试可以利用芯片内部的时钟生成电路如PLL的时钟，但必须要有精准的对PLL的控制。高速的测试仪更是价格不菲。所以，全速测试的代价是昂贵的，只有在某几个特殊的对频率非常敏感的领域才需要去做，比如CPU, DSP等。但是如果运用BIST的方法，其内部的被测电路的时钟可以由内部时钟产生电路供给，并且可以由内部控制，被测电路输入输出也是在内部控制的，这样可以简单地实现全速测试，这里需要指出的是，利用BIST方法做全速测试依然是比较复杂的，难点还是在于内部时钟的产生和精确的控制上面，但是只是其好处在于极大地减小了对高级测试仪的依赖。目前虽然基于扫描和ATPG的方法进行测试还是比较主流的方法，但是

30、它已经逐渐不能适应SoC芯片的领域了，由于SoC芯片规模巨大，内部的寄存器数量极多，如果用扫描方法，需要既多又长的扫描链，同时测试向量集也非常庞大，这样测试时间就很长，同时必须要使用大型的测试仪才能存储下那么多的测试向量。与此相比，BIST方法在芯片自测试、现场测试、延迟故障测试、全速测试、非入侵性测试等方面具有很多优点。表1.14分析了以往SCAN/ATPG的方法和BIST方法的区别，通过此表可以看出在现代SoC芯片的测试领域，BIST测试方法占有绝对优势。表1. 1 SCAN/ATPG的方法和BIST方法的区别图1.14给出了存储器BIST的典型结构。其中，测试向量生成器可以由线性反馈移位

31、寄存器或计数器来实现，根据测试的类型产生地址序列，测试控制单元通常是一个有限状态机，根据测试算法初始化一些命令和数据等输入作用到被测存储器上，存储器的测试输出结果传送到数据压缩器，经压缩后生成测试特征值，它连同一个预先定义的基准特征值一起送入比较器中进行一致性比较5。图1. 1 典型的存储器BIST结构框图 20世纪80年代，BIST开始应用于嵌入式存储器当中，早期工作主要侧重于测试算法的改进方面。例如1986年Jai n等人在分析了测试向量需求、数据压缩比较及测试生成算法后，提出了嵌入式存储器的两种自测试方案。它们都是用二进制计数器来产生地址码、数据输入及控制信号。但计数器设置不同。方案一是

32、用计数器产生的地址作为写存储器该地址的数据，结果输出到并行向量特征值寄存器进行观测比较;方案二是针对藕合故障的改进，用棋盘算法，结果输出到比较器进行压缩比较6。早期嵌入式存储器BIST用的较多的是伪随机测试向量。例如，1984年Sun等提出用伪随机向量生成器产生地址序列，1989年David等人提出了RAM的伪随机测试方案。但它们都不能检测模式敏感故障，而且硬件开销大，因为存储器的所有输入数据都要送到输出端进行比较7。伪随机测试向量对逻辑电路的测试很有效，但存储器规则的结构特征需要规则的测试向量。当今存储器GIST主要采用确定性测试向量，如MARCH测试。有限状态机和微代码是产生确定性测试向量

33、的两项主要技术。但有限状态机只能产生预先确定的测试向量，即使是可编程有限状态机的灵活性也很有限，修改测试向量就需要重新设计BIST电路。微代码BIST是一种可编程BIST，可以容易地修改测试向量。例如，1998年Dreibelbis等人提出的基于微处理器的嵌入式DRAMBIST方案，1999年Huang等人提出嵌入式DRAM的可编程BIST方案，用户可以通过编程更改测试向量。2003年Appello等人将可编程BIST方法应用到P1500compliant核的工业设计流程中，并由STMicroelectronics公司加以实现。通过处理器控制嵌入式SRAM的测试向量，不仅支持检测还支持诊断近年

34、研究热点集中在减小故障检测延迟、在线并发测试、全速测试及可靠性改进等方面。BISD(built-inself-diagnosis，内建自诊断)、BIRA(built-in redundancy analysis，内建冗余分析)、BISR(built-in self-repair，内建自修复)等高性能设计技术被用到了存储器的BIST之中8。随着半导体工艺尺寸不断缩小，嵌入式存储器可能存在的故障类型越来越多，使得测试时间和测试成本都急剧增长。合理的故障模型对于存储器的测试至关重要，一种测试方法的故障覆盖率、测试长度等质量指标与所用的故障模型有很大的关系。第二章 存储器的故障模型2.1 存储器故障分

35、类研究存储器的检测方法，就必须先建立存储器单元的故障模型，也就是要求把物理故障模型化为逻辑故障，通常可以用功能模型或灰匣子模型将存储器故障模型化，典型RAM功能模型如图2.1所示，该模型是由Vande Goor提出的简化功能DRAM模型2。图2. 1 DRAM功能模型对于图2.1的功能模型，存储器的故障主要表现有3类：（1）地址解码器故障（AF）1，主要表现为4种形式（如图2.22所示）。图2. 2 地址解码器的常见故障（2）读写逻辑模块故障。主要表现为在读写电路中，某些检测放大器的出或者写入驱动器的逻辑部分，可能产生开路、短路或者I/O固定的故障，在读写电路的数据线之间存在交叉耦合的干扰。（

36、3）存储单元阵列故障，由于存储单元阵列是存储器内规模最为复杂的一个模块，因此出现故障的概率最大，故障的类型也最为复杂，主要是由于存储器单元内的数据线开路、短路以及串扰所引起的。对于上述的功能模型去掉其中的某些逻辑模块，就可用于ROM的测试。2.2存储单元的简化功能故障基于以上各模块的故障表现形式，又由于地址译码故障和读写逻辑故障可以等效的功能映射为存储器单元阵列故障，故可把存储器故障简化为下列四种功能故障9：（1）固定故障（stuck-At Fault，SAF）单元或连线的逻辑值总为0或总为1的故障，单元/连线总是处于有故障的状态，并且故障的逻辑值不变。（2）转换故障（Transition F

37、ault，TF）转换故障是SAF的一种特殊情况，当写数据时，某一存储单元失效使得01转变或10转变不能发生，表现为固定故障的形式。（3）耦合故障（Coupling Fault，CF）存储单元中某些位的跳变导致其他位的逻辑发生非预期的变化，它既可以发生在不同单元之间，也可以发生在同一单元不同位之间。（4）相邻矢量敏化故障（Neighborhood Pattern Sensitive Faults，NPSF）一个单元因相邻单元的活动导致状态不正确，一个单元的相邻单元可能有5个，也可能有9个，如图2.32的(a)、(b)所示。图2. 3 相邻图形敏感故障2.3存储器故障诊断算法分析针对存储器故障模型

38、中的各种故障，人们提出了各种诊断算法，目前主要使用的算法有：Checkerboard算法（棋盘法）、Gallop算法（奔跳法）、MARCH算法（进行法）等10。2.3.1 Checkerboard算法（棋盘法）棋盘法的测试过程是首先对每一个存储单元赋值，使得每一个单元与其紧相邻的各个单元的值都不同，如图2.411所示，即把整个存储阵列分为两块a、b，然后采用如下过程对a、b进行读写；（1）对分块a（b）中的单元写0（1）；（2）读所有单元；（3）对分块a（b）中的单元写1（0）；（4）读所有单元；（5）该算法理论上操作的次数是O（N），其中N为存储器容量，可以检测SAF故障和相邻单元的桥接故障

39、其故障覆盖率较低。图2. 4 棋盘法2.3.2 Gallop算法（奔跳法）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）在整个阵列中漫游一样，图2.513表示1漫游的情况，该算法具有较高的故障覆盖率，能检测SAF故障、TF故障以及CF故障，单位该算法操作次数是O（N2）需要较长的测试时间。图2. 5 奔跳法2.3.3 MAR

40、CH算法（进行法）（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。2.3.4基于棋盘算法的改进通过研究和对比上述3个算法发现，Checkerboard（棋盘）算法和MARCH算法以线性方式进行读写，因此存储器操作次数与存储器容量N成正比，Gallop算法虽然有较高的故障覆盖率，但由于其对存储器刺激次数过多，因此，在实际测试中不是一种很经济的测试算法，Checkerboard算法只实现了01或

41、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两个读写状态，就可以测试出变迁故障，写改进后Checke

42、rboard算法对存储器的操作次数为5N次，而MARCH算法对存储器的操作次数则需要6N次，大大地节省了测试时间。以一个X（行地址）、Y（列地址）地址复用的128128的存储器矩阵为例，按改进后的算法编写的测试图形片断如图2.66。图2. 6 按改进后算法编写的图形片断实际的算法图形要配合读写的时序，因此图形更为复杂，但对存储器的操作次数与理论是一致的，改进的Checkerboard算法虽然使用了较少的存储器操作次数，但其只能诊断出部分AF故障，与MARCH算法相比，是以牺牲故障覆盖率为代价来提高测试速度的。在实际的生产型测试中，地址译码模块由于结构较存储矩阵要简单得多，因此出现故障的概率远远

43、小于存储矩阵，且改进的Checkerboard算法也能诊断部分的AF故障，是一种经济的测试算法16。第三章MARCH算法详细叙述3.1 ATS和改进的ATS算法(MATS)这些算法能够检测存储器中的卡住故障。ATS (Algorism Test Sequence)由Kanizuk在1977年提出，后来Nair在1979年对其进行了改进，并更名为MATS。此算法对卡住故障能提供最短的齐步测试。后来Abadir又做了进一步改进，称为MATS+算法。3.1.1 MATS算法（w0）；（r0，w1）； （r1） M0 M1 M2 算法包括四步操作：先写“0”（初始化）；按地址递增的顺序进行以下操作：读

44、0”，写“1”；按地址递减的顺序进行以下操作：读“1”。3.1.2 MAT S+算法（w0）；（r0，w1）； （r1，w0） M0 M1 M2 算法包括五步操作：先写“0”（初始化）；按地址递增的顺序进行以下操作：读“0”，写“1”；按地址递减的顺序进行以下操作：读“1”，写“0”。3.1.3 MATS+算法（w0）；（r0，w1）； （r1，w0，r0） M0 M1 M2 算法包括六步操作：先写“0”（初始化）；按地址递增的顺序进行以下操作：读“0”，写“1”；按地址递减的顺序进行以下操作：读“1”，写“0”，再读“0”。3.2 MARCH A和MARCH B算法MARCH A和MARC

45、H B算法能覆盖一些复合故障，例如:等幂耦合故障和转换故障的复合故障;倒置耦合故障和等幂耦合故障的复合故障等。3.2.1 MARCH A算法（w0）；（r0，w1，w0，w1）；（r1，w0，w1）； M0 M1M2 （r1，w0，w1，w0）；（r0，w1，w0）M3 M4算法包括十五步操作：先写“0”（初始化）；按地址递增的顺序进行以下操作：读“0”，写“1”，写“0”，写“1”；读“1”，写“0”，写“1”；按地址递减的顺序进行以下操作：读“1”，写“0”，写“1”，写“0”；读“0”，写“1”，读“0”。3.2.2 MARCH B算法（w0）；（r0，w1，w0，r0，w1）；（r1，w0，w1）； M0 M1 M2 （r1，w0，w1，w0）；（r0，w1，w0）M3 M4算法包括十六步操作：先写“0”（初始化）；按地址递增的顺序进行以下操作：读“0”，写“1”，写“0”，读“0”，写“1”；读“1”，写“0”，写“1”；按地址递减的顺序进行以下操作：读“1”，写“0”，写“1”，写“0”；读“0”，写“1”，读“0”。3.3 MARCH C算法1982年在ITC (International Test Conference)上被提出的MARCH C算法，以及它的一些衍生算法目前已成为存储器测试