组合逻辑自动测试模式生成ATPG_2
主要的组合自动测试模式生成算法
定义
D算法（Roth）-1966年
D多维
桥接缺陷
逻辑门功能改变缺陷
PODEM（Goel）-1981年
X路径检查
回溯
总结
前向隐含
产生逻辑门输入的明显标记，以便唯一确定输出；
AND门前向隐含表
图 1 前向隐含
后向隐含
当给出门输出和一些输入时，唯一确定所有门输入
图 2 后向隐含
隐含堆栈
下推式堆叠， 记录：
由ATPG在电路中设置的每个信号
是否已经尝试过备用信号值
已经搜索过的二进制搜索树的部分
图 3 隐含堆叠
回溯后的隐含堆栈
图 4 回溯后的隐含堆栈
ATPG算法的目标与回溯 Backtrace
目标– ATPG的期望信号值目标
指导它远离不可行/困难的解决方案
回溯– 确定要设置哪些主要输入和值以实现目标
使用可测试性措施
图 5 ATPG的期望信号值
分界搜索 Branch-and-Bound Search
高效搜索二叉搜索树
分支 (Branch)–在每个树级别，选择将哪个输入变量设置为哪个值
边界（Bounding）–通过人为地限制搜索决策选择来避免探索树大的部分
完全探索是不切实际的
使用启发式
D算法-罗斯 Roth IBM公司 （1966年）
发明的基本概念：
第一个完整的ATPG算法
D-多维
D-微积分
隐含–向前和向后
隐含堆栈
回溯
测试搜索空间
单一覆盖示例
最少的逻辑信号分配集合，
以显示卡诺图的基本本征隐含
图 6 单一覆盖
D_多维
折叠式真值表条目以表征逻辑
使用罗斯的5值代数
可以将所有D更改为非D，将非D更改为D（同时执行）
与门：
图 7 折叠式真值表
D交点的D-多维操作
y–未定义（与f相同）
m或l –要求D和D取反
D交点：
D防护– 
多维数据集包含： 如果b是a的子集，则多维数据集a包含数据集b
图 8 多维数据集
缺陷的初始 D- 多维数据
电路缺陷建模：
钳滞在0
钳滞在1
桥接缺陷（短路）
逻辑功能的任意变更
“与”门输出钳滞在0：“ 1 1 D”
“与”门输出钳滞在1：“ 0 X 非D”
“ X 0 非D”
联线钳滞在0： “ D”
传输D多维–缺陷影响通过门传输条件下的建模
隐含过程 Implication Procedure
具有适当的初始D-多维的缺陷模型（primitive D-cube of failure PDF）
选择传输D-多维以将缺陷影响传输到电路输出（D驱动过程）
选择单一的覆盖多维以证明内部电路信号的合理性（一致性过程）
将信号分配放入测试多维体
多维数据集是由D-ALG非常随意地选择的
桥接缺陷电路
图 9 桥接缺陷电路
原始构造缺陷的多维数据集
当好机器输出为1时使多维数据集设置为a1，当好机器输出为0时使多维数据集设置为a0
当不良机器输出为1时使多维数据集设置为b1，输出为0时使多维数据集设置为 b0
将a1输出更改为0，并与每个b0进行D相交。 如果交集起作用，将多维数据集的输出更改为D 。
将a0输出更改为1，并与每个b1进行D相交。 如果交集起作用，将多维数据集的输出更改为非D
桥接缺陷D-多维数据集
图 10 桥接缺陷D-多维数据集
门功能变化D-多维失效
图 11 门功能变化D-多维失效
D算法–顶层
从输入到输出按升序对所有电路路径编号；
选择缺陷的原始D多维数据集作为测试多维数据集；
将带有标记为D（非D）的输入的逻辑输出放到D边界上；
D驱动器（）;
一致性（）；
返回return（）;
D算法– D驱动器
当（对D边界的尝试性断层影响）
选择下一个未尝试的D边界门进行传输； 同时（存在未尝试的缺陷影响扇出）
选择下一个未尝试的缺陷影响扇出；
生成下一个未尝试的传输D多维数据集；
D将选定的多维数据集与测试多维数据集相交；
如果（交集失败或不确定）继续；
如果（所有传输D多维数据集都尝试过并且失败了），是否中断；
如果（相交成功） 将传输D多维数据集添加到测试多维数据集-重新创建D边界;
查找任务的所有前向和后向含义；
保存D边界，算法状态，测试多维数据集，扇出，缺陷；
停止;
否则（交集失败，测试多维数据集中的D和非D）返回（）；
否则（相交失败）中断；
否则 如果（所有缺陷影响均不可传输）Backtrack（）；
D算法– 一致性
g = 带有1和0的测试多维数据集的坐标；
如果（g是唯一的输入）缺陷可测试并停止；
对于（g中每个不合理的信号）
选择g中最多数量的不合理信号z，而不是输入；
如果（到门z的输入既是D又是非D），中断；
当（z门的未试单一覆盖）
选择下一个未尝试的单一覆盖；
如果（不再有单一覆盖）
如果（没有更多的堆栈选择）缺陷不可测并停止；
否则，（一致性中未尝试的替代方法） 弹出式隐含堆栈-尝试其他分配；
回溯（）;
D驱动器（）;
如果（与z的单一覆盖D相交）从g中删除z，将输入添加到g的单一覆盖，找到新赋值的所有前向和后向含义，然后中断；
如果（相交失败）将单一覆盖标记为失败；
D算法–回溯
如果（输出存在且具有缺陷影响）一致性（）；
否则，弹出先前的隐含堆栈设置以尝试进行备用分配；
如果（隐含堆栈中没有未尝试的选择） 缺陷无法测试并停止；
否则返回；
电路示例7.1和真值表
图 12 电路示例
单一覆盖和D多维数据集
单一覆盖– 用于对齐传输线
传输D多维数据集– 良好/不良机器之间的差异传输的条件
图 13 单一覆盖和D多维数据集
缺陷d 钳滞在0的步骤
图 14 缺陷d 钳滞在0
例7.2缺陷A钳滞在0的步骤
步骤1 – D-驱动 – 设置A = 1
图 15 缺陷A钳滞在0
步骤2 – D-驱动 – 设置f = 0
图 16 设置f = 0
步骤3 – D-驱动 – 设置k = 1
图 17 设置k = 1
步骤4 – 一致性 – 设置g = 1
图 18 设置g = 1
步骤5– 一致性 –设置f = 0 在之前已设置
图 19 一致性
步骤6– 一致性 – 设置c = 0, e=0
图 20 设置c = 0, e=0
D链消失 示例7.2
步骤7 –一致性– 设置B = 0 , D链消失
图 21 设置B = 0 ，D链消失
例7.3 – 缺陷s钳滞在1
步骤1，初始D- 多维缺陷
(q,b) 是指引线CC0=a, CC1=b
图 22 多维缺陷
步骤2，v的传输D多维数据集
图 23 v的传输
向前和向后的含义
图 24 向前和向后的含义
步骤3，Z的传输D多维数据集- 找到失效点
图 25 找到失效点
例7.3 –缺陷u 钳滞在1
步骤1，初始D-多维缺陷
图 26 初始D
步骤2，v的传输D多维数据集
图 27 v的传输
向前和向后的含义
图 28 向前和向后的含义
前后不一致
d= 0和m = 1不能证明r = 1（对等）
回溯
删除B = 0的任务
回溯 需要不同的传输用于v的D多维数据集
图 29 回溯
步骤3， v的传输D多维数据集
图 30 v的传输
步骤4，z的传输D多维数据集
图 31 z的传输
z的传输D多维数据集和含义
图 32 z的传输D多维数据集和含义
路径导向的决策 (PODEM Path-Oriented Decision Making)
戈尔Goel， IBM公司 （1981）
引入的新概念：
仅在主要输入周围扩展二进制决策树
使用X-PATH-CHECK测试D边界是否仍然存在
目标- 使ATPG更接近将D（非D）传输到输出
回溯
动机
IBM于1970年代后期将半导体DRAM存储器引入其大型机。
具有纠错和转换电路的存储器– 提高了可靠性
D-ALG无法测试这些电路
搜索太无方向
大型XOR门树
必须设置所有外部输入才能定义输出
需要更好的ATPG工具
PODEM高阶流程
将二进制值分配给未分配的输入
确定所有输入的含义
测试产生了吗？ 如果是这样，完成。
可以使用更多分配的输入进行测试吗？ 如果可能，请转到步骤1
分配的输入上是否有未尝试的值组合？ 如果没，退出：无法测试的缺陷
使用目标和回溯在未分配的输入上设置未尝试的值组合， 然后，转到步骤2
再回到 例7.3
步骤1，选择路径s – Y进行失效传输
图 33 s – Y失效传输
步骤2，初始目标：将r设置为1以识别缺陷
图 34 将r设置为1
步骤3
从r回溯，示意图同上
步骤4
在隐式堆栈中设置A = 0， 示意图同上
步骤5
前向影响：d = 0，X = 1
图 35 前向影响：d = 0，X = 1
步骤6
初始目标：将r设置为1
同上图
步骤7，再次从r回溯
同上图
步骤8，将B设置为1。堆栈中的含义：A = 0，B = 1
图 36 将B设置为1
步骤9
正向含义：k = 1，m = 0，r = 1，q = 1，Y = 1，s = D，u = D，v = D，Z = 1
图 37 正向含义
步骤10
X-PATH-CHECK显示路径s–Y 和 s–u–v–Z 被阻止（D边界消失）
图 38 显示路径s–Y 和 s–u–v–Z 被阻止
步骤11，设置B = 0（备用分配）
图 39 设置B = 0
步骤12 回溯- s 钳滞在1
前向含义：d = 0，X = 1，m = 1，r = 0， s = 1，q = 0，Y = 1，v = 0，Z = 1。
缺陷不敏感
图 40 前向含义
步骤13
设置A = 1（备用分配）
图 41 设置A = 1
步骤14，再次从r回溯
同上图
步骤15
设置B =0。堆栈中的含义：A = 1，B = 0
图 42 设置B =0
步骤16： 回溯， s 钳滞在1
正向含义：d = 0，X = 1，m = 1，r =0。冲突：缺陷不敏感。 回溯
图 43 正向含义
步骤17
设置B = 1（备用分配）
图 44 设置B = 1
步骤18，缺陷检测到了
正向含义：d = 1，m = 1，r = 1，q = 0，s = D，v = D，X = 0，Y = D
图 45 检测到缺陷
回溯（s，vs）伪代码
v = vs;
当（s是门输出）
如果（s是NAND或INVERTER或NOR）v = v;
如果（目标要求设置所有输入）
选择s的未分配输入a，
最难控制到值v；
否则： 选择s的未分配输入a，
最容易控制到值v；
s = a;
return（s，v）/ *要分配的门和值* /;
目标选择代码
如果（门g未分配）返回（g，v）;
从D边界中选择门P；
选择P的未分配输入l；
如果（门g具有控制值） c =控制g的输入值；
否则，如果（在XOR / EQUIV门的输入处更容易获得0值） c = 1；
否则c = 0;
返回（l，c）;
PODEM算法
当（对输出无缺陷影响）
如果（xpathcheck（D边界）
（l，vl）=目标（缺陷，vfault）；
（pi，vpi）=回溯（l，vl）; 暗示（pi，vpi）;
如果（PODEM（缺陷，vfault）==成功）返回（成功）;
（pi，vpi）=回溯（）; 暗示（pi，vpi）;
如果（PODEM（缺陷，vfault）==成功）返回
(成功）;
暗示（pi，“ X”）；
返回（失败）;
否则，如果（隐含堆栈已耗尽）
返回（失败）;
否则Backtrack（）;
返回（成功）;
小结:
D_ALG – 第一个完整的ATPG算法
D_多维
D微积分
含义–向前和向后
隐含堆栈
后备
PODEM
仅围绕输入扩展决策树
使用X-PATH-CHECK查看是否存在D边界
目标- ATPG 把D（非D）更加接近输出
回溯
