简述存储器测试图形算法

　　1　介绍
　　随着集成电路制造工艺的不断进步，半导体芯片的发展趋于高密度、高速度、高复杂度，给测试带来了极大的挑战。存储器是集成电路产品中的一个主要门类，主要用来存放数据、指令、程序等信息。存储器的测试一方面可用于判断产品质量是否合格，另一方面通过测试获得一些数据用于改进工艺。
　　目前存储器的基本测试方法已经比较成熟，主要有存储器直接存取测试、存储器的宏测试、存储器内建自测试三种，各有利弊。存储器直接存取测试是利用自动测试设备来进行测试，自动测试设备的性能和测试成本使得直接存取测试方式对大容量的存储器并不合适。存储器的宏测试将存储器作为一个宏模块，利用电路内部的扫描路径生成宏模块的测试向量，再通过自动测试设备在电路外部施加测试矢量，对于较大的存储器，宏测试向量的数据量较大，测试需要较长时间。存储器内建自测试是在存储器外围产生一整套控制电路，实现芯片内置存储器测试模式的自动产生及测试结果的自动判别，这种方法增加芯片的面积，但是具有自动化程度高、测试质量高、测试成本低、测试时间短等优势。
　　对于存储器来说，最主要的测试是读写逻辑功能测试，以检测存储单元的故障，包括由于坏的金属连接、坏的元件、芯片逻辑错误等原因引起的功能故障。这些故障通常被简化为几个较为成熟的故障模型，通过不同的测试图形算法来检测故障。本文以存储器的测试图形为切入点，先简单介绍存储器简化的故障模型，然后介绍常用的存储器测试图形算法以及一些新近提出的改进存储器测试图形算法，对其进行比较，并对将来存储器测试图形的发展进行预期。
　　2　常用的存储器测试图形算法
　　对于存储器的功能测试，算法有很多种，分别针对不同的存储器故障模型，包括固定故障、转换故障、耦合故障、图形敏感故障、寻址故障、数据保留故障等。一个高效率的测试算法，需要用尽可能少的测试图形和尽可能短的测试时间检测到尽可能多的故障。从理论上说，存在覆盖所有故障的测试算法，但是实际上由于时间复杂度的原因无法实现。假设用N 表示一个存储器的地址数，那么测试图形的复杂度可以用N来表示。
　　对于较大容量的存储器来说，N3/2图形和N2图形的测试时间在实际测试中是无法承受的。在实际测试中最常用的算法主要有全0/全1图形，奇偶校验板图形和齐步1/0图形。这三种图形均为N图形。
　　1、全0/全1图形
　　将全部存储单元按顺序写0、读0、写1、读1，测试图形序列长度为4　N，可用于检测存储器的固定故障。
　　2、奇偶校验板图形
　　奇偶校验板图形也称棋盘图形，向存储单元矩阵写入的数据图形是根据存储单元选址地址码的奇偶性而定的，如果存储单元的行地址码和列地址码中有偶数个1，其奇偶性为0，则在该存储单元中写0，反之写1。根据算法写入背景图形，然后逐位读出并检测结果的正确性，再以反码图形重复上述测试过程，测试图形序列长度为4　N。奇偶校验板图形可用于检测存储器的固定故障、地址译码故障，以及相邻位的短路故障。
　　3、齐步图形
　　齐步图形算法也称March算法，是对存储器的每个单元依次进行检验的一种方法，从第一个存储单元开始，逐一对每个单元进行取反和检验，直到最后一个单元检测结束才完成一遍扫描。齐步算法的流程如图2所示，W0、W1、R0、R1分别表示写0、写1、读0、读1。具体流程为：首先背景图形写全0，从低地址开始沿增址方向顺序读0、写1(R0W1)，一直到最高地址。然后从最高地址开始沿减地址方向顺序读1、写0(R1W0)，测试图形序列长度为5　N。齐步图形可用于检测全部的固定故障、地址译码故障和转换故障。
　　4、其他测试图形
　　以上三种测试图形均为N 型测试图形，其共同特点是测试时间短，但覆盖的故障比较有限。相较而言，齐步算法的效率最高。除此之外，还有很多复杂度更高的图形，比如乒乓算法、蝶形算法等。乒乓算法的故障覆盖率很高，能够有效地检测出固定故障、转换故障、耦合故障和部分图形敏感故障，其测试图形序列长度为4　N2+2　N，属于N2型测试图形。蝶形算法同样具有很高的故障覆盖率，能够有效地检测出固定故障、地址解码故障和图形敏感故障，属于N3/2型测试图形。
　　这些高复杂度的测试图形都具有一个共同的弊端，时间复杂度太高，测试时间过长，虽然在理论中有很高的故障覆盖率，但在实际生产中很少使用。
　　因此，在近期关于存储器测试图形算法的研究中，提出了一些改进的N图形算法，跟经典的测试算法相比，在不大量增加测试时间的前提下，能够有效地提高故障覆盖率，在下一部分将详细进行介绍。
　　3　改进的存储器测试图形算法
　　目前，国内外经典的March算法有MATS、MATS+、March　A、March　B、March　C、March　C-、March　C+、March　LR、March　SR等。1979年Nairt提出的MATS算法对固定故障提供了最短的齐步测试;由MATS改进的MATS+算法能够检测地址解码故障及固定故障;1980年提出的March　A、March　B算法可用于测试部分连接故障;1991年，Van　de　Goor对Match　C算法进行改进，提出了March　C-算法，在获得同样的故障覆盖率的前提下降低了March　C 算法的复杂度;March　C+在March　C的基础上增加了3　N 的复杂度，但同时提高了故障覆盖率。March　C算法及其衍生算法现成为存储器测试的主流算法。本文将介绍三种较为新颖巧妙的改进算法。
　　1、棋盘型齐步算法
　　这种算法的基本构想是在齐步算法中使用棋盘格式，棋盘算法可以检测出固定故障和相邻单元的桥接故障，齐步图形算法可以覆盖全部的固定故障、地址译码故障和转换故障。将两种算法相结合，不仅可以实现两种算法本来的功能，由于读写特殊性，还可以检测一部分相邻图形敏感故障。
　　(1)所有存储单元写0。
　　(2)读A0单元(表示地址为0的单元)的0，再改写为0读A1单元的0，再改写为1读A2单元的0，再改写为0读A3单元的0，再改写为1直到An-1。此步执行完后，存储器被写为棋盘格式。
　　(3)读An-1单元的l，再改写为0读An-2单元的0，再改写为l直到A0。此步完成后，存储器被写为一个与步骤(2)结束后相反的棋盘格式。
　　经过改进的棋盘格齐步算法测试图形序列长度为5　N，跟齐步图形算法相比，测试时长没有增加，而故障覆盖率明显提高。
　　2、基于棋盘算法的改进
　　棋盘格图形算法中，对于每一个存储单元来说，只经过了从0到1的转换或者从1到0的转换，不能覆盖全部的转换故障。于是对棋盘算法进行了巧妙的改进，具体流程如下：
　　(1)写入反棋盘格图形;
　　(2)写入棋盘格图形;
　　(3)读棋盘格图形;
　　(4)写入反棋盘格图形;
　　(5)读反棋盘格图形。
　　该改进算法与棋盘格算法相比，测试图形序列长度增加了N，能够检测出全部的转换故障、地址解码故障、固定故障以及相邻单元的桥接故障，故障覆盖率有所提高。
　　3、March　SSE算法
　　(1)所有存储单元写0
　　(2)从低地址位递增到高地址位，对每个存储单元依次进行读0、写0、读0、写1、读1操作;
　　(3)从低地址位递增到高地址位，对每个存储单元依次进行读1、写1、读1、写0、读0操作;
　　(4)从高地址位递减到低地址位，对每个存储单元依次进行读0、写0、读0、写1、读1操作;
　　(5)从高地址递位减到低地址位，对每个存储单元依次进行读1、写1、读1、写0、读0操作;
　　(6)所有的存储单元读0。其测试图形序列长度为22N，通过改进，除了能够覆盖固定故障、地址解码故障等静态故障意外，还能够覆盖全部的动态读破坏故障、动态读错误故障、动态干扰耦合故障和部分动态伪读破坏故障、动态伪读破坏耦合故障。在检测存储器动态故障的算法中，以较低的测试时间复杂度，获得了较高的故障覆盖率。
　　4　存储器测试图形算法的应用
　　在目前的实际测试生产中，采用的都是存储器直接存取测试的方法，考虑到设备能力和测试效率的问题，通常使用的都是经典的O(N)型测试图形，仅包括全0/全1测试图形和奇偶校验板图形，对于大容量的存储器，由于设备测试图形存储容量的限制，仅采用奇偶校验板图形进行测试。这两种算法时间复杂度低，算法编写简单，且覆盖了出现频率较高的基本故障。结合测试图形自动发生器(Automatic　Pattern　Generator，APG)能够生成复杂度更高的测试图形，但又带来了可读性差、测试时间长、调试不便等问题，因而一些针对某些特殊故障的复杂测试图形更多地还停留在科研阶段。简单、高效、高故障覆盖率的测试图形算法是实际工业生产中追求的最终目标。
　　上一节提到的基于棋盘算法的改进方法，跟棋盘格算法比较，测试图形序列长度仅增加了N，覆盖了全部转换故障，测试图形的编写难度未增加。因此，在设备能力能够满足需求的条件下，在实际测试中采用该改进算法替换传统的棋盘格算法是很有价值的。
　　齐步法较目前使用的方法具有更高的故障覆盖率，测试图形的复杂度极少量的提高，测试图形编写难度也有所增加。棋盘型齐步算法结合了齐步法和棋盘法的特点，较齐步法有更高的故障覆盖率而未增加时间复杂度，在实际的测试生产中值得去尝试。
　　5　结语
　　存储器的测试图形算法始终存在测试时间复杂度和故障覆盖率的矛盾，故障覆盖率高的算法必然时间复杂度大。在目前的工业生产应用中，只能使用时间复杂度为O(N)的测试图形，因而根据实际需要，国内外研究人员基于经典N 型测试图形算法进行了改进研究，在不大量增加时间复杂度的前提下，提高故障覆盖率。但大多数研究还停留在理论分析层面，未通过实验验证，更没有投入到生产应用中。将来测试算法有可能将测试时间复杂度和故障覆盖率的矛盾调和到更低，也可能出现解决时间复杂度的方法，总之，存储器测试图形算法的研究还有待进一步的研究和发展。