第5章专用可测性设计.PPT

1、南京航空航天大学 信息科学与技术学院 电子工程系,第5章 专用可测性设计,本章主要内容 可测性分析 可测性的改善方法 测试图形简化 容易测试的电路 组合电路的可测性设计 时序电路可测性设计中的问题,南京航空航天大学 信息科学与技术学院 电子工程系,概述 在当今的VLSI电路中，可测性设计结构是理想化的、广为自愿接受的设计技术。关于可测性目前还没有正式定义。 可测性的概念应该包含两方面的内容： （1）电路内的故障是否可以用有限的测试图形来检测或定位； （2）故障效应观察的难易程度。即，检测故障所需的测试图形的长度和生成时间、施加时间长度的问题。,可测性设计这门学科开始于专用设计技术。 专用可测性

2、设计常用的方法是用可测性的度量值来寻找有限的附加测试点和控制点，以提高电路的可观性和可控性，从而提高电路的可测性。 随着可测性技术理论的发展和应用的深入，系统化的可测性设计技术也得以迅速发展，如：路径扫描、内建自测试和边界扫描技术的应用更加广泛，成为VLSI可测性设计和应用的主流。,南京航空航天大学 信息科学与技术学院 电子工程系,可测性分析中用两个术语来表达此意思，一个是可控性，另一个是可观性。 可控性表明把电路中节点置为预定逻辑值的难易程度； 可观性表明电路中任意节点的值在原始输出可观察的难易程度。 为了对可测性进行量化分析，Goldstein于1979年提出了可测性度量的概念，于1980

