第6讲[3-2]主要的组合ATPG算法HQU2015VIP免费

3.2主要的组合ATPG算法2004-5-25北京大学微电子学研究院SOC研究所1•定义•D-算法(Roth)--1966·D-立方·桥接故障·故障改变逻辑门功能•PODEM(Goel)--1981·X-路径检查·回溯（Backtracing）·小结第一页，共三十二页。定义1初始D-立方•n维空间中任意一个点、一条线段,……均称为一个立方.其中点是对应逻辑函数的最小项.而除了点以外的各种线段、面积等表示的均不是最小项,称为奇异立方.•任何一个逻辑函数都可以用若干（奇异）立方来描述.例如,f=x1x3+x2x3可以用奇异立方（1×1）及（×10）来描述.实际上,逻辑函数的立方表示法就是真值表的压缩格式表示法.如或非门NOR,有的也称为初始立方,每一行称为一个立方.2004-5-25北京大学微电子学研究院SOC研究所2（a）真值表（b）初始立方abC010100001110abC001x101x0第二页，共三十二页。2故障D立方•在元件E的输出可产生故障信号D（D）的最小输入条件称为故障D立方.•其中D表示正常电路输出为1,故障时输出为0,记为D=1/0;D则反之,记为D=0/1;.•如果用表示正常电路的奇异立方,用表示故障电路的奇异立方,则有D=1n0D=0n1•逻辑门的故障D立方是通过正常门和故障门的初始立方进行交（n）运算而得到的.2004-5-25北京大学微电子学研究院SOC研究所3第三页，共三十二页。•故障D立方的形成规则·首先形成逻辑门的正常初始立方和故障初始立方.·对正常初始立方和故障初始立方进行交运算.（1）正常初始立方（2）故障初始立方10以上为逻辑门输入端的故障初始D立方的形成规则.而对于逻辑门输出端的故障初始立方可按照:只要将正常初始立方中的输出值1改为D,输出值0改为D即可.012004-5-25北京大学微电子学研究院SOC研究所4abf1110x0x00abf1x10x0第四页，共三十二页。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(试验&失败所有传播D-立方)break;if(交叉成功)增加传播D-立方到测试立方--recreateD-边界;求所有分配的正向&反向蕴涵;存储D-边界,算法规定,测试立方,扇出,故障;break;elseif(交集失败&测试立方中的DandD)Backtrack();elseif(交集失败)break;if(所有故障响应不能传播)Backtrack();2004-5-25北京大学微电子学研究院SOC研究所10第十页，共三十二页。—相容性检查（Consistency）g=具有1和0的测试立方的coord...