存储器故障诊断算法实现
1 引言
存储器是各种电子设备中保存信息的主要部件，随着存储器芯片的密度和复杂度的日益提高，设计一个良好的测试算法来测试存储器变得尤为重要。
2 存储器的故障模型
研究存储器的检测方法，就必须先建立存储器单元的故障模型，也就是要求把物理故障模型化为逻辑故障，通常可以用功能模型或灰匣子模型将存储器故障模型化，典型ram功能模型如图1所示，该模型是由vande goor提出的简化功能dram模型[1]。
对于图1的功能模型，存储器的故障主要表现有3类：
(1)地址解码器故障(af)[2]，主要表现为4种形式(如图2所示)。
(2)读写逻辑模块故障。主要表现为在读写电路中，某些检测放大器的出或者写入驱动器的逻辑部分，可能产生开路、短路或者i/o固定的故障，在读写电路的数据
线之间存在交叉耦合的干扰。
(3)存储单元阵列故障，由于存储单元阵列是存储器内规模最为复杂的一个模块，因此出现故障的概率最大，故障的类型也最为复杂，主要是由于存储器单元内的数据线开路、短路以及串扰所引起的。
对于上述的功能模型去掉其中的某些逻辑模块，就可用于rom的测试。
3 存储器的简化功能故障[2、5、6]
基于以上各模块的故障表现形式，又由于地址译码故障和读写逻辑故障可以等效的功能映射为存储器单元阵列故障，故可把存储器故障简化为下列四种功能故障：
(1)固定故障(stuck-at fault，saf)
单元或连线的逻辑值总为0或总为1的故障，单元/连线总是处于有故障的状态，并且故障的逻辑值不变。
(2)转换故障(transition fault.tf)
转换故障是saf的一种特殊情况，当写数据时，某一存储单元失效使得0→1转变或1→0转变不能发生，表现为固定故障的形式。
(3)耦合故障(coupling fault，cf)
存储单元中某些位的跳变导致其他位的逻辑发生非预期的变化，它既可以发生在不同单元之间，也可以发生在同一单元不同位之间。
(4)相邻矢量敏化故障(neighborhood pattern sensitive faults，npsf)
一个单元因相邻单元的活动导致状态不正确，一个单元的相邻单元可能有5个，也可能有9个，如图3的(a)、(b)所示。
4 存储器故障诊断算法分析
针对存储器故障模型中的各种故障，人们提出了各种诊断算法，目前主要使用的算法有：checkerboard算法(棋盘法)、gallop算法(奔跳法)、march算法(进行法)等。
4.1 checkerboard算法(棋盘法)[7]
棋盘法的测试过程是首先对每一个存储单元赋值，使得每一个单元与其紧相邻的各个单元的值都不同，如图4所示，即把整个存储阵列分为两块a、b，然后采用如下过程对a、b进行读写;
(1)对分块a(b)中的单元写0(1);
(2)读所有单元;
(3)对分块a(b)中的单元写1(0);
(4)读所有单元;
(5)该算法理论上操作的次数是o(n)，其中n为存储器容量，可以检测saf故障和相邻单元的桥接故障，其故障覆盖率较低。
4.2 gallop算法(奔跳法)
gallop算法也称为1(0)漫游或乒乓测试，测试过程如下：
(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)在整个阵列中漫游一样，图5表示1漫游的情况，该算法具有较高的故障覆盖率，能检测saf故障、tf故障以及cf故障，单位该算法操作次数是o(n2)需要较长的测试时间。
4.3 march算法(进行法)[3，4]
(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故障。
5 一种基于棋盘算法的改进及实现
通过研究和对比上述3个算法发现，checkerboard(棋盘)算法和march算法以线性方式进行读写，因此存储器操作次数与存储器容量n成正比，gallop算法虽然有较高的故障覆盖率，但由于其对存储器刺激次数过多，因此，在实际测试中不是一种很经济的测试算法，checkerboad算法只实现了0→1或1→0的读写，所以不能测试变迁故障。而march算法恰恰实现了这两个状态的转换，但march算法操作次数(6n)要多于checkerboard算法的操作次数(4n)，对于大容量存储器的测试，march算法将需要比checkerboard算法更多的测试时间来完成整个测试过程，因此结合march算法的特点，对checkerboard算法进行如下改进。
(1)对分块a(b)中单元写1(0);
(2)对分块a(b)中的单元写0(1);
(3)读所有单元;
(4)对分块a(b)中的单元写1(0);
(5)读所有单元。
这样整个存储器就同时经历了由0→1和1→0两个读写状态，就可以测试出变迁故障，写改进后checkboard算法对存储器的操作次数为5n次，而march算法对存储
器的操作次数则需要6n次，大大地节省了测试时间。
以一个x(行地址)、y(列地址)地址复用的128×128的存储器矩阵为例，按改进后的算法编写的测试图形片断如图6。
实际的算法图形要配合读写的时序，因此图形更为复杂，但对存储器的操作次数与理论是一致的，改进的checkerboard算法虽然使用了较少的存储器操作次数，但其只能诊断出部分af故障，与march算法相比，是以牺牲故障覆盖率为代价来提高测试速度的。
在实际的生产型测试中，地址译码模块由于结构较存储矩阵要简单得多，因此出现故障的概率远远小于存储矩阵，且改进的checkerboard算法也能诊断部分的af故障，是一种经济的测试算法。
6 结语
改进的算法虽然提高了测试速度，但这种改进牺牲了故障覆盖率。但就实际的测试需要而言，是完全符合要求且行之有效的，在实际应用中，要根据存储器的故障类型和测试需求来选择合适的诊断算法，才能达到满意的效果。
意大利KTech Genesis3D打印机
米尔科技DSTREAM-ST高性能仿真器介绍
机器人催生“竞赛热” 教育机器人市场一片蓝海
阿尔卡特发布了一款新机Alcatel 1S搭载八核A55处理器售价不到千元
华为P10还未发布，起步价却宣布提升300元
存储器故障诊断算法实现
USB PD3.1 EPR助力24V直流电机驱动
是否掌握重组全球产业链的能力 才是贸易战中决胜的关键
DARPA为开发长距离远程水下航行器向三家公司授予开发合同
自动驾驶那么火 丰田为什么押注机器人？
车联网前景可人，5G WIFI提供更大创造力
iOS11惊曝网红最期待的新功能：iOS11竟然加入直播功能？
XboxOne美版电源直改220V教程
用于SciLifeLab提供医疗研究的微阵列技术
华为Mate20Pro翡冷翠高清图赏
华进半导体与芯德科技合作共同助力江苏省先进封装发展
泰科面向固态照明行业推出全新G13型灯头连接器
李宝山：中国光伏将在2020年稳步进入平价时代
如何为低负载系统提供高效率的稳压功能？这些方法有何优点？
解密“输入标配PFC，功率因素高达0.99”的作用
存储器是各种电子设备中保存信息的主要部件，随着存储器芯片的密度和复杂度的日益提高，设计一个良好的测试算法来测试存储器变得尤为重要。
2 存储器的故障模型
研究存储器的检测方法，就必须先建立存储器单元的故障模型，也就是要求把物理故障模型化为逻辑故障，通常可以用功能模型或灰匣子模型将存储器故障模型化，典型ram功能模型如图1所示，该模型是由vande goor提出的简化功能dram模型[1]。
对于图1的功能模型，存储器的故障主要表现有3类：
(1)地址解码器故障(af)[2]，主要表现为4种形式(如图2所示)。
(2)读写逻辑模块故障。主要表现为在读写电路中，某些检测放大器的出或者写入驱动器的逻辑部分，可能产生开路、短路或者i/o固定的故障，在读写电路的数据
线之间存在交叉耦合的干扰。
(3)存储单元阵列故障，由于存储单元阵列是存储器内规模最为复杂的一个模块，因此出现故障的概率最大，故障的类型也最为复杂，主要是由于存储器单元内的数据线开路、短路以及串扰所引起的。
对于上述的功能模型去掉其中的某些逻辑模块，就可用于rom的测试。
3 存储器的简化功能故障[2、5、6]
基于以上各模块的故障表现形式，又由于地址译码故障和读写逻辑故障可以等效的功能映射为存储器单元阵列故障，故可把存储器故障简化为下列四种功能故障：
(1)固定故障(stuck-at fault，saf)
单元或连线的逻辑值总为0或总为1的故障，单元/连线总是处于有故障的状态，并且故障的逻辑值不变。
(2)转换故障(transition fault.tf)
转换故障是saf的一种特殊情况，当写数据时，某一存储单元失效使得0→1转变或1→0转变不能发生，表现为固定故障的形式。
(3)耦合故障(coupling fault，cf)
存储单元中某些位的跳变导致其他位的逻辑发生非预期的变化，它既可以发生在不同单元之间，也可以发生在同一单元不同位之间。
(4)相邻矢量敏化故障(neighborhood pattern sensitive faults，npsf)
一个单元因相邻单元的活动导致状态不正确，一个单元的相邻单元可能有5个，也可能有9个，如图3的(a)、(b)所示。
4 存储器故障诊断算法分析
针对存储器故障模型中的各种故障，人们提出了各种诊断算法，目前主要使用的算法有：checkerboard算法(棋盘法)、gallop算法(奔跳法)、march算法(进行法)等。
4.1 checkerboard算法(棋盘法)[7]
棋盘法的测试过程是首先对每一个存储单元赋值，使得每一个单元与其紧相邻的各个单元的值都不同，如图4所示，即把整个存储阵列分为两块a、b，然后采用如下过程对a、b进行读写;
(1)对分块a(b)中的单元写0(1);
(2)读所有单元;
(3)对分块a(b)中的单元写1(0);
(4)读所有单元;
(5)该算法理论上操作的次数是o(n)，其中n为存储器容量，可以检测saf故障和相邻单元的桥接故障，其故障覆盖率较低。
4.2 gallop算法(奔跳法)
gallop算法也称为1(0)漫游或乒乓测试，测试过程如下：
(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)在整个阵列中漫游一样，图5表示1漫游的情况，该算法具有较高的故障覆盖率，能检测saf故障、tf故障以及cf故障，单位该算法操作次数是o(n2)需要较长的测试时间。
4.3 march算法(进行法)[3，4]
(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故障。
5 一种基于棋盘算法的改进及实现
通过研究和对比上述3个算法发现，checkerboard(棋盘)算法和march算法以线性方式进行读写，因此存储器操作次数与存储器容量n成正比，gallop算法虽然有较高的故障覆盖率，但由于其对存储器刺激次数过多，因此，在实际测试中不是一种很经济的测试算法，checkerboad算法只实现了0→1或1→0的读写，所以不能测试变迁故障。而march算法恰恰实现了这两个状态的转换，但march算法操作次数(6n)要多于checkerboard算法的操作次数(4n)，对于大容量存储器的测试，march算法将需要比checkerboard算法更多的测试时间来完成整个测试过程，因此结合march算法的特点，对checkerboard算法进行如下改进。
(1)对分块a(b)中单元写1(0);
(2)对分块a(b)中的单元写0(1);
(3)读所有单元;
(4)对分块a(b)中的单元写1(0);
(5)读所有单元。
这样整个存储器就同时经历了由0→1和1→0两个读写状态，就可以测试出变迁故障，写改进后checkboard算法对存储器的操作次数为5n次，而march算法对存储
器的操作次数则需要6n次，大大地节省了测试时间。
以一个x(行地址)、y(列地址)地址复用的128×128的存储器矩阵为例，按改进后的算法编写的测试图形片断如图6。
实际的算法图形要配合读写的时序，因此图形更为复杂，但对存储器的操作次数与理论是一致的，改进的checkerboard算法虽然使用了较少的存储器操作次数，但其只能诊断出部分af故障，与march算法相比，是以牺牲故障覆盖率为代价来提高测试速度的。
在实际的生产型测试中，地址译码模块由于结构较存储矩阵要简单得多，因此出现故障的概率远远小于存储矩阵，且改进的checkerboard算法也能诊断部分的af故障，是一种经济的测试算法。
6 结语
改进的算法虽然提高了测试速度，但这种改进牺牲了故障覆盖率。但就实际的测试需要而言，是完全符合要求且行之有效的，在实际应用中，要根据存储器的故障类型和测试需求来选择合适的诊断算法，才能达到满意的效果。
意大利KTech Genesis3D打印机
米尔科技DSTREAM-ST高性能仿真器介绍
机器人催生“竞赛热” 教育机器人市场一片蓝海
阿尔卡特发布了一款新机Alcatel 1S搭载八核A55处理器售价不到千元
华为P10还未发布，起步价却宣布提升300元
存储器故障诊断算法实现
USB PD3.1 EPR助力24V直流电机驱动
是否掌握重组全球产业链的能力 才是贸易战中决胜的关键
DARPA为开发长距离远程水下航行器向三家公司授予开发合同
自动驾驶那么火 丰田为什么押注机器人？
车联网前景可人，5G WIFI提供更大创造力
iOS11惊曝网红最期待的新功能：iOS11竟然加入直播功能？
XboxOne美版电源直改220V教程
用于SciLifeLab提供医疗研究的微阵列技术
华为Mate20Pro翡冷翠高清图赏
华进半导体与芯德科技合作共同助力江苏省先进封装发展
泰科面向固态照明行业推出全新G13型灯头连接器
李宝山：中国光伏将在2020年稳步进入平价时代
如何为低负载系统提供高效率的稳压功能？这些方法有何优点？
解密“输入标配PFC，功率因素高达0.99”的作用