Menu Close

数字集成电路组合逻辑自动测试模式生成ATPG_2

组合逻辑自动测试模式生成ATPG_2

主要的组合自动测试模式生成算法

定义 

D算法(Roth)-1966年

D多维

桥接缺陷

逻辑门功能改变缺陷

PODEM(Goel)-1981年

X路径检查

回溯

总结

 

前向隐含

产生逻辑门输入的明显标记,以便唯一确定输出;

C:\WINNT\Profiles\bushnell\bookfoils\catpg\forwardimp.tif C:\WINNT\Profiles\bushnell\bookfoils\catpg\forwardimp.tif

AND门前向隐含表

图 1    前向隐含

 

后向隐含

当给出门输出和一些输入时,唯一确定所有门输入

C:\WINNT\Profiles\bushnell\bookfoils\catpg\backimp.tif

图 2    后向隐含

 

隐含堆栈

下推式堆叠, 记录:

由ATPG在电路中设置的每个信号

是否已经尝试过备用信号值

已经搜索过的二进制搜索树的部分

%title插图%num

图 3    隐含堆叠

 

回溯后的隐含堆栈

%title插图%num

%title插图%num

 

图 4    回溯后的隐含堆栈

 

ATPG算法的目标与回溯 Backtrace

 

目标– ATPG的期望信号值目标

指导它远离不可行/困难的解决方案

回溯– 确定要设置哪些主要输入和值以实现目标

使用可测试性措施

C:\WINNT\Profiles\bushnell\bookfoils\catpg\backtrace.tif

图 5    ATPG的期望信号值

 

分界搜索 Branch-and-Bound Search

高效搜索二叉搜索树

分支 (Branch)–在每个树级别,选择将哪个输入变量设置为哪个值

边界(Bounding)–通过人为地限制搜索决策选择来避免探索树大的部分

完全探索是不切实际的

使用启发式

 

D算法-罗斯 Roth IBM公司 (1966年)

发明的基本概念:

第一个完整的ATPG算法

D-多维

D-微积分

隐含–向前和向后

隐含堆栈

回溯

测试搜索空间

 

单一覆盖示例 

最少的逻辑信号分配集合,

以显示卡诺图的基本本征隐含

C:\WINNT\Profiles\bushnell\bookfoils\catpg\singcov.tif

%title插图%num

图 6    单一覆盖

D_多维

折叠式真值表条目以表征逻辑

使用罗斯的5值代数

可以将所有D更改为非D,将非D更改为D(同时执行)

与门:

%title插图%num

图 7    折叠式真值表

 

D交点的D-多维操作 

y–未定义(与f相同)

m或l –要求D和D取反

D交点:

D防护–  %title插图%num

多维数据集包含: 如果b是a的子集,则多维数据集a包含数据集b

%title插图%num

图 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非常随意地选择的

桥接缺陷电路

%title插图%num

图 9    桥接缺陷电路

 

原始构造缺陷的多维数据集

当好机器输出为1时使多维数据集设置为a1,当好机器输出为0时使多维数据集设置为a0

当不良机器输出为1时使多维数据集设置为b1,输出为0时使多维数据集设置为 b0

将a1输出更改为0,并与每个b0进行D相交。 如果交集起作用,将多维数据集的输出更改为D 。

将a0输出更改为1,并与每个b1进行D相交。 如果交集起作用,将多维数据集的输出更改为非D

桥接缺陷D-多维数据集

 

%title插图%num

图 10    桥接缺陷D-多维数据集

 

门功能变化D-多维失效

C:\WINNT\Profiles\bushnell\bookfoils\catpg\andor.tif

%title插图%num

图 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和真值表

%title插图%num

图 12    电路示例

 

单一覆盖和D多维数据集

单一覆盖– 用于对齐传输线

传输D多维数据集– 良好/不良机器之间的差异传输的条件

%title插图%num

图 13    单一覆盖和D多维数据集

 

缺陷d 钳滞在0的步骤

%title插图%num

图 14    缺陷d 钳滞在0

 

例7.2缺陷A钳滞在0的步骤

步骤1 – D-驱动 – 设置A = 1

