第6讲[3-2]主要的组合ATPG算法HQU2015.ppt

3.2主要的组合ATPG算法,2004-5-25,北京大学微电子学研究院SOC研究所,1,定义D-算法(Roth)-1966D-立方桥接故障故障改变逻辑门功能PODEM(Goel)-1981X-路径检查回溯（Backtracing）小结,定义,1初始D-立方,n维空间中任意一个点、一条线段,均称为一个立方.其中点是对应逻辑函数的最小项.而除了点以外的各种线段、面积等表示的均不是最小项,称为奇异立方.任何一个逻辑函数都可以用若干（奇异）立方来描述.例如,f=x1x3+x2x3可以用奇异立方（11）及（10）来描述.实际上,逻辑函数的立方表示法就是真值表的压缩格式表示法.如或非门NOR,有的也称为初始立方,每一行称为一个立方.,2004-5-25,北京大学微电子学研究院SOC研究所,2,（a）真值表,（b）初始立方,2故障D立方,在元件E的输出可产生故障信号D（D）的最小输入条件称为故障D立方.其中D表示正常电路输出为1,故障时输出为0,记为D=1/0;D则反之,记为D=0/1;.如果用表示正常电路的奇异立方,用表示故障电路的奇异立方,则有D=1n0D=0n1逻辑门的故障D立方是通过正常门和故障门的初始立方进行交（n）运算而得到的.,2004-5-25,北京大学微电子学研究院SOC研究所,3,故障D立方的形成规则首先形成逻辑门的正常初始立方和故障初始立方.,对正常初始立方和故障初始立方进行交运算.（1）正常初始立方（2）故障初始立方,10,以上为逻辑门输入端的故障初始D立方的形成规则.而对于逻辑门输出端的故障初始立方可按照:只要将正常初始立方中的输出值1改为D,输出值0改为D即可.,01,2004-5-25,北京大学微电子学研究院SOC研究所,4,3传播D立方把元件E的输入端的若干故障信号能传播至E的输出端的最小输入条件称为传播D立方.传播D立方可从门的正常初始立方得到,即把门的正常初始立方中具有不同输出值的立方进行交运算即可获得.4D相交D相交又称D立方相交,它是建立敏化通路的工具,又是回推相容运算中是否相容的工具.5D边界它是指输入含有D/D信号而输出还未定值的所有逻辑单元的集合.6D驱赶指D运算中,把D/D从故障源向原始输出传播的过程.,2004-5-25,北京大学微电子学研究院SOC研究所,5,(ForwardImplication),正向蕴涵,正向蕴涵是指当一个逻辑单元的一个或几个输入的值确定之后,对其输出定值的运算.,（a）正向蕴涵,2004-5-25,北京大学微电子学研究院SOC研究所,6,（b）AND门正向蕴涵表,反向蕴涵指当门的输出和某些门的输入的值确定之后,确定其输入值的运算.,反向蕴涵（BackwardImplication）,图1反向蕴涵,2004-5-25,北京大学微电子学研究院SOC研究所,7,D-算法-RothIBM(1966),2004-5-25,北京大学微电子学研究院SOC研究所,8,提出基本概念:第一个完备的ATPG算法D-立方D-驱赶蕴涵正向和反向线确认相容性检查,D-算法,-总流程D-算法又称多维通路敏化法,它是一维通路敏化法的改进.它的主要思想是同时敏化从故障源到电路所有输出的全部可能的通路.1.电路所有连线数从PI到PO增加量级;2.选择故障的原始D-立方为测试立方;使逻辑输出与输入标记D-边界上D(D);3.D-驱动();4.相容性检查();5.返回();,2004-5-25,北京大学微电子学研究院SOC研究所,9,D-驱赶（drive）,while(未试验D-边界上的故障响应)选择下一个未试验的D-边界门进行传播;while(未试验的故障响应扇出存在)选择下一个未试验的故障响应扇出;生成下一个未试验的传播D-立方;D-交叉选择的立方与测试立方;if(交叉失败或未定义)继续;if(试验,2004-5-25,北京大学微电子学研究院SOC研究所,10,相容性检查（Consistency）,g=具有1和0的测试立方的coordinates;if(g仅是PIs)故障可测,2004-5-25,北京大学微电子学研究院SOC研究所,11,例1故障As-a-0Step1,Step1D-驱赶SetA=1,D,2004-5-25,北京大学微电子学研究院SOC研究所,12,1,D,Step2,D,2004-5-25,北京大学微电子学研究院SOC研究所,13,1,0,D,Step2D-驱赶Setf=0,D,Step3,D,1,Step3D-驱赶设定k=11D0,D,D,2004-5-25,北京大学微电子学研究院SOC研究所,14,Step4,Step4相容性检查设定g=1,D,1,D,D,1,D,1,2004-5-25,北京大学微电子学研究院SOC研究所,15,相容性检查指在一次D驱赶成功之后,还要检查一下所得测试立方是否与元件的奇异立方有矛盾,以便早发现矛盾早返回.,Step5,Step5相容性检查f=0已经设定,D,1,D0,D,D,1,1,2004-5-25,北京大学微电子学研究院SOC研究所,16,Step6,Step6相容性检查Setc=0,Sete=0,D,1,0,D,D,1,D,1,2004-5-25,北京大学微电子学研究院SOC研究所,17,0,0,D-链消失,Step7相容性检查SetB=0D-链消失X,D,1,0,D,D,1,D,1,2004-5-25,北京大学微电子学研究院SOC研究所,18,0,0,0,测试立方:A,B,C,D,e,f,g,h,k,L,例2故障ss-a-1故障初始D-立方,1,D,sa1,2004-5-25,北京大学微电子学研究院SOC研究所,19,Step2传播v的D-立方,ss-a-1,1,D,sa10,D,1,D,2004-5-25,北京大学微电子学研究院SOC研究所,20,Step3ssa1正向和反向蕴涵,1,D,sa10,D,D,1,2004-5-25,北京大学微电子学研究院SOC研究所,21,1,0,1,1,Step4,ss-a-1,D,D,传播Z的D-立方测试矢量建立!01,2004-5-25,北京大学微电子学研究院SOC研究所,22,D,sa10,1,1,1,1,1,D,Step5故障us-a-1失败的原始D-立方,1,D,0,sa1,2004-5-25,北京大学微电子学研究院SOC研究所,23,Step6传播v的D-立方,us-a-1,1,D,0,sa1,D,0,2004-5-25,北京大学微电子学研究院SOC研究所,24,Step7us-a-1正向和反向蕴涵,1,D,0,0sa1,2004-5-25,北京大学微电子学研究院SOC研究所,25,D,0,0,1,1,0,例3回溯（Backtrack）,1,sa1,D,0,2004-5-25,北京大学微电子学研究院SOC研究所,26,需要交替传播v的D-立方,传播v的D-立方,Step2us-a-1,1,sa1,D,0,1,D,2004-5-25,北京大学微电子学研究院SOC研究所,27,传播Z的D-立方,Step3us-a-1,D,1,sa1,D,0,1,D,1,2004-5-25,北京大学微电子学研究院SOC研究所,28,1,传播Z的D-立方和蕴涵,Step4us-a-1,D,1,0sa1,D,0,1,D,1,2004-5-25,北京大学微电子学研究院SOC研究所,29,1,0,0,1,1,2004-5-25,北京大学微电子学研究院SOC研究所,30,开始给电路中门的输入输出编号,将其测试D立方与,其传播D立方进行D相交,形成门的传播D立方确定故障初试D立方从D边界中选出一逻辑单元,写出门的初试立方表,成功？,到初试输出？,相容性检查,成功？,另选择一传播D立方,还有传播D立方？,D边界中还有逻辑