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

厦门大学软件学院-毕业论文 1 本科毕业论文本科毕业论文 (毕业设计) 题题 目：基于目：基于 MARCH 算法的内存异常检测研算法的内存异常检测研 究究 -MARCH-TB 及及 MARCH-Y 算法分析算法分析 姓 名： 学 院：软件学院软件学院 系：软件工程软件工程 专 业：软件工程软件工程 年 级： 学 号： 指导教师（校内）： 职称： 年 月 厦门大学软件学院-毕业论文 I 摘摘 要要 在当今工业，由于生产技术和产品设计提高等的原因，每个晶体管的制造成本呈持续下 降的趋势，而每个晶体管的测试成本却基本保持不变。因而测试成本在快速追上制造成本， 并且将很快超过其制造成本。原因很简单，因为先进的测试设备的价格非常昂贵使得测试成 本居高不下。因此，对测试方法和测试算法的改进就成了重中之重。 本文从研究系统芯片可测试性设计理论出发，从对可测试性设计的内建自测试方法的研 究中找寻对内存测试方法的有益论点。然后，分析存储器和存储单元的故障类型，思考他们 的特点，进而比较各种当前较常用的算法，详细分析 MARCH 算法的特性，探寻对 MARCH 算法的改进。在文章的下半部份以便于学者及研究人员对 MARCH 算法的研究和改进为目 标，分析设计了一个以 MARCH 算法为基础的内存检测系统，并对系统的重点和难点进行 了详细分析。 本文包括了对内存故障模型和内存测试算法的分析，并主要对所设计的 Windows 和 DOS 版内存检测系统进行介绍，分别列出了其详细设计，和运行效果，并就各种 MARCH 算法所提供的测试向量进行了分析比较。 关键词：关键词：MARCH 算法 存储器 内存异常检测 BIST 厦门大学软件学院-毕业论文 II AbstractAbstract 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 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. 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. Keywords: MARCH Algorithm ，Memory， Memory Anomaly Detection ，BIST 厦门大学软件学院-毕业论文 III 目目 录录 摘要摘要.II 引引 言言.1 第一章第一章 存储器测试的发展存储器测试的发展 2 1.11.1 存储器测试发展动态存储器测试发展动态.2 1.21.2 BISTBIST 的测试方法的测试方法.4 第二章第二章 存储器的故障模型存储器的故障模型 8 2.12.1 存储器故障分类存储器故障分类8 2.22.2 存储单元的简化功能故障存储单元的简化功能故障.9 2.3 存储器故障诊断算法分析存储器故障诊断算法分析9 2.3.1 Checkerboard 算法（棋盘法）.10 2.3.2 Gallop 算法（奔跳法）.10 2.3.3 MARCH 算法（进行法）.11 2.3.4 基于棋盘算法的改进.11 第三章第三章 MARCHMARCH 算法详细叙述算法详细叙述.15 3.13.1 ATSATS 和改进的和改进的 ATSATS 算法算法(MATS)(MATS).15 3.1.1 MATS 算法.15 3.1.2 MAT S+算法15 3.1.3 MATS+算法16 3.23.2 MARCHMARCH A A 和和 MARCHMARCH B B 算法算法.16 3.2.1 MARCH A 算法.17 3.2.2 MARCH B 算法.17 3.33.3 MARCHMARCH C C 算法算法.18 3.3.1 MARCH C 算法.18 3.3.2 MARCH C+算法19 3.3.3 MARCH C-算法20 3.43.4 其它其它 MARCHMARCH 算法算法.20 3.4.1 MARCH X 算法.20 3.4.2 MARCH-TBA 算法.21 3.4.3 MARCH SS 算法.22 3.53.5 小结小结.23 厦门大学软件学院-毕业论文 IV 第四章第四章 MARCH-TBMARCH-TB 和和 MARCH-YMARCH-Y 算法算法27 4.14.1 MARCHMARCH TBTB 算法思想及内容算法思想及内容.27 4.1.1 MARCH-TB 算法的故障检测能力.28 4.1.2 对 SAF 故障分析30 4.1.3 对 TF 分析.30 4.1.4 对 CF 故障分析31 4.1.5 对 DRF 故障分析.33 4.24.2 MARCH-YMARCH-Y 算法算法.33 4.2.1 MARCH-Y 算法及其检测能力.33 4.2.2 对 SAF 故障34 4.2.3 对 TF 故障.35 4.2.4 对 CFin 故障35 第五章第五章 总结总结37 致谢致谢.38 参考文献参考文献 .39 厦门大学软件学院-毕业论文 V Contents ABSTRACTII INTRODUCTION 1 CHAPTER I OF THE DEVELOPMENT OF MEMORY TEST.2 1.1 Memory test developments2 1.2 BIST testing methods4 CHAPTER II MEMORY FAULT MODEL8 2.1 Memory fault classification8 2.2 Storage units feature a simplified fault.9 2.3 Memory fault diagnosis algorithm of 9 2.3.1 Checkerboard algorithm (The board).10 2.3.2 Gallop algorithm (Ben jump) .10 2.3.3 MARCH algorithm (a)11 2.3.4 based on the chessboard of the algorithm to improve 11 CHAPTER III MARCH ALGORITHM DESCRIBED IN DETAIL.15 3.1 ATS ATS and improve the algorithm (MATS)15 3.1.1 MATS algorithm.15 3.1.2 MAT S + algorithm.15 3.1.3 MATS + + algorithm16 3.2 MARCH A algorithm and MARCH B16 3.2.1 MARCH A algorithm17 3.2.2 MARCH B algorithm17 3.3 MARCH C algorithm.18 3.3.1 MARCH C algorithm18 3.3.2 MARCH C + algorithm19 3.3.3 MARCH C-algorithms .20 3.4 Algorithm other MARCH .20 3.4.1 MARCH X algorithm20 3.4.2 MARCH-TBA algorithm.21 3.4.3 MARCH SS algorithm.22 3.5 Summary.23 厦门大学软件学院-毕业论文 VI CHAPTER IV MARCH-TB ALGORITHM DETAILING.27 4.1 MARCH TB algorithm thinking and content of .27 4.1.1MARCH-TB capacity fault detection algorithm 28 4.1.2 Failure Analysis of the SAF30 4.1.3 Failure Analysis of the TF.30 4.1.4 Failure Analysis of the CF31 4.1.5 Failure Analysis of the DRF.33 4.2 MARCH-Y algorithm.33 4.2.1 MARCH-Y algorithm and its ability to detect.33 4.2.2 Failure Analysis to SAF34 4.2.3 Failure Analysis to TF.35 4.2.4 Failure Analysis to CFin35 CHAPTER V CONCLUDED.37 THANKS.38 REFERENCES .39 厦门大学软件学院-毕业论文 1 引引 言言 随着深亚微米 VLSI 技术的发展，大量的不同厂家的电路设计或核集成到一个芯片上。 存储器密度的增长使存储器的测试面临着更大的挑战。嵌入式 RAM 存储器是最难测试的电 路，因为存储器的测试通常需要大量的测试模式来激活存储器并将存储器的单元内容读出来 与标准值进行比较。在可以接受的测试费用和测试时间的限制下，准确的故障模型和有效的 测试算法是至关重要的。而为了保证测试时间和故障覆盖率，测试的好坏大大的依赖于所选 的功能故障模型。 随着集成电路设计方法与工艺技术的不断进步，集成电路的可测性己经成为提高产品可 靠性和成品率的一个不可忽视的因素。在近的二十多年中，尤其是最近十年来，电路测试方 法的研究日益受到重视，测试问题己经成为了集成电路产品开发的流程中关键问题之一。 伴随着电子设备功能和结构日益复杂， “暗箱”方法越来越难以满足需求，因此要求测 试人员以更积极的方式介入测试过程，不仅要承担传统测试中激励生成者和响应分析者的角 色，而且要作为整个测试过程的主导者和设计者。通过改善被测试对象的设计来提高被测对 象的可测试性，从而能更容易找到测试码，并使测试和测试码的生成问题大大简化，这就是 可测性设计(DFT)1。 厦门大学软件学院-毕业论文 2 第一章第一章 存储器测试的发展存储器测试的发展 1.11.1 存储器测试发展动态存储器测试发展动态 自集成电路诞生之日起，设计方法、制造方法和测试方法始终是集成电路发展不可分割 的 3 个组成部分。但在集成电路发展的早期，人们更多的注意力集中在设计和制造领域，而 且早期的集成电路逻辑设计与工艺技术相对简单，因此测试方法学的研究曾一度处于不被重 视的地位，在当时人们认为可测性设计是可有可无的，是否采用完全由成本预算来决定。 可测性设计是在 1970 年 Cherry Hill 测试会议上提出的，然而可测性设计的必要性直至 上个世纪 70 年代中期随着集成电路设计的发展才逐渐被人们认识。随后关于可测性设计设 计方面的论文和研究成果越来越多，目前在一些重要的国际会议上，如国际测试会议(ITC), 国际设计自动化会议(DAC)等都有专门的分组会。此外，一些可测性设计的规则已经成为集 成电路设计的工业标准，如 IEEE1149. 1 标准等。可测性设计己经成为集成电路设计领域一 个极其重要的组成部分1。 在过去的 20 年乃至更长的时间里，可测性设计方法的研究主要集中在如何协调测试性 能与其所带来的额外代价的折衷关系上。而在整个可测性设计方法学的发展道路上，对于额 外代价的考虑也经历了几个不同的阶段，各个阶段都有其不同的研究侧重点，由此也出现了 相应的各类可测性设计方法。 在集成电路发展的早期，面积是所有产品设计的关键因素，同时由于可测性设计方法始 终是集成电路设计方法的一种补充，因此在那一时期，面积代价成为了研究可测性设计方法 学的核心，增加尽可能少的额外面积也就成为了选择可测性设计方法的主导因素。在此期间 出现的可测性设计方法多以非扫描方法为主，所 i 胃非扫描方法主要是区别于后来出现的扫 描方法而言的。这类方法在写入测试数据时仍然保持电路正常工作时的模式，即所有的测试 数据都是通过功能 I/0 并行写入，一电路内部的工作状态也与正常的工作状态相同。这样的 方法必然会导致电路内部的某些节点难以控制或者难以观测，因此需要增加适当的结构，在 不改变电路逻辑的前提下，提高这些节点的可控性和可观性，例如插入测试点技术、初始化 技术、冗余逻辑等等2。 非扫描可测性设计方法在发展的早期具有突出的优点:它的面积代价小，测试模式与正 常功能模式接近，易于被设计人员理解和接受。但是其设计思想也决定了它具有不可避免的 厦门大学软件学院-毕业论文 3 先天不足。 第一，设计复杂，为了将电路的测试性能提高到所需的范围，经常需要搜索整个设计空 间，并且搜索空间随着电路规模的增加呈级数递增。 第二，需要复杂的自动测试生成(Auto Test Pattern Generation, ATPG)技术，在非扫描 可测性设计方法中，ATPG 算法的优劣对最终能够达到的故障覆盖率有至关重要的影响。 第三，非扫描可测性设计方法在处理复杂时序电路时，其测试向量的效率很难得到保证。 原因是在时序电路中，非扫描方法经常需要采用一组特定的测试向量序列才能控制或观测某 个特定的节点，测试向量序列的长度与节点本身的可测性及可观性密切相关，也就是说与电 路的结构密切相关。因此非扫描方法本身并不能保证其效率。 非扫描可测性方法的这些不足在集成电路规模不大、复杂度不是很高的情况下，由于其 面积代价上的优势，通常比较容易被设计工程师所接受。直接采用功能测试向量进行产品测 试实际上就是非扫描测试方法的雏形。但是随着集成电路规模和复杂度的不断提高，非扫描 可测性技术逐渐无法再满足设计的需要。同时随着集成电路工艺技术的发展，面积代价的比 重也逐渐降低，此时另一种更适于处理复杂电路的可测性设计方法基于扫描的可测性设 计方法逐渐成为了可测性设计方法的主流。 所谓基于扫描的可测性设计方法，其基本的设计思想是将电路内部的存储单元(触发器、 锁存器等时序单元)全部或部分地构建成链式结构，并采用扫描寄存器(Scan Register)来代 替原有的存储单元，由此组成串行的扫描链3。外部的测试数据可以通过指定的测试端口， 在测试控制信号的控制下，串行写入存储单元内。 在基于扫描的可测性设计方法中，全扫描方法，即将所有存储单元都替换为扫描寄存器 的方法，是优点最突出的一种方法。因为如果采用全扫描结构，整个时序电路实际上被转换 成了一个单纯的组合电路来进行测试。而对于组合电路来说，它的可测性问题相对时序电路 要容易分析得多，而且在逻辑设计中也完全有可能避免使用某些难测的组合电路。经过多年 的研究与探索，目前对于一般的组合电路，现有的 ATPG 算法都可以轻而易举地获得接近 百分之百的故障覆盖率，而这些组合电路 ATPG 算法的复杂性也要远远低于时序电路的 ATPG 算法。同时由于全扫描方法具有很好的结构化，因此采用全扫描的可测性设计方法， 可以以比较低的测试设计代价完成复杂时序电路的处理，并获得满意的故障覆盖率。 基于扫描的测试方法同样也有其不足之处。扫描设计需要增加一定的硬件资源来完成扫 描寄存器的插入。同时串行的扫描链结构也是缩短测试时间的瓶颈。这些因素对于扫描方法 的应用造成了一些负面影响。 厦门大学软件学院-毕业论文 4 上述所讨论的基于扫描的可测性设计方法和非扫描方法都是通过对电路施加特定的测试 向量，使得电路内部节点上的故障，例如固定为 0/1(stack-at-0/1)故障，可以体现在测试结 果向量的逻辑值中，从而可以判断电路是否存在故障。因此可以称之为逻辑响应方法。这类 方法是目前最为成熟、适用范围最广的一类可测性设计方法。在它们的基础上又根据不同系 统对测试性能要求衍生出众多的可测性设计方法。如基于扫描的全扫描设计、部分扫描设计、 以及内建自测试等等。 除了传统的通过电路的逻辑响应来判断电路故障情况的方法外，还有一些其他的测试方 法可以用来检测电路内部是否存在故障。IDDQ 测试方法就是另一类较为常见集成电路测试 方法。它通过检测电路在特定状态下的静态工作电流来检测电路的内部故障。它可以有效地 检测到非固定故障，如桥接故障等。但是当集成电路工艺技术进入深亚微米阶段后，由于亚 阈值电流的干扰，通过检测 IDDQ 电流判断晶体管是否存在故障变得越来越困难。 1.21.2 BISTBIST 的测试方法的测试方法 可测性设计中的内建自测试方法(Built-In Self-Test，简称 BIST)通过在芯片内部集成少 量的逻辑电路实现对整个电路的测试，被认为是解决电路测试问题的有效方法之一。随着芯 片集成度的提高，集成电路工程师已不太在乎 BIST 逻辑所占用的少量的芯片面积，因此 BIST 已被广泛应用于现代的集成电路中。 现代芯片的规模增长迅速，但是管脚数量并没有按比例增长，造成测试的可控制性 (controllability)和可观测性(observability)不高。同时芯片密度增高，频率提升，也造成测试 困难，在测试领域，全速率测试一向是比较困难的，更何况是一块复杂的 SOC 芯片。规模 巨大的芯片即使是采用 DFT 的扫描方法进行测试，由于扫描链的长度很长并且扫描链的数 量也很多，还是需要很长的单芯片测试时间。高级测试仪器的价格急速攀升，即使是租用的， 租金也非常昂贵。 在芯片的设计流程中，经常发生的事情是，前端设计人员与测试人员的交流甚少，前端 设计人员对功能很清楚，但是并不是很了解测试的领域，造成测试的困难，这也是一个障碍。 另外，工业界中高级测试工程师比较短缺，然而测试的地位却变得越来越重要。所以必须要 有新的测试技术，目的为了简化测试方法、提高测试效率。 BIST 即片内自测试的方法便应运而生。这是一种在芯片中增加一些专门为满足测试的 电路和结构，由芯片内部产生测试的激励并且分析被测电路的响应，绝大部分的测试工作可 以在芯片内部自动地完成。另外也有的 BIST 方法需要外界进行控制来半自动的进行，但是 厦门大学软件学院-毕业论文 5 最主要的工作还是由芯片内部的 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 测试方法占有绝对优势。 厦门大学软件学院-毕业论文 6 表 1. 1 SCAN/ATPG 的方法和 BIST 方法的区别 图 1.14给出了存储器 BIST 的典型结构。其中，测试向量生成器可以由线性反馈移位寄 存器或计数器来实现，根据测试的类型产生地址序列，测试控制单元通常是一个有限状态机， 根据测试算法初始化一些命令和数据等输入作用到被测存储器上，存储器的测试输出结果传 送到数据压缩器，经压缩后生成测试特征值，它连同一个预先定义的基准特征值一起送入比 较器中进行一致性比较5。 厦门大学软件学院-毕业论文 7 图 1. 1 典型的存储器 BIST 结构框图 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-inself- diagnosis，内建自诊断)、BIRA(built-in redundancy analysis，内建冗余分析)、BISR(built- in self-repair，内建自修复)等高性能设计技术被用到了存储器的 BIST 之中8。 随着半导体工艺尺寸不断缩小，嵌入式存储器可能存在的故障类型越来越多，使得测试 时间和测试成本都急剧增长。合理的故障模型对于存储器的测试至关重要，一种测试方法的 故障覆盖率、测试长度等质量指标与所用的故障模型有很大的关系。 厦门大学软件学院-毕业论文 8 第二章第二章 存储器的故障模型存储器的故障模型 2.12.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 的测试。 厦门大学软件学院-毕业论文 9 2.22.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 存储器故障诊断算法分析存储器故障诊断算法分析 针对存储器故障模型中的各种故障，人们提出了各种诊断算法，目前主要使用的算法有： Checkerboard 算法（棋盘法）、Gallop 算法（奔跳法）、MARCH 算法（进行法）等10。 厦门大学软件学院-毕业论文 10 2.3.12.3.1 CheckerboardCheckerboard 算法（棋盘法）算法（棋盘法） 棋盘法的测试过程是首先对每一个存储单元赋值，使得每一个单元与其紧相邻的各个单 元的值都不同，如图 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.3.22.3.2 GallopGallop 算法（奔跳法）算法（奔跳法） 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），重复以上步骤。 厦门大学软件学院-毕业论文 11 整个过程就像 1（0）在整个阵列中漫游一样，图 2.513表示 1 漫游的情况，该算法具 有较高的故障覆盖率，能检测 SAF 故障、TF 故障以及 CF 故障，单位该算法操作次数是 O（N2）需要较长的测试时间。 图 2. 5 奔跳法 2.3.32.3.3 MARCHMARCH 算法（进行法）算法（进行法） （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.42.3.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）； 厦门大学软件学院-毕业论文 12 （3）读所有单元； （4）对分块 a（b）中的单元写 1（0）； （5）读所有单元。 这样整个存储器就同时经历了由 01 和 10 两个读写状态，就可以测试出变迁故障， 写改进后 Checkerboard 算法对存储器的操作次数为 5N 次，而 MARCH 算法对存储器的操 作次数则需要 6N 次，大大地节省了测试时间。 以一个 X（行地址）、Y（列地址）地址复用的 128128 的存储器矩阵为例，按改进 后的算法编写的测试图形片断如图 2.66。 厦门大学软件学院-毕业论文 13 图 2. 6 按改进后算法编写的图形片断 实际的算法图形要配合读写的时序，因此图形更为复杂，但对存储器的操作次数与理论 是一致的，改进的 Checkerboard 算法虽然使用了较少的存储器操作次数，但其只能诊断出 部分 AF 故障，与 MARCH 算法相比，是以牺牲故障覆盖率为代价来提高测试速度的。 厦门大学软件学院-毕业论文 14 在实际的生产型测试中，地址译码模块由于结构较存储矩阵要简单得多，因此出现故障 的概率远远小于存储矩阵，且改进的 Checkerboard 算法也能诊断部分的 AF 故障，是一种 经济的测试算法16。 厦门大学软件学院-毕业论文 15 第三章第三章 MARCHMARCH 算法详细叙述算法详细叙述 3.13.1 ATSATS 和改进的和改进的 ATSATS 算法算法(MATS)(MATS) 这些算法能够检测存储器中的卡住故障。ATS (Algorism Test Sequence)由 Kanizuk 在 1977 年提出，后来 Nair 在 1979 年对其进行了改进，并更名为 MATS。此算法对卡住故障 能提供最短的齐步测试。后来 Abadir 又做了进一步改进，称为 MATS+算法。 3.1.13.1.1 MATSMATS 算法算法 （w0） ；（r0，w1） ； （r1） M0 M1 M2 算法包括四步操作： 先写“0” （初始化） ； 按地址递增的顺序进行以下操作： 读“0” ，写“1” ； 按地址递减的顺序进行以下操作： 读“1” 。 3.1.23.1.2 MATMAT S+S+算法算法 （w0） ；（r0，w1） ； （r1，w0） M0 M1 M2 厦门大学软件学院-毕业论文 16 算法包括五步操作： 先写“0” （初始化） ； 按地址递增的顺序进行以下操作： 读“0” ，写“1” ； 按地址递减的顺序进行以下操作： 读“1” ，写“0” 。 3.1.33.1.3 MATS+MATS+算法算法 （w0） ；（r0，w1） ； （r1，w0，r0） M0 M1 M2 算法包括六步操作： 先写“0” （初始化） ； 按地址递增的顺序进行以下操作： 读“0” ，写“1” ； 按地址递减的顺序进行以下操作： 读“1” ，写“0” ，再读“0” 。 3.23.2 MARCHMARCH A A 和和 MARCHMARCH B B 算法算法 MARCH A 和 MARCH B 算法能覆盖一些复合故障，例如:等幂耦合故障和转换故障的 复合故障;倒置耦合故障和等幂耦合故障的复合故障等。 厦门大学软件学院-毕业论文 17 3.2.13.2.1 MARCHMARCH A A 算法算法 （w0） ；（r0，w1，w0，w1） ；（r1，w0，w1） ； M0 M1 M2 （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.23.2.2 MARCHMARCH B 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” ； 厦门大学软件学院-毕业论文 18 读“1” ，写“0” ，写“1” ； 按地址递减的顺序进行以下操作： 读“1” ，写“0” ，写“1” ，写“0” ； 读“0” ，写“1” ，读“0” 。 3.33.3 MARCHMARCH C C 算法算法 1982 年在 ITC (International Test Conference)上被提出的 MARCH C 算法，以及它的 一些衍生算法目前已成为存储器测试中最流行的算法20。 MARCH C 算法可以检测固定故障，跳变故障以及大部分的藕合故障。 MARCH C+算法是改进后的 MARCH C 算法，在齐步的每一级增加了一次读操作，使 它能够覆盖 Stuck-open 故障，即前面提到的开路故障是由于 MOS 管的缺陷等原因造成在某 个特定向量输入时，逻辑门的输出端为不期望发生的高阻态。通常发生在控制或译码电路中， 对此种故障的覆盖率与输入向量的先后次序有很大关系，因此在每步增加一次读操作可大大 提高对此种故障的覆盖率。另外 MARCH C+算法同样可检测固定型故障、转换故障以及耦 合故障。可见，它是一种很适合检测存储器的算法。 MARCH C-算法是对 MARCH C 算法的修正，去掉了第四步的读“0”操作，使总的操 作步骤减少到 10 步，同时并没有降低错误覆盖率，可检测和 MARCH C 相同的故障类型。 MARCH C-测试算法是其它算法的基础，各单元均得到执行，同时单元地址按递增或 递减方式提供。 3.3.13.3.1 MARCHMARCH C C 算法算法 （w0） ；（r0，w1） ；（r1，w0） ；（r0） ；（r0，w1） ； M0 M1 M2 M3 M4 厦门大学软件学院-毕业论文 19 （r1，w0） ；（r0） M5 M6 算法包括十一步操作： 先写“0” （初始化） ； 按地址递增的顺序进行以下操作： 读“0” ，写“1” ； 读“1” ，写“0” ； 读“0” ； 按地址递减的顺序进行以下操作： 读“0” ，写“1” ； 读“1” ，写“0” ； 读“0” 。 3.3.23.3.2 MARCHMARCH C+C+算法算法 （w0） ；（r0，r0，w1） ；（r1，r1，w0） ；（r0） ；（r0，r0，w1） ； M0 M1 M2 M3 M4 （r1，r1，w0） ；（r0） M5 M6 算法包括十五步操作： 先写“0” （初始化） ； 按地址递增的顺序进行以下操作： 读“0” ，读“0” ，写“1” ； 读“1” ，读“1” ，写“0” ； 读“0” ； 按地址递减的顺序进行以下操作： 读“0” ，读“0” ，写“1” ； 读“1” ，读“1” ，写“0” ； 读“0” 。 厦门大学软件学院-毕业论文 20 3.3.33.3.3 MARCHMARCH C-C-算法算法 （w0） ；（r0，w1） ；（r1，w0） ；（r0，w1） ； M0 M1 M2 M3 （r1，w0） ；（r0） M4 M5 算法包括十步操作： 先写“0” （初始化） ； 按地址递增的顺序进行以下操作： 读“0” ，写“1” ； 读“1” ，写“0” ； 按地址递减的顺序进行以下操作： 读“0” ，写“1” ； 读“1” ，写“0” ； 读“0” 。 3.43.4 其它其它 MARCHMARCH 算法算法 3.4.13.4.1 MARCHMARCH X X 算法算法 （w0） ；（r0，w1） ； （r1，w0） ；（r0） M0 M1 M2 M3 厦门大学软件学院-毕业论文 21 算法包括六步操作： 先写“0” （初始化） ； 按地址递增的顺序进行以下操作： 读“0” ，写“1” ； 按地址递减的顺序进行以下操作： 读“1” ，写“0” ； 读“0” 。 3.4.23.4.2 MARCH-TBAMARCH-TBA 算法算法 算法包括十八步： 第 0 步：在所测试内存空间内按由低到高顺序进行写一，读一操作; 第 1 步：由低地址到高地址进行写一，读一，写零操作; 第 2 步：由低地址到高地址做读零，写一操作； 第 3 步：由低地址到高地址做读一操作操作； 第 4 步：由低地址到高地址做读一，写零操作； 第 5 步：由低地址到高地址做读零操作； 第 6 步：由高地址到低地址做读零，写一操作： 第 7 步：由高地址到低地址做读一操作； 第 8 步：由高地址到低地址做读一，写零操作； 第 9 步：延迟； 厦门大学软件学院-毕业论文 22 第 10 步；由高地址到低地址做读零操作； 第 11 步：由高地址到低地址做写一操作； 第 12 步：延迟； 第 13 步：由高地址到低地址做读一操作； 第 14 步: 由低地址到高地址做写零操作； 第 15 步：由低地址到高地址做读一，写一操作； 第 16 步：由高地址到低地址做写零操作； 第 17 步：由高地址到低地址做写一，读零操作； 第 18 步：由低地址到高地址做写零，读一操作。 3.4.33.4.3 MARCHMARCH SSSS 算法算法 （w0） ；（r0，r0，w0，r