%title插图%num

图 15    缺陷A钳滞在0

 

步骤2 – D-驱动 – 设置f = 0

%title插图%num

图 16    设置f = 0

 

步骤3 – D-驱动 – 设置k = 1

%title插图%num

图 17    设置k = 1

 

步骤4 – 一致性 – 设置g = 1

%title插图%num

图 18    设置g = 1

 

步骤5– 一致性 –设置f = 0 在之前已设置

%title插图%num

图 19    一致性

 

步骤6– 一致性 – 设置c = 0, e=0

%title插图%num

图 20    设置c = 0, e=0

 

D链消失 示例7.2

步骤7 –一致性– 设置B = 0 , D链消失

%title插图%num

图 21    设置B = 0 ,D链消失

 

例7.3 – 缺陷s钳滞在1

步骤1,初始D- 多维缺陷

%title插图%num

(q,b) 是指引线CC0=a, CC1=b

 

图 22    多维缺陷

 

步骤2,v的传输D多维数据集

%title插图%num

图 23    v的传输

 

向前和向后的含义

%title插图%num

图 24    向前和向后的含义

 

步骤3,Z的传输D多维数据集- 找到失效点

%title插图%num

图 25    找到失效点

 

例7.3 –缺陷u 钳滞在1

步骤1,初始D-多维缺陷

%title插图%num

图 26    初始D

 

步骤2,v的传输D多维数据集

%title插图%num

图 27     v的传输

 

向前和向后的含义

%title插图%num

图 28    向前和向后的含义

 

前后不一致

d= 0和m = 1不能证明r = 1(对等)

回溯

删除B = 0的任务

回溯 需要不同的传输用于v的D多维数据集

%title插图%num

图 29    回溯

 

步骤3, v的传输D多维数据集

%title插图%num

图 30    v的传输

 

步骤4,z的传输D多维数据集

%title插图%num

图 31    z的传输

 

z的传输D多维数据集和含义

%title插图%num

图 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进行失效传输

%title插图%num

图 33    s – Y失效传输

 

步骤2,初始目标:将r设置为1以识别缺陷

%title插图%num

图 34     将r设置为1

步骤3

从r回溯,示意图同上

步骤4

在隐式堆栈中设置A = 0, 示意图同上

步骤5

前向影响:d = 0,X = 1

%title插图%num

图 35    前向影响:d = 0,X = 1

步骤6

初始目标:将r设置为1

同上图

步骤7,再次从r回溯

同上图

步骤8,将B设置为1。堆栈中的含义:A = 0,B = 1

%title插图%num

图 36    将B设置为1

步骤9

正向含义:k = 1,m = 0,r = 1,q = 1,Y = 1,s = D,u = D,v = D,Z = 1

%title插图%num

图 37    正向含义

步骤10

X-PATH-CHECK显示路径s–Y 和 s–u–v–Z 被阻止(D边界消失)

%title插图%num

图 38    显示路径s–Y 和 s–u–v–Z 被阻止

 

步骤11,设置B = 0(备用分配)

%title插图%num

图 39    设置B = 0

步骤12 回溯- s 钳滞在1

前向含义:d = 0,X = 1,m = 1,r = 0, s = 1,q = 0,Y = 1,v = 0,Z = 1。

缺陷不敏感

%title插图%num

图 40    前向含义

步骤13

设置A = 1(备用分配)

%title插图%num

图 41    设置A = 1

步骤14,再次从r回溯

同上图

步骤15

设置B =0。堆栈中的含义:A = 1,B = 0

%title插图%num

图 42    设置B =0

 

步骤16: 回溯, s 钳滞在1

正向含义:d = 0,X = 1,m = 1,r =0。冲突:缺陷不敏感。 回溯

%title插图%num

图 43    正向含义

步骤17

设置B = 1(备用分配)

%title插图%num

图 44    设置B = 1

 

步骤18,缺陷检测到了

正向含义:d = 1,m = 1,r = 1,q = 0,s = D,v = D,X = 0,Y = D

%title插图%num

图 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)更加接近输出

回溯

 

Posted in 数字集成电路

发表评论

相关链接