《VLSI测试及可测性设计方法课件.ppt》由会员分享，可在线阅读，更多相关《VLSI测试及可测性设计方法课件.ppt（67页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章组合电路测试图形生成算法介绍组合电路测试图形生成算法介绍1第第 二二 章章 内内 容容故障模型故障模型通路敏化法通路敏化法布尔差分法布尔差分法D D算法算法伪穷举法伪穷举法特征分析法特征分析法2 第一节第一节 故故 障障 模模 型型31.1.固定故障（固定故障（Stuck-At-FaultStuck-At-Fault）固定值故障：某一节点（包括输入或输出）的固定值故障：某一节点（包括输入或输出）的 逻辑值固定在逻辑值固定在“1”“1”或或“0”“0”。Stuck-At-1Stuck-At-1：节点逻辑值固定在：节点逻辑值固定在“1”“1”。Stuck-At-0Stuck-At-0：节点逻
2、辑值固定在：节点逻辑值固定在“0”“0”。42.2.固定开路，固定短路故障固定开路，固定短路故障（Switch-Level-FaultSwitch-Level-Fault）固定开路：晶体管一直维持截止状态。固定短路：晶体管一直维持导通状态。53.3.桥接故障（桥接故障（Bridging FaultBridging Fault）两根或多根信号线连接在一起引起的电路故障。64.4.时滞（延迟）故障（时滞（延迟）故障（Delay FaultDelay Fault）门延迟（门延迟（Gate DelayGate Delay）：延迟发生在）：延迟发生在逻辑门上。逻辑门上。路径延迟（路径延迟（Path De
3、layPath Delay）：延迟发生）：延迟发生在路径上。在路径上。检测方法检测方法75.5.冗余故障（冗余故障（Redundancy FaultRedundancy Fault）特点1：要么是不可 激活的，要么是无法检测的。特点2：不影响电路逻辑功能的。8第第 二二 节节 通通 路路 敏敏 化化 法法9异 或 运 算10113 3逻辑函数的异或表达式逻辑函数的异或表达式 逻辑函数都可以用两级与或的表达式来描述，如果把逻辑函数都可以用两级与或的表达式来描述，如果把逻辑函数表示成若干两两之间至少有一个变量互反的各乘逻辑函数表示成若干两两之间至少有一个变量互反的各乘积项之和，那么，利用公式积项之
4、和，那么，利用公式:X1X2/X1X3=X1X2+/X1X3:X1X2/X1X3=X1X2+/X1X3就可以把其中的或运算全部用异或运算来替代，即只用异就可以把其中的或运算全部用异或运算来替代，即只用异或门和与门来实现任何逻辑。最极端的例子是用最小项来或门和与门来实现任何逻辑。最极端的例子是用最小项来表示的逻辑函数，因为任意二个最小项中至少有一个变量表示的逻辑函数，因为任意二个最小项中至少有一个变量是互反变量，因此可以用两级与异或电路来描述任意逻是互反变量，因此可以用两级与异或电路来描述任意逻辑函数。辑函数。公式公式X10=X1X10=X1和和X11=/X1X11=/X1分别表示将变量与分别表
5、示将变量与常数常数0 0和和1 1作异或运算就可以求原变量和反变量，因此可以作异或运算就可以求原变量和反变量，因此可以得出下述结论：只用原变量（或只用反变量）和与异或得出下述结论：只用原变量（或只用反变量）和与异或运算就可以表示出任何逻辑函数。运算就可以表示出任何逻辑函数。逻辑函数的异或表达形式在可测性设计以及在一些公逻辑函数的异或表达形式在可测性设计以及在一些公式的证明中是非常有用的。式的证明中是非常有用的。12 4.4.用卡诺图作异或运算用卡诺图作异或运算 用公式法来求两个函数的异或值是很用公式法来求两个函数的异或值是很繁琐的，但是用卡诺图来做却是异常简单繁琐的，但是用卡诺图来做却是异常简
6、单的，具体方法如下的，具体方法如下:将表示逻辑函数将表示逻辑函数f1f1和和f2f2的卡诺图（必须的卡诺图（必须有相同个输入变量）重叠在一起，逐一检有相同个输入变量）重叠在一起，逐一检查相同位置的最小项情况，如某个最小项查相同位置的最小项情况，如某个最小项包含于包含于f1f1和和f2f2中，或都不包含于中，或都不包含于f1f1和和f2f2中，中，则异或结果中该最小项为则异或结果中该最小项为0 0；如某个最小项；如某个最小项只包含于只包含于f1f1和和f2f2中的任意一个（只有一个）中的任意一个（只有一个），则异或结果中该最小项为，则异或结果中该最小项为1 1。135 5逻辑函数的展开定理逻辑函
7、数的展开定理14第三节第三节 布布 尔尔 差差 分分 法法15定定 义义16一阶布尔差分定定 义：义：17定义了函数定义了函数f f对于对于XiXi的一阶布尔差分后，则可得的一阶布尔差分后，则可得到诊断故障到诊断故障Xi(s-a-1)Xi(s-a-1)和和Xi(s-a-0)Xi(s-a-0)的测试矢量的测试矢量分别为：分别为：18一阶布尔差分的计算公式一阶布尔差分的计算公式1920举举 例例21高高 阶阶 布布 尔尔 差差 分分 一阶布尔差分是用来求单故障测试矢量一阶布尔差分是用来求单故障测试矢量集的。如果要求多故障的测试矢量集，就集的。如果要求多故障的测试矢量集，就必须使用高阶布尔差分的概念
8、。这里主要必须使用高阶布尔差分的概念。这里主要叙述二阶布尔差分及双故障测试矢量集的叙述二阶布尔差分及双故障测试矢量集的求法。更高阶的布尔差分和多故障测试矢求法。更高阶的布尔差分和多故障测试矢量集产生方法可依此类推。量集产生方法可依此类推。2223第 四 节 *D 算 法24D D 算算 法法事实上，要检测或诊断某一个故障往往只事实上，要检测或诊断某一个故障往往只需找到其中一个或一些测试矢量就能满足需找到其中一个或一些测试矢量就能满足实际工作的需要。实际工作的需要。D D算法就是其中的一种重算法就是其中的一种重要方法。罗思（要方法。罗思（RothRoth）在）在19661966年提出的年提出的D
9、 D算算法对于任意非冗余的组合电路中的故障均法对于任意非冗余的组合电路中的故障均能找到某个（某些）故障的测试矢量，而能找到某个（某些）故障的测试矢量，而且它的计算方法很容易用计算机来实现。且它的计算方法很容易用计算机来实现。251.1.函函 数数 的的 D D 立立 方方262.2.故故 障障 D D 立立 方方 在元件E的输出处可产生故障信号D(/D）的最小输入条件叫做故障D立方。其中D表示正常电路输出为1，故障时输出为0，简记为D=1/0；/D则反之，简记为/D=0/1。如果用B表示正常电路的奇异立方，用a表示故障电路的奇异立方则有：273.3.传传 播播 D D 立立 方方定义：把元件定
10、义：把元件E E输入端的若干故障信号能传播至输入端的若干故障信号能传播至E E的输出端的输出端的最小输入条件叫做传播的最小输入条件叫做传播D D立方。立方。计算方法：计算方法：284.D 4.D 驱驱 赶赶定义：逐级将故障信号定义：逐级将故障信号D D（/D/D）从故障点敏化至可及输出端）从故障点敏化至可及输出端的过程叫做的过程叫做D D驱赶（驱赶（D drive).D drive).D D驱赶的具体做法：是将输入端有驱赶的具体做法：是将输入端有D(/DD(/D）信号而输出值）信号而输出值尚尚未确定的元件（这种元件叫做未确定的元件（这种元件叫做D D激活元件）的传播激活元件）的传播D D立方同
11、立方同测试立方作求交运算测试立方作求交运算，使该元件输出，使该元件输出D D或或/D/D信号（即将错误信号（即将错误信号信号D D或或/D/D驱赶通过该元件）。如果该交存在，说明本次驱驱赶通过该元件）。如果该交存在，说明本次驱赶成功，否则不成功。驱赶过程中的求交运算按下表进行。赶成功，否则不成功。驱赶过程中的求交运算按下表进行。295.5.蕴蕴 涵涵 定义：在定义：在D D驱赶过程中会确定某些线上的值，驱赶过程中会确定某些线上的值，从而有些元件的输出值已经唯一确定了，从而有些元件的输出值已经唯一确定了，此时应把这些值及时确定下来，这个确定此时应把这些值及时确定下来，这个确定那些已经唯一确定值的
12、过程叫做蕴涵那些已经唯一确定值的过程叫做蕴涵 (implication)(implication)。蕴涵的具体求法：是蕴涵的具体求法：是将与新确定值有关的将与新确定值有关的各元件的奇异立方同测试立方求交各元件的奇异立方同测试立方求交。如果。如果先确定的是该元件的输入端值，则求交之先确定的是该元件的输入端值，则求交之后可以确定它的输出值，这叫前向蕴涵。后可以确定它的输出值，这叫前向蕴涵。如果先确定的是元件如果先确定的是元件EiEi的输出值，则求交的输出值，则求交之后可以确定它的输入值，这叫后向蕴涵。之后可以确定它的输入值，这叫后向蕴涵。306.6.线线 确确 认认 和和 相相 容容 性性 检检
13、查查 定义：定义：线确认（线确认（line justificationline justification）是相容）是相容性检查（性检查（consistencyconsistency）的一种。所谓相容性检查）的一种。所谓相容性检查是指在一次是指在一次D D驱赶成功之后，还要检查一下所得测驱赶成功之后，还要检查一下所得测试立方是否与元件的奇异立方（已经确定了的）试立方是否与元件的奇异立方（已经确定了的）有矛盾，以便及早发现矛盾而及早返回。有矛盾，以便及早发现矛盾而及早返回。相容性检查的具体做法：是将测试立方与该次相容性检查的具体做法：是将测试立方与该次D D驱驱赶过程中没有使用到的元件的已确定的
14、奇异立方赶过程中没有使用到的元件的已确定的奇异立方逐一求交，如果对每个元件至少能找到一个相容逐一求交，如果对每个元件至少能找到一个相容的奇异立方，则相容性检查通过，此时才称该次的奇异立方，则相容性检查通过，此时才称该次D D驱赶完全成功。如果相容性检查没有通过，此次驱赶完全成功。如果相容性检查没有通过，此次D D驱赶仍未成功，应该及时返回到上一个选择点。驱赶仍未成功，应该及时返回到上一个选择点。31举举 例例3233343536第第 五五 节节 伪伪 穷穷 举举 法法37穷穷 举举 法法定义：把所有可能的定义：把所有可能的XiXi都作为输入矢量，然后观察其响应都作为输入矢量，然后观察其响应是否
15、与原设计相符，以鉴别其是否有故障。是否与原设计相符，以鉴别其是否有故障。180180个输入端个输入端 2 2180180=1.53x10=1.53x105454 若施加及观察一个测试矢量需若施加及观察一个测试矢量需0.1us0.1us（10MHz10MHz）则需：则需：1.53x101.53x104747秒；秒；约合：约合：4.8x104.8x103939年年38单单 输输 出出 电电 路路单输出电路：只有一个可及（可测量）输单输出电路：只有一个可及（可测量）输出端的电路。出端的电路。无扇出电路：任一元件的输出信号或原始无扇出电路：任一元件的输出信号或原始输入信号都只送到一个元件的输入端。输入
16、信号都只送到一个元件的输入端。有扇出电路：若干个元件的输出信号或若有扇出电路：若干个元件的输出信号或若干原始输入信号送到两个或两个以上的元干原始输入信号送到两个或两个以上的元件的输入端。件的输入端。39组合电路的树型表示法组合电路的树型表示法40电电 路路 的的 分分 块块主要思想：把电路分割成若干小块，以减少测试矢量。主要思想：把电路分割成若干小块，以减少测试矢量。举例：举例：问题：应在电路的什么地方进行分割？问题：应在电路的什么地方进行分割？41无无 扇扇 出出 电电 路路特点：一个具有特点：一个具有n n个输入端的组合电路，其中：个输入端的组合电路，其中：（1 1）任意一个门的输出只与一
17、组具有）任意一个门的输出只与一组具有k k个输入变量个输入变量的子集有关，而与其余（的子集有关，而与其余（n-kn-k）个输入端无关。）个输入端无关。（2 2）每多分出一个子块则增加一个伪输入端。）每多分出一个子块则增加一个伪输入端。若把一个电路分成若把一个电路分成s s块，则该电路等效输入端为块，则该电路等效输入端为（s+n-1s+n-1）个（包括原始输入与伪输入）。不失一般）个（包括原始输入与伪输入）。不失一般性，设这性，设这s s块电路对应的等效输入端分别为块电路对应的等效输入端分别为AiAi（i=1i=1，2 2，s),s),则有：则有：为了穷举测试具为了穷举测试具AiAi个输入端的子
18、块，必须有个输入端的子块，必须有2 2AiAi个测个测试矢量，穷举整个测试电路需：试矢量，穷举整个测试电路需：可以证明：只有当可以证明：只有当A1=A2=AsA1=A2=As时（即输入端数相等）时（即输入端数相等），所需的测试矢量数量少。，所需的测试矢量数量少。42例例 子子43有扇出会聚的单输出电路有扇出会聚的单输出电路在穷举在穷举g g时，必须选择合适的时，必须选择合适的X XA A才能使才能使e e信号传输信号传输至至Z Z。如不存在这样的矢量。如不存在这样的矢量X XA A，则，则g g中的故障在加中的故障在加所有的所有的X XA A时是时是“无关紧要无关紧要”的，因此可把这些测的，因
19、此可把这些测试从试从XeXe中略去。中略去。在穷举在穷举f f时，必须利用时，必须利用Xe-XXe-XA A中的原始输入端来控中的原始输入端来控制制e e电平。但如某组电平。但如某组X XA A已确定了已确定了e e的电平，即已同的电平，即已同Xe-XXe-XA A的选择无关，即的选择无关，即f f（X XA A，1 1）或）或f f（X XA A，0 0）不）不会出现，因而也没有必要去测试它。会出现，因而也没有必要去测试它。对于电路要分成两块以上，由于各块的对于电路要分成两块以上，由于各块的X XP P（eiei）不同，情况要更复杂一些，也没有象无扇出电路不同，情况要更复杂一些，也没有象无扇
20、出电路那样，分块方法有一个基本原则可循，分块方案那样，分块方法有一个基本原则可循，分块方案很多，往往要作各种方案的比较选优。很多，往往要作各种方案的比较选优。44多多 输输 出出 电电 路路一个具有一个具有m m个输出端的多输出电路，如果每一个输个输出端的多输出电路，如果每一个输出都与全部的原始输入信号有关，则相当于有出都与全部的原始输入信号有关，则相当于有m m个个单输出电路，可以分别用单输出电路分块方法来单输出电路，可以分别用单输出电路分块方法来解。解。若多输出电路中若干个输出信号均只同部分原始若多输出电路中若干个输出信号均只同部分原始输入端有关，则在测试其中某个输出端时只使用输入端有关，
21、则在测试其中某个输出端时只使用部分输入端，而其它原始输入端都是自由项，利部分输入端，而其它原始输入端都是自由项，利用这些自由项及部分已使用的原始输入端可以同用这些自由项及部分已使用的原始输入端可以同时测试其中的另一些输出端，因此可以进一步减时测试其中的另一些输出端，因此可以进一步减少测试整个电路的测试矢量数。少测试整个电路的测试矢量数。讨论核心：如何充分发挥每个测试矢量的测试功讨论核心：如何充分发挥每个测试矢量的测试功能，以进一步减少测试电路的测试矢量数。能，以进一步减少测试电路的测试矢量数。45第第 六六 节节 特特 征征 分分 析析 法法46常常 用用 的的 特特 征征 分分 析析 法法线
22、性反馈移位寄存器（线性反馈移位寄存器（LFSRLFSR）组成）组成的特征分析器的特征分析器跳变次数测试（跳变次数测试（TCTC）症候群（症候群（syndromesyndrome）测试）测试47一个响应序列的特征应该满足如下几个条件：一个响应序列的特征应该满足如下几个条件：（1 1）这个特征应尽可能多地保留原序列中的有用）这个特征应尽可能多地保留原序列中的有用（即对故障检测和诊断有用的）信息。同时，各（即对故障检测和诊断有用的）信息。同时，各序列的特征应有较明显的差异，尽量做到各种不序列的特征应有较明显的差异，尽量做到各种不同的序列应有不同的特征。同的序列应有不同的特征。（2 2）从序列中提取特
23、征的方法应尽可能简单，特征）从序列中提取特征的方法应尽可能简单，特征的长度应尽可能短。的长度应尽可能短。（3 3）为了应用特征来检测或诊断故障，对激励信号）为了应用特征来检测或诊断故障，对激励信号的要求应比较简单而松弛。的要求应比较简单而松弛。（4 4）响应序列之间的与、或和非序列的特征与原序）响应序列之间的与、或和非序列的特征与原序列的特征之间最好要有比较简单的逻辑关系。列的特征之间最好要有比较简单的逻辑关系。48 2.2.线性反线性反馈移位寄存器馈移位寄存器 49 脉冲数脉冲数 D1 D2 D3 D4 D1 D2 D3 D4 0 1 1 1 10 1 1 1 1 1 0 1 1 1 1 0
24、 1 1 1 2 0 0 1 1 2 0 0 1 1 3 0 0 0 1 3 0 0 0 1 4 1 0 0 0 4 1 0 0 0 5 0 1 0 0 5 0 1 0 0 6 0 0 1 0 6 0 0 1 0 7 1 0 0 1 7 1 0 0 1 8 1 1 0 0 8 1 1 0 0 9 0 1 1 0 9 0 1 1 0 10 1 0 1 1 10 1 0 1 1 11 0 1 0 1 11 0 1 0 1 12 1 0 1 0 12 1 0 1 0 13 1 1 0 1 13 1 1 0 1 14 1 1 1 0 14 1 1 1 0 15 1 1 1 1 15 1 1 1 1 5
25、0 脉冲数脉冲数 D1 D2 D3 D4 D1 D2 D3 D4 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 *1 0 1 1 1 *2 0 0 1 1 2 0 0 1 1 3 1 0 0 1 3 1 0 0 1 4 1 1 0 0 4 1 1 0 0 5 1 1 1 0 5 1 1 1 0 6 0 1 1 1 *6 0 1 1 1 *7 0 0 1 1 7 0 0 1 151由由LFSRLFSR组成的特征分析器组成的特征分析器 1.1.序列的多项式表示法序列的多项式表示法有一个有一个n n位长的序列位长的序列在迦罗华域在迦罗华域GF(2)GF(2)上用多项式上用多项式52r
26、r 次次 本本 原原 多多 项项 式式在迦罗华域在迦罗华域GF(2GF(2）上用多项式）上用多项式表示，其中符号和一均理解为异或运算。如果表示，其中符号和一均理解为异或运算。如果F(xF(x）是一个质多项式（不能做因式分解），且）是一个质多项式（不能做因式分解），且能整除多项式能整除多项式 ，而不能整除任何幂次，而不能整除任何幂次低于低于 的任何多项式，那么称的任何多项式，那么称F(x)F(x)是一个是一个r r次本原多项式。次本原多项式。532.N2.N位长的线性移位寄存器位长的线性移位寄存器54特特 点点1.1.如果如果h h（x x）是本原多项式，则其表示的线）是本原多项式，则其表示的线
27、性反馈移位寄存器具有最大的周期，而且性反馈移位寄存器具有最大的周期，而且最大周期是最大周期是2 2n n-1,-1,2.2.因此，要构造具有最大周期的因此，要构造具有最大周期的n n位位LFSRLFSR，只，只要寻找要寻找n n次本原多项式就可以了。对于不同次本原多项式就可以了。对于不同的的n n一定有不同的本原多项式，而对于同一一定有不同的本原多项式，而对于同一个个n n值也可能有不同的多项式（即本原多项值也可能有不同的多项式（即本原多项式不具有唯一性）。本原多项式的求法是式不具有唯一性）。本原多项式的求法是比较麻烦的，但现在已有现成的表可以查比较麻烦的，但现在已有现成的表可以查到，下面列出
28、其中常用的本原多项式到，下面列出其中常用的本原多项式：55常常 用用 的的 本本 原原 多多 项项 式式56特特 点点3.3.需要指出的一点是：前面所表达的多项式是本原需要指出的一点是：前面所表达的多项式是本原多项式的必要条件是至少存在一个多项式的必要条件是至少存在一个hihi不等于不等于0 0，即即h(xh(x）中至少包含两项含有）中至少包含两项含有x x的项。的项。4.4.如果如果h h（x x）是本原多项式，那么多项式）是本原多项式，那么多项式 也是本原多项式，这也就进一步说明了本原多项式也是本原多项式，这也就进一步说明了本原多项式的不唯一性。的不唯一性。573 3伪随机信号发生器伪随机
29、信号发生器 LFSRLFSR的输出信号在实际使用中，经常可以作为伪随机信号使用的输出信号在实际使用中，经常可以作为伪随机信号使用三个随机性特征：三个随机性特征：R1 R1特征特征1 1：在序列：在序列aiai的每一个周期里，的每一个周期里，aiai取取0 0和和1 1两种值的概率相等，即在序列的每两种值的概率相等，即在序列的每个周期中，两个不同值出现的次数应该近似相等。个周期中，两个不同值出现的次数应该近似相等。R2 R2特征特征2 2：在序列中同一值的连续出现称为一次游动；在一次游动中出现的相同值的：在序列中同一值的连续出现称为一次游动；在一次游动中出现的相同值的个数称为这个游动的长度。伪随
30、机序列中应该有：长度为个数称为这个游动的长度。伪随机序列中应该有：长度为1 1的游动占的游动占1/21/2，长度为，长度为2 2的游动的游动占占1/4,.1/4,.，即长度为，即长度为k(kk(k应小于序列的周期应小于序列的周期r r）的游动应占）的游动应占1/2k1/2k。0 0和和1 1两种值的同两种值的同长度游动次数应相等。长度游动次数应相等。R3 R3特征特征3 3：伪随机序列：伪随机序列aiai的自相关函数应是二值的，即的自相关函数应是二值的，即 其中其中K K与与t t无关。这个特征表明序列无关。这个特征表明序列aiai中各个元素的独立性。中各个元素的独立性。C(r)C(r)越小，
31、则越小，则aiai之间之间的相关性越小。的相关性越小。58 4 4用具有量大周期的用具有量大周期的LFSRLFSR组成的特征分析器组成的特征分析器 59 5 5特特 征征 的的 计计 算算 方方 法法 上面所说的输入序列的特征是通过硬件电路上面所说的输入序列的特征是通过硬件电路LFSRLFSR来提取的，事实来提取的，事实上也可以通过软件计算来得到。下面我们来说明，只要通过作简单的上也可以通过软件计算来得到。下面我们来说明，只要通过作简单的长除法就可以求得输入序列的特征长除法就可以求得输入序列的特征R R和输出序列，同时证明输入序列和输出序列，同时证明输入序列M(x),M(x),输出序列输出序列
32、Q(x),Q(x),特征多项式特征多项式r(x)r(x)与与LFSRLFSR的特征多项式之间存在关的特征多项式之间存在关系系60长长 除除 法法 61举举 例例 求输入序列求输入序列1011011010110110移入特征多项式为移入特征多项式为x4x4x x1 1的特征分析器后的特征分析器后的输出序列的输出序列Q Q和特征和特征R R。解：应用长除法得解：应用长除法得62 第第 七七 节节 症症 候候 群群 测测 试试（非重点）（非重点）63 1 1函函 数数 的的 症症 候候 群群 如果一个电路有如果一个电路有n n个原始输入端，则由这个原始输入端，则由这n n个输个输入变量组成的最小项有
33、入变量组成的最小项有2n2n个。而函数个。而函数f f所包含的所包含的不同的最小项数（即使不同的最小项数（即使f=1f=1的最小项数）为的最小项数）为k k个，个，则定义则定义 为函数为函数f f的症候群。的症候群。642 2症候群的运算规则症候群的运算规则 65举举 例例图错，s1,s2处为OR门66症候群可测的充分必要条件症候群可测的充分必要条件 若函数若函数f=AXi+B(/Xi)+Cf=AXi+B(/Xi)+C，其中表式，其中表式A A，B B和和C C中中没有变量没有变量XiXi和和/Xi/Xi（XiXi可以是原始输入端变量，也可以是原始输入端变量，也可以是中间变量），则为使可以是中间变量），则为使XiXi点的故障是症候群点的故障是症候群可测的充分必要条件是：可测的充分必要条件是：67