基于March算法的内存异常检测分析——TBA算法分析-毕业论文

本科毕业论文(科研训练、毕业设计)题 目：基于March算法的内存异常检测分析TBA算法分析姓 名： 学 院：软件学院系：软件工程专 业：软件工程年 级： 学 号： 指导教师： 职称： 年 月厦门大学本科毕业论文摘 要在当今工业，由于生产技术和产品设计提高等原因，每个晶体管的制造成本呈持续下降的趋势，而每个晶体管的测试成本却基本保持不变。因而测试成本在快速追上制造成本，并且将很快超过其制造成本。原因很简单，因为先进的测试设备的价格非常昂贵使得测试成本居高不下。因此，对测试方法和测试算法的改进就成了重中之重。本文从研究系统芯片的可测试性设计理论出发，对可测性设计中的内建自测试方法作了更为深入的研究，并对该领域的研究情况进行了介绍。在此基础之上，本文分析了嵌入式存储器内建自测试技术的相关理论和方法，包括其故障模型与测试算法，重点剖析了March测试算法，并在己有算法(March-TB)的基础上分析了一种改进型的March测试算法March-TBA算法。该算法通过增加六步读(写)操作，不但覆盖了更多的测试过程中可区分的故障类型，增强了故障诊断能力，而且减少了测试所需要的时间。改进后的算法的故障覆盖率更高，从而验证了该算法的有效性。关键词： 可测性设计(DFT) 内建自测试(BIST) 嵌入式存储器 March算法49AbstractIn 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.First of all，the thesis researches the testing design 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 embedded memory，Particularly analyzes the March algorithm. and the thesis puts forward an improved March algorithmMarch-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 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目 录引 言1第一章 存储器测试的发展21.1存储器测试发展动态21.2 BIST的测试方法4第二章 存储器的故障模型82.1 存储器故障分类82.2存储单元的简化功能故障92.3基于嵌入式存储器的故障模型102.4存储器故障诊断算法分析112.4.1 Checkerboard算法（棋盘法）112.4.2 Gallop算法（奔跳法）122.4.3 March算法（进行法）132.4.4基于棋盘算法的改进13第三章March算法介绍163.1 March算法简介163.2 March算法演变183.2.1 ATS和改进的ATS算法（MATS）183.2.2 March A和March B算法183.2.3 March C算法183.2.4 March C+算法193.2.5 March C-算法193.3 March算法处理的故障类型193.3.1单一内存单元故障（Stuck-At Fault，SAF）203.3.2单一内存单元转换故障（Transition Fault，TF）203.3.3耦合故障（Coupling Fault，CF）203.3.4相邻内存单元敏化故障（Neighborhood Pattern Sensitive Fault，NPSF）203.3.5数据保留故障（Data Retention Fault，DRF）20第四章March -TBA算法分析214.1 March-TBA算法的前身214.2 March-TBA算法的主要内容234.3 March-TBA算法的检验成果244.3.1 March-TBA算法对固定故障（SAF）的检测情况254.3.2 March -TBA算法对状态转换故障（TF）的检测264.3.3 March C-算法对翻转耦合故障（CFin）的检测274.3.4 March C-算法对幂耦合故障（CFid）的检测304.3.5 March C-算法对状态耦合故障（CFst）的检测364.4 March-TBA算法的故障覆盖率42第五章 结论44致谢45参考文献46ContentsIntroduction1Charpter 1 Developments Of Memory Testing21.1 Developments Of Memory Testing21.2 Testing Methods Of BIST4Charpter 2 The Fault Mode Of The Memory82.1 The Kinds of Fault Mode Of The Memory82.2 Simplified Fault Of Storage Unit92.3 The Fault Mode Of The SoC Memory102.4 The Analysis Of Memory Testing Algorithm112.4.1 Checkerboard Algorithm（Chessboard）112.4.2 Gallop Algorithm122.4.3 March Algorithm132.4.4 The Improve Base On The Chessboard13Charpter 3 The Introductio Of March Algorithm163.1 Brief Introduction Of March Algorithm163.2 Evolvement Of March Algorithm183.2.1 ATS And Improved ATS Algorithm (MATS)183.2.2 March A和March B Algorithm183.2.3 March C Algorithm183.2.4 March C+ Algorithm193.2.5 March C- Algorithm193.3 The Fault Mode For March Algorithm193.3.1 Stuck-At Fault203.3.2 Transition Fault203.3.3 Coupling Fault203.3.4 Neighborhood Pattern Sensitive Fault203.3.5 Data Retention Fault20Charpter 4 Analysis Of March -TBA Algorithm214.1 Preexistence Of March-TBA Algorithm214.2 Detail Of March-TBA Algorithm234.3 March-TBA Fault Analysis244.3.1 March TBA Algorithm For Stuck-At Fault254.3.2 March TBA Algorithm For Transition Fault264.3.3 March TBA Algorithm For Coupling Fault274.3.4 March -TBA Algorithm For Neighborhood Pattern Sensitive Fault304.3.5 March -TBA Algorithm For Data Retention Fault364.4 The Fault Cover Of March-TBA Algorithm42Charpter 5 Summarize44Acknowledgements45References46引 言随着深亚微米VLSI技术的发展，大量的不同厂家的电路设计被核集成到一个芯片上。存储器密度的增长使存储器的测试面临着更大的挑战。嵌入式RAM存储器是最难测试的电路，因为存储器的测试通常需要大量的测试模式来激活存储器并将存储器的单元内容读出来与标准值进行比较。在可以接受的测试费用和测试时间的限制下，准确的故障模型和有效的测试算法是至关重要的。而为了保证测试时间和故障覆盖率，测试的好坏大大的依赖于所选的功能故障模型。随着集成电路设计方法与工艺技术的不断进步，集成电路的可测性己经成为提高产品可靠性和成品率的一个不可忽视的因素。在近的二十多年中，尤其是最近十年来，电路测试方法的研究日益受到重视，测试问题己经成为了集成电路产品开发的流程中关键问题之一。伴随着电子设备功能和结构日益复杂，“暗箱”方法越来越难以满足需求，因此要求测试人员以更积极的方式介入测试过程，不仅要承担传统测试中激励生成者和响应分析者的角色，而且要作为整个测试过程的主导者和设计者。通过改善被测试对象的设计来提高被测对象的可测试性，从而能更容易找到测试码，并使测试和测试码的生成问题大大简化，这就是可测性设计(DFT)1。第一章 存储器测试的发展1.1存储器测试发展动态自集成电路诞生之日起，设计方法、制造方法和测试方法始终是集成电路发展不可分割的3个组成部分。但在集成电路发展的早期，人们更多的注意力集中在设计和制造领域，而且早期的集成电路逻辑设计与工艺技术相对简单，因此测试方法学的研究曾一度处于不被重视的地位，在当时人们认为可测性设计是可有可无的，是否采用完全由成本预算来决定。可测性设计是在1970年Cherry Hill测试会议上提出的，然而可测性设计的必要性直至上个世纪70年代中期随着集成电路设计的发展才逐渐被人们认识。随后关于可测性设计设计方面的论文和研究成果越来越多，目前在一些重要的国际会议上，如国际测试会议(ITC),国际设计自动化会议(DAC)等都有专门的分组会。此外，一些可测性设计的规则已经成为集成电路设计的工业标准，如IEEE1149. 1标准等。可测性设计己经成为集成电路设计领域一个极其重要的组成部分21。在过去的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.14分析了以往SCAN/ATPG的方法和BIST方法的区别，通过此表可以看出在现代SoC芯片的测试领域，BIST测试方法占有绝对优势。表1. 1 SCAN/ATPG的方法和BIST方法的区别图1.14给出了存储器BIST的典型结构。其中，测试向量生成器可以由线性反馈移位寄存器或计数器来实现，根据测试的类型产生地址序列，测试控制单元通常是一个有限状态机，根据测试算法初始化一些命令和数据等输入作用到被测存储器上，存储器的测试输出结果传送到数据压缩器，经压缩后生成测试特征值，它连同一个预先定义的基准特征值一起送入比较器中进行一致性比较5。图1. 1 典型的存储器BIST结构框图 20世纪80年代，BIST开始应用于嵌入式存储器当中，早期工作主要侧重于测试算法的改进方面。例如1986年Jain等人在分析了测试向量需求、数据压缩比较及测试生成算法后，提出了嵌入式存储器的两种自测试方案。它们都是用二进制计数器来产生地址码、数据输入及控制信号。但计数器设置不同。方案一是用计数器产生的地址作为写存储器该地址的数据，结果输出到并行向量特征值寄存器进行观测比较;方案二是针对藕合故障的改进，用棋盘算法，结果输出到比较器进行压缩比较6。早期嵌入式存储器BIST用的较多的是伪随机测试向量。例如，1984年Sun等提出用伪随机向量生成器产生地址序列，1989年David等人提出了RAM的伪随机测试方案。但它们都不能检测模式敏感故障，而且硬件开销大，因为存储器的所有输入数据都要送到输出端进行比较7。伪随机测试向量对逻辑电路的测试很有效，但存储器规则的结构特征需要规则的测试向量。当今存储器GIST主要采用确定性测试向量，如March测试。有限状态机和微代码是产生确定性测试向量的两项主要技术。但有限状态机只能产生预先确定的测试向量，即使是可编程有限状态机的灵活性也很有限，修改测试向量就需要重新设计BIST电路。微代码BIST是一种可编程BIST，可以容易地修改测试向量。例如，1998年Dreibelbis等人提出的基于微处理器的嵌入式DRAMBIST方案，1999年Huang等人提出嵌入式DRAM的可编程BIST方案，用户可以通过编程更改测试向量。2003年Appello等人将可编程BIST方法应用到P1500compliant核的工业设计流程中，并由ST Microelectronics公司加以实现。通过处理器控制嵌入式SRAM的测试向量，不仅支持检测还支持诊断近年研究热点集中在减小故障检测延迟、在线并发测试、全速测试及可靠性改进等方面。BISD(Built-In Self-Diagnosis，内建自诊断)、BIRA(Built-In Redundancy Analysis，内建冗余分析)、BISR(Built-In Self-Repair，内建自修复)等高性能设计技术被用到了存储器的BIST之中8。随着半导体工艺尺寸不断缩小，嵌入式存储器可能存在的故障类型越来越多，使得测试时间和测试成本都急剧增长。合理的故障模型对于存储器的测试至关重要，一种测试方法的故障覆盖率、测试长度等质量指标与所用的故障模型有很大的关系。第二章 存储器的故障模型2.1 存储器故障分类研究存储器的检测方法，就必须先建立存储器单元的故障模型，也就是要求把物理故障模型化为逻辑故障，通常可以用功能模型或灰匣子模型将存储器故障模型化，典型RAM功能模型如图2.1所示，该模型是由Vande.Goor提出的简化功能DRAM模型2。图2. 1 DRAM功能模型对于图2.1的功能模型，存储器的故障主要表现有3类：（1）地址解码器故障（AF）1，主要表现为4种形式（如图2.22所示）。图2. 2 地址解码器的常见故障（2）读写逻辑模块故障。主要表现为在读写电路中，某些检测放大器的出或者写入驱动器的逻辑部分，可能产生开路、短路或者I/O固定的故障，在读写电路的数据线之间存在交叉耦合的干扰。（3）存储单元阵列故障，由于存储单元阵列是存储器内规模最为复杂的一个模块，因此出现故障的概率最大，故障的类型也最为复杂，主要是由于存储器单元内的数据线开路、短路以及串扰所引起的。对于上述的功能模型去掉其中的某些逻辑模块，就可用于ROM的测试。2.2存储单元的简化功能故障基于以上各模块的故障表现形式，又由于地址译码故障和读写逻辑故障可以等效的功能映射为存储器单元阵列故障，故可把存储器故障简化为下列四种功能故障9：（1）固定故障（stuck-At Fault，SAF）单元或连线的逻辑值总为0或总为1的故障，单元/连线总是处于有故障的状态，并且故障的逻辑值不变。（2）转换故障（Transition Fault，TF）转换故障是SAF的一种特殊情况，当写数据时，某一存储单元失效使得01转变或10转变不能发生，表现为固定故障的形式。（3）耦合故障（Coupling Fault，CF）存储单元中某些位的跳变导致其他位的逻辑发生非预期的变化，它既可以发生在不同单元之间，也可以发生在同一单元不同位之间。（4）相邻矢量敏化故障（Neighborhood Pattern Sensitive Faults，NPSF）一个单元因相邻单元的活动导致状态不正确，一个单元的相邻单元可能有5个，也可能有9个，如图2.32的(a)、(b)所示。图2. 3 相邻图形敏感故障2.3基于嵌入式存储器的故障模型根据嵌入式存储器的结构和工艺特点，我们把具体的工艺鼓掌抽象为行为级模型方便设计相应的模块来进行测试。对于嵌入式存储器，故障的行为模型主要有5种，分别是：固定故障、状态转换故障、耦合故障、图形敏感故障、寻址故障。2.3.1固定故障（SAF Stuck-At Fault）：固定故障是存储器的某个单元或某条线固定为逻辑0或者逻辑1上不变。此类故障较为简单，各种MARCH算法都能检测得出。2.3.2 状态转换故障（TF Transition Fault）：也称为跳变故障，是固定故障中的一个特殊情况，指某个单元或某条线在通过一个写操作以后不能实现0到1或者1到0的转换，分别叫做上升状态转换故障和下降状态转换故障。可由MATS+算法、March X算法、March C算法、March A算法、March Y算法、March B算法检测出来。2.3.3 耦合故障（CF Coupling Fault）：耦合故障是指在两个单元当中，由于一个单元的状态转换而致使另外一个单元的内容发生了变化。这叫做2耦合故障，就是只涉及两个单元；还有K耦合故障。K耦合故障有是两个单元之间的耦合，但只有当另外（k-2）个单元处于某种状态时，故障才会发生。耦合故障具体还有下列5种模型：1、翻转耦合故障（Inversion Coupling Fault）:是指一个单元中上升沿跳变或下降沿跳变会引起另一个单元内容的翻转。此类是耦合故障中较为简单的，March X算法、March C算法、March A 算法、March Y算法、March B算法检测出。 2、幂耦合故障（Idempotent Coupling Fault）:是指一个单元中上升沿跳变或下降沿跳变会迫使另一个单元内容置0或置1。可由March C算法检测出。 3、动态耦合故障（Dynamic Coupling Fault）:是幂耦合故障中的一种特殊情况，是指当一个单元发生读或写操作后，迫使另一个单元的内容为0或1。可由March C算法检测出。 4、桥联故障（BF Bridging Fault）:是由两个或多个单元或线短路所引起的，分为与桥联故障和或桥联故障。与桥联故障的逻辑值是两个桥联单元逻辑值的与；或桥联故障情况亦然。可由March C算法检测出。 5、状态耦合故障（SCF State Coupling Fault）:是指一个单元处于某个状态值时，另一个耦合单元被置为0或1的故障。可由March C算法检测出。2.3.4 图形敏感故障（PSF Pattern sensitive Fault）：图形敏感故障是一种特殊的状态耦合故障。图形敏感故障意味着在部分存储器出现一些特定的数据时，其他部分存储器的数据会受到影响。2.3.5 寻址故障（AF Address decoder Fault）：寻址故障行或列译码器可能访问不到寻址的单元；或者多个地址访问 同一个存储单元；或者一个地址同时访问多个单元；或不访问所指定的单元而访问其他的单元。MATS算法能检测出部分，改进了的MATS算法（MATS+）以及其他的各种March算法都能检测出此故障11。2.4存储器故障诊断算法分析针对存储器故障模型中的各种故障，人们提出了各种诊断算法，目前主要使用的算法有：Checkerboard算法（棋盘法）、Gallop算法（奔跳法）、March算法（进行法）等10。2.4.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故障和相邻单元的桥接故障，其故障覆盖率较低。图2. 4 棋盘法2.4.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.4.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。2.4.4基于棋盘算法的改进通过研究和对比上述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的存储器矩阵为例，按改进后的算法编写的测试图形片断如图2.66。实际的算法图形要配合读写的时序，因此图形更为复杂，但对存储器的操作次数与理论是一致的，改进的Checkerboard算法虽然使用了较少的存储器操作次数，但其只能诊断出部分AF故障，与March算法相比，是以牺牲故障覆盖率为代价来提高测试速度的。在实际的生产型测试中，地址译码模块由于结构较存储矩阵要简单得多，因此出现故障的概率远远小于存储矩阵，且改进的Checkerboard算法也能诊断部分的AF故障，是一种经济的测试算法16。图2. 6 按改进后算法编写的图形片断第三章March算法介绍3.1 March算法简介March算法具有较高的故障覆盖率和较少的时间复杂度等特点，所以它在嵌入式存储器测试中最为常用。传统的存储器测试算法的算法复杂度为0 (n)或0 (n) (n表示存储单元数目)，对于大容量的SRAM，将导致很长的测试时间17。 March测试由于其算法复杂度为0 (n)而成为目前广泛使用的存储器测试算法。该算法的基本原理是利用有限状态机，对所有的地址逐个进行读写操作。算法的指令比较简单，只有读写0/1和地址变化的指令，通过对存储器不断地读写，能够检测几乎所有的存储器故障。首先队March算法做简要介绍，为方便起见，先定义一些符号代表March算法所涉及的存储器操作方式：图3. 1 March算法操作符测试过程中，March算法以不同的方式（如地址递增或地址递减方式）遍历存储器的每个存储单元，并且在每次遍历过程中对所有存储单元进行同样的操作（在不同的遍历过程中对存储单元的操作方式可以不同）。不同的遍历方式和存储单元操作方式能检测到的故障类型是不同的，所需要的测试时间也是不同的，根据存储器的遍历方式和存储单元的操作方式，March算法又可以细分为MATS、MATS、MATS、March X、March C-、MarchA、March Y等算法，这些算法的测试流程如表3.1所示表3. 1 各种March算法的测试流程18在各种测试方案中，首先对单个单元进行一系列的操作，然后才进行下个单元的操作。操作序列称为March单元(March Element)，一个March单元可能包括一组简单的MSCAN序列，也可能包括一组复杂的，带有多个读/写操作的操作序列。基本的March算法如上表所示。由于是对单个单元进行读/写操作，因此其读/写操作的复杂度为0 (mn)。这里m为步进单元中的读/写操作数目。这种算法的故障覆盖率相当好，可以包括单元固定、状态跳变以及大量的NPSF和耦合故障。由于存储器的故障类型及其多样，某种算法并不是都能够测到所有的故障。下表列举了不同的算法能够检测到的故障类型。表3. 2 各种March算法能够检测到的故障类型193.2 March算法演变3.2.1 ATS和改进的ATS算法（MATS）这些算法能够检测存储器中的卡住故障。ATS (Algorism Test Sequence)由Kanizuk在1977年提出，后来Nair在1979年对其进行了改进，并更名为MATS。此算法对卡住故障能提供最短的齐步测试。后来Abadir又做了进一步改进，称为MATS+算法。3.2.2 March A和March B算法March A和March B算法能覆盖一些复合故障，例如:等幂耦合故障和转换故障的复合故障;倒置耦合故障和等幂耦合故障的复合故障等。3.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算法可以检测固定故障，跳变故障以及大部分的藕合故障。3.2.4 March C+算法March C+算法是改进后的March C算法，在齐步的每一级增加了一次读操作，使它能够覆盖Stuck-Open故障，即前面提到的开路故障是由于MOS管的缺陷等原因造成在某个特定向量输入时，逻辑门的输出端为不期望发生的高阻态。通常发生在控制或译码电路中，对此种故障的覆盖率与输入向量的先后次序有很大关系，因此在每步增加一次读操作可大大提高对此种故障的覆盖率。另外March C+算法同样可检测固定型故障、转换故障以及耦合故障。可见，它是一种很适合检测存储器的算法。3.2.5 March C-算法March C-算法是对March C算法的修正，去掉了第四步的读“0”操作，使总的操作步骤减少到10步，同时并没有降低错误覆盖率，可检测和March C相同的故障类型。March C-测试算法是其它算法的基础，各单元均得到执行，同时单元地址按递增或递减方式提供。表3. 3 各种March算法的复杂度193.3 March算法处理的故障类型首先我们都知道嵌入式内存由地址译码逻辑，读写控制逻辑和内存阵列组成。所以先对嵌入式内存阵列故障做一下细分，它是专指在存储单元中的故障，它有如下五种故障模型：3.3.1单一内存单元故障（Stuck-At Fault，SAF）故障单元的逻辑值被常置为逻辑0（SAF（0）或逻辑1（SAF（1）。3.3.2单一内存单元转换故障（Transition Fault，TF） 故障单元不能进行由0到1（ /0）故障）或者由1到0的转换（/1）障）。3.3.3耦合故障（Coupling Fault，CF）CF故障又可以细分为三种故障类型：1倒置耦合故障（Inversion Coupling Fault，CFin），一个内存单元的写0或写1操作将使另一内存单元的逻辑值倒置，有两种倒置耦合故障：CFin(;)，CFin(;)，其中表示内存单元的值倒置。2固化耦合故障（Idempotent Coupling Fault，CFid），一个内存单元的写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）。3.3.4相邻内存单元敏化故障（Neighborhood Pattern Sensitive Fault，NPSF）一个内存单元的状态受它邻近内存单元的状态或者状态变化的影响。3.3.5数据保留故障（Data Retention Fault，DRF）数据保留故障（Data Retention Fault，DRF），内存单元逻辑值经过一些周期由于漏电而改变。第四章March -TBA算法分析4.1 March-TBA算法的前身March C-算法的诊断能力比较差，并且它不能检测DRF故障（跳变型故障）。为了改善算法的故障诊断能力并探测DRF故障，有人提出了March -TB算法，。比较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故障。此算法的测试流程如