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

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 初始立方 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 1 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 Step1 D 驱赶 SetA 1 D 2004 5 25 北京大学微电子学研究院SOC研究所 12 1 D Step2 D 2004 5 25 北京大学微电子学研究院SOC研究所 13 1 0 D Step2 D 驱赶 Setf 0 D Step3 D 1 Step3 D 驱赶 设定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 0 D 链消失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边界中还