3、年提出的SCOAP可测性度量受到广泛接受。 SCOAP可测性度量规定 电路中每个节点由6个参量来描述： 组合0可控性(CC0)，组合1可控性(CC1)，时序0可控性(SC0)， 时序1可控性(SC1)，组合可观性(CO)，时序可观性(SO)。,5.1 可测性分析,南京航空航天大学 信息科学与技术学院 电子工程系,定义5.1 欲置节点N的值为组合逻辑值0(1)，需要对相关节点赋以确定组合逻辑值的最少赋值次数，称为节点N的组合0(1)可控性值，用 CC0(N)(CC1(N)表示。 定义5.2 欲置节点N的值为时序0(1)，需要对相关节点赋以确定时序逻辑的最少赋值次数，称为节点N的时序0(1)可控性

4、值，用SC0(N)(SC1(N)表示。实际上，时序可控性值提供了控制节点所需的时段数。,5.1.1 可控性值的估计,基本逻辑单元的CC0(N),CC1(N),SC0(N),SC1(N)的计算公式： (1)对于原始输入节点PI，只需按组合节点赋值一次，不需按时序节点赋值，因此： CC0(PI) = CC1(PI) =1 SC0(PI) = SC1(PI) =0,南京航空航天大学 信息科学与技术学院 电子工程系,(3)对于“非”逻辑元件y = ，其计算与缓冲器一样，但要注意非逻辑，因此有： CC0(y) = CC1(x) + 1 CC1(y) = CC0(x) + 1 SC0(y) = SC1(x

5、) SC1(y) = SC0(x),(2)对于缓冲器y=x，要确定y的值，那么y比x要多一次组合节点赋值，而缓冲器中不是时序元件，因此有: CC0(y) = CC0(x) + 1 CC1(y) = CC1(x) + 1 SC0(y) = SC0(x) SC1(y) = SC1(x),南京航空航天大学 信息科学与技术学院 电子工程系,(4)对于二输入与门y = ，要使y=0， 与 中只需一个为0即可，但要使y=1，则必须 与 同时为1，因此有； CC0(y) = minCC0(x1),CC0(x2) + 1 CC1(y) = CC1(x1) + CC1(x2) + 1 SC0(y) = minS

6、C0(x1) , SC0(x2) SC1(y) = SC1(x1) + SC1(x2),(5)对于二输入或门y = x1 + x2，要使y = 0 ,则x1与x2必须为0，要使y=1，x1与x2中只需一个为1即可，因此有； CC0(y) = CC0(x1) + CC0(x2) + 1 CC1(y) = minCC1(x1) , CC1(x2) + 1 SC0(y) = SC0(x1) + SC0(x2) SC1(y) = minSC1(x1) , SC1(x2),(6)对于三输入或非门 ，要使y=0， 中只需一个为1即可；要使y=1，则必须 因此有： CC0(y) = minCC1(x1) ,

7、 CC1(x2) , CC1(x3) + 1 CC1(y) = CC0(x1) + CC0(x2) + CC0(x3) + 1 SC0(y) = minSC1(x1) , SC1(x2) , SC1(x3) SC1(y) = SC0(x1) + SC0(x2) + SC0(x3),表5.1 典型的组合逻辑门的可控性值,南京航空航天大学 信息科学与技术学院 电子工程系,(7)对于图5.1中带复位端的负边沿触发D触发器，可由功能表达式求得可控性值：,图5.1 D触发器,CC0(Q) = minCC1(R)+CC0(C),CC0(D)+CC1(C)+CC0(C)+CC0(R) CC1(Q) = CC

8、1(D)+CC1(C)+CC0(C)+CC0(R) 注意：式中CC1(C)+CC0(C)表示把触发脉冲C先置成1，再置成0，用两个电 平来模拟一个负脉冲，因为该触发器是负边沿触发。 同理可得： SC0(Q) = minSC1(R)+SC0(C),SC0(D)+SC1(C)+SC0(C)+SC0(R) SC1(Q) = SC1(D)+SC1(C)+SC0(C)+SC0(R),若要观察输出Q，则需保持R=0，同时C加一个负脉冲。,南京航空航天大学 信息科学与技术学院 电子工程系,例5.1 试计算图中输入节点的可控性值。,用输入门的序号来标记节点: A1,A2,B1,B2,C1,C3,H4,H5。设

9、定原始输入为最前面的节点， 原始输出为最后面的节点，先算前面的节点，每一个节点的逻辑值由前面节点的逻辑值确定。,所有的原始输入及其分支的 可控性值设为1； 所有其他节点的可控性值初始化 为无穷大()，计算完毕后，仍然保持为的节点为不可控的。,CC0(F) = minCC0(A),CC0(B),CC0(C)+1 = 2 CC1(F) = CC1(A)+CC1(B)+CC1(C)+1 = 4 CC0(H) = CC1(A)+CC1(B)+1 = 3 CC1(H) = minCC0(A),CC0(B)+1 = 2 CC0(G) = CC1(C)+1 = 2 CC1(G) = CC0(C)+1 = 2

10、,南京航空航天大学 信息科学与技术学院 电子工程系,电路中每个原始输出节点的可控性值为： CC0(Y) = CC0(F)+CC0(H)+1 = 6 CC1(Y) = minCC1(F),CC1(H)+1=3 CC0(Z) = CC1(G)+CC1(H)+1 = 5 CC1(Z) = minCC0(G),CC0(H)+1 = 3,可控性值表示了对电路中节点置预定逻辑值的成本，随着节点在电路中深度的增加，成本也增加。,南京航空航天大学 信息科学与技术学院 电子工程系,定义5.3 为把节点N的信息传播到原始输出，所需最少的组合逻辑值赋值次数叫做节点N的组合可观性值，用CO(N)表示。 定义5.4 为

11、把节点N的信息传播到原始输出，所需最少的时序逻辑赋值次数叫做节点N的时序可观性值，用SO(N)表示。,5.1.2 可观性值,基本逻辑单元的可观性计算公式： (1)对原始输出PO，从它到原始输出PO之间的组合和时序单元数均为0，不需要对任何组合节点赋值和对时序节点控制就能直接观察，假定原始输出的可观性值为1，则有： CO(PO) = SO(PO) = 1 (2)对于缓冲器y=x，从x到y只有一个标准组合单元，不需要任何条件，因此有： CO(x)=CO(y)+1 SO(x)=SO(y),南京航空航天大学 信息科学与技术学院 电子工程系,(3)对于非门y= ，它的分析方法与缓冲器一样，有： CO(x

12、)=CO(y)+1 SO(x)=SO(y),(4)对于二输入与门y=x1x2，要观察x1必须控制x2=1； 要观察x2必须控制x1=1； CO(x1) = CO(y) +CC1(x2) + 1 CO(x2) = CO(y) +CC1(x1) + 1 SO(x1) = SO(y) + SC1(x2) SO(x2) = SO(y) + SC1(x1) (5)对于二输入或门y=x1+x2，要观察x1必须控制x2=0；要观察x2必须控制x1=0； CO(x1) = CO(y) +CC0(x2) + 1 CO(x2) = CO(y) +CC0(x1) + 1 SO(x1) = SO(y) + SC0(x

13、2) SO(x2) = SO(y) + SC0(x1),南京航空航天大学 信息科学与技术学院 电子工程系,(6)对于三输入或非门 ，要观察 xi(i=1,2,3)，必须控制 xj(j=1,2,3;ji)=0和xk(k=1,2,3;ki,j)=0, 因此有： CO(xi) = CO(y) + CC0(xj) + CC0(xk) + 1 SO(xi) = SO(y) + SC0(xj) + SC0(xk),表5.2 典型的组合逻辑门的可观性值,1是与门、与非门的非控制值；0是或门、或非门的非控制值。,(7)对于带复位端的负边沿触发D触发器 若要观察输入D，则需保持R=0，同时C加一个负脉冲，因此有

14、： CO(D) = CO(Q) + CC0(R) + CC1(C) + CC0(C) + 1 SO(D) = SO(Q) + SC0(R) + SC1(C) + SC0(C) 要观察R，需先置Q为1，然后保持时钟电平为低电平，因此有： CO(R) = CO(Q) + CC1(Q) + CC1(C) + CC0(C) + 1 SO(R) = SO(Q) + SC1(Q) + SC1(C) + SC0(C) 若要观察时钟线，在假定R、Q和D正常的情况下， 置Q=1，保持R=0，用一负脉冲从D线置入一个0， 若Q变为0，则说明时钟正常； 置Q=0，保持R=0，用一负脉冲从D线置入一个1， 若Q变为1

15、，则说明时钟正常。因此有： CO(C) = minCC1(Q)+CC0(R)+CC1(C)+CC0(C)+CC0(D)+CO(Q) CC0(Q)+CC0(R)+CC1(C)+CC0(C)+CC1(D)+CO(Q) SO(C) = minSC1(Q)+SC0(R)+SC1(C)+SC0(C)+SC0(D)+SO(Q) SC0(Q)+SC0(R)+SC1(C)+SC0(C)+SC1(D)+SO(Q),例5.2 试计算图5.2中节点的可观性值。,图5.2 计算可测性度量值示例电路,所有原始输出的可观性值设为1，所有其他节点的可观性值初始化为无穷大()，计算完毕后，仍然保持为的节点则为不可观的。,先算

16、第二级节点F，G和H的可观性值。 控制H为0使得F敏化到原始输出Y，F在Y的可观性值为： COY(F) = CO(Y) + CC0(H) + 1 = 5 G在Z的可观性值为： COZ(G) = CO(Z) + CC1(H) + 1 = 4 观察节点H有两条路径，一条是H4Y，一条是H5Z，两个可观性值为： COY(H) = CO(Y) + CC0(F) + 1 = 4 COZ(H) = CO(Z) + CC1(G) + 1 = 4,南京航空航天大学 信息科学与技术学院 电子工程系,每一个原始输入A、B、C相应地也有两个可观性值： COYH(A) = COY(H) + CC1(B) + 1 =

17、6 AHY COZ(A) = COZ(H) + CC1(G) + 1 = 7 AHZ COY(C) = COY(F) + CC1(A) + CC1(B) + 1 = 8 CFY COZ(C) = COZ(G) + 1 = 5 CGZ 图5.2中所有节点的可观度量值如表5.3所示。,由表可以看出：可观性随着电路深度而变化，原始输出的可观性值小，而原始输入的可观性大。 可观性值代表了在原始输出观察节点逻辑值所付出的成本。,表5.3 图5.2所有节点的可观性度量值,右图是SCOAP算法中计算任意节点N的可控性值CCi(N)或SCi(N)(i=0,1)的流程图。 SCOAP算法中，设置一个先进先出的排

18、队表，称之为后继表。每次计算时都按顺序从后继表中取出一个元件，再调用标准元件的可控性值数据库算出该元件所有输出节点的可控性值。 后继指先得到元件的输入节点的可控性值，然后向后计算元件输出节点的可控性值。 为了防止重复计算，若节点的可控性值经计算已发生改变，则将计算的值(称为后继)保存在后继表，否则后继不进后继表。 另外，若节点的后继在后继表中已有，则新的后继也不进表，计算过程直到表空才结束。,5.2.3 SCOAP算法描述,计算可控性值的流程图,右图是SCOAP算法中计算任意节点N的可观性值COi(N)或SOi(N)(i=0,1)的流程图。 SCOAP算法中，为了方便计算节点的可观性值，设置一

19、个先进先出的排队表，称之为前趋表。每次计算时按顺序从该表中取出一个元件，再调用标准元件的可观性数据库和前面已求得的各元件可控性值，求出该元件所有输入节点的可观性值。对于扇出节点，取所有扇出分支中可观性值最小的作为扇出根节点的可观性值。 前趋指先得到元件输出节点的可观性值，然后向前计算元件输入节点的可观性值。 若某节点的可观性值在计算后没变，则其前趋不进前趋表。若表中已有某节点的前趋，该前趋也不入表。重复上述计算过程，直到各节点的可观性值稳定之后才结束。,计算可观性值的流程图,注意： 在SCOAP算法中，取所有扇出分支中可观性值最小的作为扇出根节点的可观性值，因此同一个扇出根节点和分支节点中只列

20、出一个节点。,5.2.4 可测性度量的应用,上图中主要节点的可控(观)性值,对于右图电路，运用SCOAP算法求得主要节点的可控性值和可观性值如表所示。,计算结果表明：重复计算太多，计算效率有待改善，时序控制性值和可观性值的初始值设得太小 ，使得计算出的时序可测性值与相应的组合可测性值小，显示不出时序电路测试复杂性，计算复杂性却很大，对重聚的扇出节点的可测性值处理粗糙。,可测性度量是衡量电路可测性的难易程度。在电路设计过程中应该对所设计的电路的可测性度量值进行估算，以分析电路的可测性。 可测性的概念应该包含两方面内容：电路内的故障是否可以用有限的测试图形来检测或定位；故障效应在原始输出可观察的难

21、易程度，也就是说检测故障所需的测试图形的长度和生成时间的长短问题。 可控性值表示了对电路中节点置为预定逻辑值的成本，随着节点在电路中深度的提高，成本也增加。,关于可测性分析有以下观点：,可观性值随着电路深度而变化。原始输出的可观性值小，原始输入的可观性值大。可观性值代表了在原始输出观察电路节点的逻辑值所付出的成本。 可控性值和可观性值同等重要。一个容易可观的节点并非都是可控的。表明，除非节点是可控的，否则单纯提高其可观性值无意义。 SCOAP可测性度量可以快速的分析测试生成的难易程度，并不生成测试图形。可测性分析所用的时间并不像测试生成那样长，一般与电路中的线条数成正比。,南京航空航天大学 信

22、息科学与技术学院 电子工程系,测试点有两类： 控制点(Control Point, CP) 改善电路可控性的原始输入 观察点(Observer Point, OP) 改善电路可观性的原始输出 由测试生成的知识及可控性、可测性的概念可以得出： 插入测试点可以使测试更容易,5.2 可测性的改善方法,5.2.1 插入测试点,1. 插入观察点 假如(a)中节点P的信号难以通过C2观察到，那么在节点P插入观察点OP，修改后的结构如图(b)所示。,南京航空航天大学 信息科学与技术学院 电子工程系,例5.3 研究图5.7(a)所示电路，它需要5个测试图形来检测所有的s-a故障，如果在F插入观测点OP，则只需

23、4个测试图形来检测所有故障，这样就可以缩短测试图形长度，改善测试。 但是，这样的观察点不能以随机的方式插入，例如在图5.7(b)中，在H点插入观察点不会减少测试图形，按照可测性分析，这点的组合可测性值很大。,图5.7 插入观察点举例,引入控制点CP为该或非门的另外输入，可将或非门的输出保持为低电平（图(c)）。 如果要求把图(a)中的P既可控制为0，也可控制为1，则插入两个控制点(图(e)。图(f)是采用多路选择器来实现插入控制点的一种结构。,2. 插入控制点,插入控制点易于把节点置为预设的逻辑值。,例:,图 (a)中从或非门输出端得不到0逻辑。,注意：插入控制点会影响节点的可控性值，同样也影

24、响节点的可观性。,改善了P点的可控性,但影响了C1的可观性,1,1,1,南京航空航天大学 信息科学与技术学院 电子工程系,一些存储器件的复位由复杂逻辑控制，初始化比较困难，插入测试点后就可初始化，左图 (a)电路是一种实现方法。,通过插入测试点初始化,测试点对改善长位数计数器的可测性非常有用。 例，对32位计数器进位端的s-a-0故障，需要施加232个测试图形。按照左图(b)插入控制点，就把电路分成C1和C2两部分，分别对它们进行测试，总共用的测试图形是217个。 （将电路分成2个16位计数器C1和C2，测试图形长度=216+216=217),时序电路中测试点插入的最终形式是扫描路径。,内建自

25、测试电路设计中，插入测试点是非常重要的，插入的控制点看做是原始输入的一部分。,南京航空航天大学 信息科学与技术学院 电子工程系,电路的可测性度量是其深度的函数，电路越小越容易测试。将一块大的电路分为几块小的子电路，就容易插入控制点和观察点。,5.2.2 电路分块,1. 硬件分块法 采用多个多路选择器，将子电路G1和G2非独立的部分隔离，可改善子电路的可控性和可观性（a）。 正常操作时附加的多路选择器是透明的（b）。,南京航空航天大学 信息科学与技术学院 电子工程系,如下图电路,可将其分块为3个子电路,和。 可加入二选一多路选择器，这样： 测试部分可直接观察部分(S=0或者S=1) ； 对输入施

26、加合适的值可同时测试电路的每一部分。,输入可控： 电路中的多路选择器可用于控制W端的输出，当对和电路分别测试时，w需要为0或者1，这可以通过控制二选一的输入端P来得到。 输出可观：电路的另一个多路选择器用于在电路的输出端观察与的输出。,P,南京航空航天大学 信息科学与技术学院 电子工程系,电路分块的第二种方法是对测试数据敏化，即敏化分块法。 假定将N输入的电路划分成M块，每块具有Ki个原始输入KiN，则穷举测试所有的分块电路的测试集的长度为 。,2. 敏化分块法,例：电路有8个原始输入，穷举测试的测试图形长度是256(28)。 将电路分为, 和 。 穷举测试电路须用8个测试图形，通过原始输出Z

27、1观察。 有3个输入，可通过Z1或Z2敏化。 有4个输入，可通过16个测试图形穷举测试。 总的测试长度是3个分块的测试长度之和，是32个测试图形。,南京航空航天大学 信息科学与技术学院 电子工程系,通过分块的并行测试使得测试图形极小化。 例如，分块的测试图形中有满足R=0的，而分块的测试图形中有满足W=0的，这两部分测试图形相结合可以减少测试图形长度。 类似地，分块的测试图形中有满足W1的，而分块的测试图形中有满足V1的，这两部分测试图形可同时施加。 用此方法 ，总的测试图形长度可由32个减为16个。,对分块电路测试敏化时，需保持W=0，观察分块电路的响应时需保持W=1。 对于分块电路，测试图

28、形应使得中R=0，或使分块中V=1，测试响应可通过Z1或Z2观察。,表5.5 图5.11所示电路的伪穷举测试,表5.5 图5.11所示电路的伪穷举测试,表5.5 图5.11所示电路的伪穷举测试,表5.5 图5.11所示电路的伪穷举测试,南京航空航天大学 信息科学与技术学院 电子工程系,W=0实现对的测试，W=1实现对的测试；块可通过Z1Z2观察。 总的测试图形长度可由32个减为20个。,5.3 测试图形简化 对于每一个原始输出只是原始输入子集的函数的电路，也可以采用分块技术生成精简的测试图形，分块后的子电路具有叠加的元件。,图5.13 电路C4,例: 图5.13所示的电路C4，有5个输入和3个

29、输出，每个输出均是原始输入集的子集的函数，输出函数为： f(a,b,c)=a(b+c) g(b,c,d)=d(b+c) h(e,d)=e+d,3个输出具有的原始输入的个数分别为3，3和2。 穷举测试整体电路需要32个测试图形。 如果一次只穷举测试一个输出，那么每个原始输出对应的穷举测试集的个数分别为8，8和4，总共是20个测试图形。,南京航空航天大学 信息科学与技术学院 电子工程系,如果两个输入从来没有在同一个输出函数中出现，那么就可对这两个输入施加相同的测试施加信号。,构造m行n列的相关矩阵，m是原始输出数，n是原始输入数。 每一行对应一个原始输出函数，每一列对应一个原始输入。如果输出函数与

30、相应的原始输入相关，则矩阵中对应的单元值为1，否则为0。, McCluskey于1984年提出并加以证明,基于此规律的技术称为最大测试并发。,例: f(a,b,c)=a(b+c) g(b,c,d)=d(b+c) h(e,d)=e+d,再对原始输入分块，使每一个分块所包含的输出函数不受两个或两个以上输入的影响 ，即，每一个矩阵分块中每一行中1的个数少于或等于1。,如，把a与d划为一分块，因为f与a有关而与d无关，g和h与d有关而与a无关，可把c(或b)与e合为一分块。这种分块方法并不唯一。,5.3.1 测试图形化简规律,南京航空航天大学 信息科学与技术学院 电子工程系,每一个矩阵分块中每一行中1

31、的个数少于或等于1，测试时可以对同一分块中的变量赋相同的值。 K是一行中1的最大个数，称为最大相关。可以确定测试图形总的个数，即2K。 本例只需施加8(23)个测试图形即可伪穷举测试整块电路，比穷举测试（256）减少75%。,表5.7 电路C4的测试集 对应分块ad,b,ce,例 图5.13所示电路C3，有8个原始输入及两个原始输出Z1和Z2，每个原始输出与原始输入的子集有关。 穷举测试两个分块电路的测试集长度分别为32（5个输入）和64（6个输入），则整块电路的测试长度是96，不用分块方法时整块电路的穷举测试的测试集长度是256。,图5.13 对电路C3的验证测试,共享输入端的一些信号是两个

32、分块电路的测试图形共用的，可对这个长度为96的测试集进一步化简。,(a) 相关矩阵,(b) 输入分块,最大的相关度为6，测试图形长度=64.,例5.5 对图5.14所示电路寻找最小的测试集。,最大的相关度为3，测试图形长度=8.,5.3.2 测试图形简化规律应用,(a) 相关矩阵,(b) 输入分块,(c) 特征相关矩阵,南京航空航天大学 信息科学与技术学院 电子工程系,结构上有规律的电路一般由相同的单元组成，排列成一维或多维阵列方式。如RAM、FPGA、阵列复选等典型电路等，单元结构可能是组合电路，也可能是时序电路。,图5.16 有规律的结构,5.4 容易测试的电路,南京航空航天大学 信息科学

33、与技术学院 电子工程系,有规律的组合电路一般是指迭代的逻辑阵列。 例如： （1）n位比较器（一维阵列），每一阵列单元对两个数字按位比较； （2）奇偶树，阵列单元是两输入的异或门； （3）组合电路乘法器则是二维阵列，阵列单元是某种类型的全加器。 迭代的逻辑阵列的C可测性 指迭代的逻辑阵列电路中，那些容易用常数测试图形进行测试，且测试图形与电路的大小(阵列单元个数)无关的特性。 常数测试图形指测试图形的格式和代码固定。,南京航空航天大学 信息科学与技术学院 电子工程系,对于左图所示的一维阵列，假定Tc是阵列中任意一个单元j的穷举测试集，该测试可将单元j的所有故障敏化到输出，而Rc是单元j对该测试的

34、测试响应。 若Rc Tc，则Rc可穷举测试单元j(故障支配关系)，因此任意一单元j的测试集就是Tc与图形Vj的并集。 同样的，如果有Rc Tc，则Rc与图形Vj1的并集就是单元(j+1)的测试，Rc与Tc不必顺序相同。 依此规律可以探索出此类电路测试图形的构成。,C可测性,用C可测性得到的测试集,Rci+1=ab+aRci+bRci 进位,sum=a bTc= V1 Tc 和,V1=(a,b),全加器,按公式,按公式,南京航空航天大学 信息科学与技术学院 电子工程系,如图所示的阵列结构，其单元都是全加器。 Tc0,1， Vj00,01,10,11， Rcj0,1。 则Tc与Vj的并集或Rcj与

35、Vj的并集只有8个测试图形。 因此,用8个穷举测试图形就足以测试此阵列电路。,5.4.1 部分积乘法器的C可测性,例5.6 分析N输入的奇偶树可用4个测试图形容易测试。,图5.16 8输入的奇偶树,解：奇偶树是无扇出的电路，其测试集应包括测试原始输入故障的测试图形。 已知穷举测试二输入异或门的4个测试图形是： RS 00,01,10,11,图5.16 奇偶树,对奇偶树两个原始输入施加穷举测试集并分别以R和S命名，测试响应输出的以T命名。 为了观察原始输出，对门2的另一个输入可施加信号0或1，这里对门2同时施加序列R和T进行穷举测试，则原始输出的测试图形是S。,奇偶树的3个测试图形具有这样的特性

36、: ViVj Vk Vi，Vj和Vk分别选自测试图形集R、S和T，无固定顺序，只要这3个图形互不相同。 将8输入奇偶树按此符号标识，标识后的输入结构如图5.16(c)所示。,南京航空航天大学 信息科学与技术学院 电子工程系,对于8输入奇偶树，测试集是4个图形，为：,此方法成功用于奇偶校验电路的可测性确定中。,南京航空航天大学 信息科学与技术学院 电子工程系,5.5 组合电路的可测性设计,5.5.1 用Reed-Muller模式设计组合电路,1. Reed-Muller扩展式 对于一个n输入变量(x1,x2,xn)的组合电路，实现的逻辑功能可用布尔函数F (x1,x2,xn)表达，也可用Reed

37、-Muller扩展式表达：,任何一个组合逻辑均可用异或门来实现，基于这种方法所设计的电路虽然比原电路复杂，但测试十分简单，只需用确定的测试图形就可以检测电路中所有的单故障，而与电路实现的功能完全无关。,南京航空航天大学 信息科学与技术学院 电子工程系,例如，对于三输入变量的函数F(x1,x2,x3)，用式(5.1)得到：,Ci（i：02n-1，即，07）的值可以依下列表达式计算：,k=0 k=1 k=1 k=1 k=2 k=2 k=2 k=3,，k=2, x1x2的4种组合, k=3, x1x2x3的8种组合,k=2, x1x3的4种组合,k=2, x2x3的4种组合,南京航空航天大学 信息科

38、学与技术学院 电子工程系,例：布尔函数 ，用Reed-Muller扩展式可表示为：,按式： 计算得：C0=1，C1=0，C2=1，C3=0，C4=1，C5=1，C6=1，C7=0,2. 逻辑函数改写成Reed-Muller扩展式 可依于以下步骤： (1)通过配项等方法把函数转换成SOP形式； (2)用“异或”操作代替SOP形式中的“和”操作； (3)如果各项中有补码出现的变量，如 ，则用公式 代替； (4)整理结果，即得式(5.1)所示的模式。,南京航空航天大学 信息科学与技术学院 电子工程系,3. Reed-Muller扩展式的硬件实现及特性 Reed-Muller扩展式硬件实现的典型结构如

39、图5.19(a)所示，电路的基本结构是双输入异或门的串联结构，函数原始变量根据式(5.1)中对应的非零系数Ci加入到异或门。 的硬件结构如图5.19(b)所示。,例5.8 把函数 表达成Reed-Muller形式。,南京航空航天大学 信息科学与技术学院 电子工程系,图5.19 硬件结构图与实现图,南京航空航天大学 信息科学与技术学院 电子工程系,用Reed-Muller扩展式设计的数字电路具有以下特性： (1)对于级联的异或门中存在的单故障，通用的测试图形完全能够检测，而与电路实现的功能无关； (2)如果输入节点无故障（输入总线上无故障，但是与门的输入输出有单固定型故障），至少需要(n+4)个

40、测试图形就能检测电路存在的所有单故障； (3)如果所有节点都有故障，那么测试图形长度为(n+4)+2ne，ne是在Reed-Muller扩展式中出现偶次的输入变量的个数。例如图5.19中，只有输入变量x1与x3出现偶次(2次)，因此ne=2。,对于特性(1)，可用5.4节中的C可测性进行证明（下图）。,仿照此例，对于Reed-Muller扩展式硬件实现的结构图，标识测试图形符号如图所示。,可以看出，级联的异或门单故障测试集为T1=R,S,R,T,T0110,南京航空航天大学 信息科学与技术学院 电子工程系,对一般：,即，S=x1=x2=xn=x1x2=x1x3=xn-1xn= x1x2xn 所

41、以有： S=x1=x2=xn=0101,南京航空航天大学 信息科学与技术学院 电子工程系,C0,x1 x2,x2,输入序列为： C0x1x2x3=0000,0111,1000,1111 结论： 输入序列的结构与输入变量个数n无关，而且只含4个测试。,对于5输入变量的函数，输入序列可能形式为C0x1x2x3x4x5= 000000,011111,100000,111111,南京航空航天大学 信息科学与技术学院 电子工程系,用Reed-Muller扩展式设计的数字电路具有以下特性： (1)对于级联的异或门中存在的单故障，通用的测试图形完全能够检测，而与电路实现的功能无关； (2)如果输入节点无故障

42、（输入总线上无故障，但是与门的输入输出有单固定型故障），至少需要(n+4)个测试图形就能检测电路存在的所有单故障； (3)如果所有节点都有故障，那么测试图形长度为(n+4)+2ne，ne是在Reed-Muller扩展式中出现偶次的输入变量的个数。例如图5.19中，只有输入变量x1与x3出现偶次(2次)，因此ne=2。,检测异或门故障的测试图形是4个。 对N输入与门的s-a-0 输入故障（N个），以及输出端的s-a-0故障（1个），可以用以上的(C0x1x2x3) 0111, 1111进行测试； 对N输入与门的s-a-1输出端故障（1个），可以用以上的 (C0x1x2x3)0000, 1000

43、进行测试； 与门输入端还有N个s-a-1故障用以下T2测试，形式为： 完全的测试集应包括了T1和T2两项（n+4），均是(n+1)维图形。,是x1/1的测试图形,是x2/1的测试图形,是xn/1的测试图形,也可以这样推导N输入与门有N+1个特征故障：y/0(x1/0、x2/0、xn/0、y/0等效为1个)， x1/1、 x2/1、 xn/1。其中y/0的测试图形是111，余测试图形是T2 。 任何1个输入端xi/1的测试图形均可测试y/1故障。,南京航空航天大学 信息科学与技术学院 电子工程系,用Reed-Muller扩展式设计的数字电路具有以下特性： (1)对于级联的异或门中存在的单故障，通

44、用的测试图形完全能够检测，而与电路实现的功能无关； (2)如果输入节点无故障（输入总线上无故障，但是与门的输入输出有单固定型故障），至少需要(n+4)个测试图形就能检测电路存在的所有单故障； (3)如果所有节点都有故障，那么测试图形长度为(n+4)+2ne，ne是在Reed-Muller扩展式中出现偶次的输入变量的个数。例如图5.19中，只有输入变量x1与x3出现偶次(2次)，因此ne=2。（可查论文证明）,用Reed-Muller扩展式实现的组合电路，测试图形长度为(n+4+2ne)，这些测试图形可以通过观察直接写出，不需专门的测试生成算法。,南京航空航天大学 信息科学与技术学院 电子工程系

45、,1. 实现方法 可以证明，加入额外的逻辑，一个数字电路可以修改得只用5个测试图形就能完全测试。 异或门插入的设计方法就具有这种特性，设计步骤如下： (1)用两输入与非门及反相器来实现给定的布尔函数； (2)把所有反相器用两输入异或门代替（1 X=X，0X=X），异或门多余的输入作为控制端引出； (3)给两输入与非门的另一个输入端加入两输入异或门，加入的异或门的第二个输入作为控制端引出。,5.5.2 异或门插入法,南京航空航天大学 信息科学与技术学院 电子工程系,图5.24 函数 的实现,1,1,例5.9 布尔函数,图5.25所示电路产生的测试图形: （1）对两个两输入异或门进行穷举测试（非括

46、号中所示），在输出端P1、P2分别得到输出序列（非括号中所示） ； （2）这两个输出序列再作为两输入与非门的穷举测试图形； （3）观察与非门的输出序列，其中0出现次数少于2，因此不能对后续的两输入电路进行穷举测试，需再加一个测试图形(括号中所示)，则穷举测试整个电路至少需要5个测试图形，如表5.12所示。,图5.25 构成两输入异或门和与非门的模型,2. 测试图形,表5.12 图5.25电路的测试图形及响应,1,南京航空航天大学 信息科学与技术学院 电子工程系,更一般的分析说明，对于异或门插入法修改后的组合电路，在原始输入和与非门的输入施加一类确定的测试图形可对电路完全测试，这类测试图形属于集

47、合P=(P0,P1,P2,P9) ,称为P域，其中： P0=00111 P1=01011 P2=01110 P3=01110 P4=10011 P5=10101 P6=10110 P7=11001 P8=11010 P9=11100 P域中的运算规则如下： (1)若Pi=(a1,a2,a3,a4,a5),aj(0,1),j=1,2,3,4,5 则 (2)若Pi=(a1,a2,a3,a4,a5), Pj=(b1,b2, b3,b4,b5), at,bt(0,1),t=1,2,3,4,5 则Pi+Pj=(a1+b1,a2+b2,a3+b3,a4+b4,a5+b5) PiPj=(a1b1,a2b2,

48、a3b3,a4b4,a5b5) (3)若Pi P,Pj P,且 ,则称Pi和Pj是相容对。,南京航空航天大学 信息科学与技术学院 电子工程系,相容对序列有以下重要性质： 若Pi和Pj是相容对，则Pi和Pj对应位中包含了所有可能的4种组合； 若Pi和Pj是相容对，且 ，则Si和Pj对应位中包含了所有可能的4中组合； 若Pi P,Pj P，则必然存在一个Pk P，使得(Pk,Pj)和(Pk,Pi)均是相容对。 根据上述P域运算规则，对图5.25标识测试图形符号如图5.26所示。根据测试图形的符号标识和P域运算规则可以确定测试图形。,图5.26 异或门插入法基本模块的测试图形的符号标识,5.5.3 组合电路的其他可测性设计方法 任意一个n输入的门可用(n+1)个测试图形完全测试。 对于任意一个n输入的、完全用与门构成的组合电路，就可能用(n+1)个测试图形完全测试该组合，这样的结论对由其他类型两输入门构成的电路同样成立。 例：一个三输入的或门可用两输入的“