第8章 随机测试和伪随机测试.ppt

1、第8章 随机测试和伪随机测试,本章主要内容 随机测试 伪随机序列 LFSR的数学基础 基本的伪随机测试序列生成电路 其它类型伪随机序列的生成方法 低功耗测试序列,南京航空航天大学 信息科学与技术学院 电子工程系,南京航空航天大学 信息科学与技术学院 电子工程系,定义 穷举测试 施加所有可能的2n 向量到具有n个输入的电路。 伪穷举测试将电路划分为较小的电路, 重迭模块和完全测 试每个模块： 验证测试 硬件分块 敏化路径分块 伪随机测试向量生成器产生所有可能测试向量的子集： 生成规则的测试向量可重复性； 具有随机方法的所有描述的特性； 不需要覆盖所有2n 输入组合, 确定性ATPG测试序列长度穷

2、举测试； 高的故障覆盖率需要长的序列。 不可化简的多项式不能分解的布尔多项式。 伪随机测试在内建自测试中用的特别广泛,LFSR 线性反馈移位寄存器, 生成伪随机测试向量序列的硬件,8.1 随机测试,8.1.1 随机测试的概念,随机测试的主要特征： 把位独立的随机序列（测试序列x1,x2,xn中各变量相互独立）加到被测电路的输入上。 假定被测电路的原始输入个数为n，随机测试是把变 量xi (xi属于0，1，i=1，2，n)施加到被测电路的第i个输入。,典型随机测试系统包括： 随机位序列产生电路 被测电路 参考电路 输出响应比较器,南京航空航天大学 信息科学与技术学院 电子工程系,典型随机测试系统

3、： 随机位序列产生电路 根据给定的概率分布P (xi=1)产生独 立的随机量，生成的测试图形同时加到被测电路与参考电路的输入上。 输出响应比较器 对被测电路与参考电路的输出响应进行 比较，若二者一致，则称被测电路无故障，否则称被测电路有故障，必要时进行相应的故障诊断。,简单逻辑电路 输出概率P (y=f(x1,x2,xn)与输入概率P(xi=1)(i=1,2,n， )的关系如：,单输入x1的非门：,门电路输出概率与输入概率的关系：,南京航空航天大学 信息科学与技术学院 电子工程系,南京航空航天大学 信息科学与技术学院 电子工程系,如，对于两输入与门：P (y=1)=P(x1=1)P(x2=1)

4、,多输入与门，输出y只有当所有输入为1时才为1，因此： 或写为： 因为 y=x1x2xn， 而x1=1,x2=1,xn=1独立。,对于两输入或门：,南京航空航天大学 信息科学与技术学院 电子工程系,则有：,例8.1 如图所示电路，当施加位独立的随机序列时，假定概率 P(x1=1)=P(x2=1)=P(x3=1)=P(x4=1)=P(x5=1)=p,当p=1/2时， p(f1=1)=0.125，p(f2=1)=0.75，p(f3=1)=0.08375。,当把随机测试序列加到被测电路时，通过比较电路节点实际的概率值p*(f1=1)、p*(f2=1)和p*(f3=1)，可进一步判断是否有故障。,例如

5、，对于故障f11，可得p*(f1=1)=1，p*(f2=1)=0.75， p*(f3=1)= p*(f1=1) p*(f2=1)= 0.75，表明电路有故障。,南京航空航天大学 信息科学与技术学院 电子工程系,定义：对于一固定型故障fk(k 0，1)，随机测试图形可检测到的概率为故障检测率，记为 pdfk。 pd是随机测试效率的度量（表征对特定故障检测的复杂程度）,8.1.2 故障检测率pd的估算,随机测试的关键问题：为得到满足要求的故障覆盖率，测 试图形的长度应该取多长。 测试图形的长度取多长与故障检测率有关。,检测故障fk 应由两个并发事件的概率确定： 故障在其源处的再现及故障传播到电路的

6、一个输出端,分别对应由故障fk在特定节点的再现概率 pe (fk )及故障在任一输出可观的概率pt=fk 来估值： Pd=Pe . Pt,例: n输入与门的故障检测率pd,对于原始输入的任一故障，对其传播的条件是从该输入到原始输出的路径敏化，它由事件x2=1，x3=1，xn=1确定，相应的概率为p(x2=1，x3=1，xn=1)。,设对与门进行随机测试时施加的位输入测试序列为：x1x2xn 并假定各个位的概率： P(x1=1)= P(x2=1)= =P (xn=1)=p P (xi=0)=1-p 则故障s-a-0出现在原始输入的概率与“1”出现在该输入的概率是相同的，即 Pe(x10)=P(x

7、1=1)=p 故障s-a-1出现在原始输入的概率与“0”出现在该输入的概率是相同的，即 Pe(x11)=P(x1=0)=1- P(x1=1)=1-p,由于对输入所施加的随机序列相互独立，最后得到： Pt(x1k)=p(x2=1) p(x3=1) p (xn=1)=pn-1,因此，简单门的故障检测率Pd (fk)： Pd(fk)=Pe(fk) . Pt(fk),对或门有：Pe(x10)=P(x1=1)=p 同样， Pe(x11)=P(x1=0)=1- P(x1=1)=1-p,对于原始输入的任一故障，对其传播的条件是从该输入到原始输出的路径敏化，它由事件x2=0，x3=0，xn=0确定，相应的概率

8、为p(x2=0，x3=0，xn=0)。,由于对输入所施加的随机序列相互独立，最后得到： Pt(x1k)=p(x2=0) p(x3=0)p (xn=0)=(1-p)n-1,前已述及，门电路输出概率与输入概率的关系：,表8.1 与门和或门节点故障的故障检测率Pd (Pd=Pe . Pt),Pe(x10)=P(x1=1)=p Pe(x11)=P(x1=0)=1- P(x1=1)=1-p Pt(x1k)=p(x2=1)p (xn=1)=pn-1（与门） Pt(x1k)=p(x2=0)p (xn=0)=(1-p)n-1 （或门）,Pe(yk)= k=1 Pe(y=1)=p(y=0)=1-p(y=1) k

9、=0 Pe(y=0)=p(y=1) Pt ( y k)=1,南京航空航天大学 信息科学与技术学院 电子工程系,例如：对于4输入与门，p=1/2，由前述表8.1可得： Pd(xi0)=2-4； 对于4输入或门， Pd(xi0)=1-2-4。,由于故障再现的相关性以及多故障效应传播到电路的一个输出，用分析方法估算故障检测率尤为复杂。 因此，大多数情况下，只估算单故障的概率。,8.1.3 测试图形长度的计算,数字电路测试中一个非常重要的参数是测试施加时间。 测试施加时间与测试图形长度成正比 对于确定性测试方法，测试图形长度可由测试所有可能存在的故障所需的故障覆盖率来确定，满足覆盖率的测试长度一般不会

10、超过2000。 测试图形越长，故障覆盖率越高。,南京航空航天大学 信息科学与技术学院 电子工程系,对随机测试，故障覆盖率与随机测试图形长度间的曲线如下， 表明：故障覆盖率T与随机测试图形长度N可按下式近似表达。,定理8.1 （测试图形长度估算） 假定一电路存在k个故障，每个故障的测试图形互不相交，且故障检测率平均值为pd。为使测试时未被检测的概率小于或等于Pn(N)，则所施加的随机测试图形长度N应满足以下不等式：,南京航空航天大学 信息科学与技术学院 电子工程系,8.1.4 输入变量的优化,为了取得最小长度的测试图形，应对输入变量根据其概率进行优化选择。 选择输入变量概率的优化值有多种，先研究

11、满足检测难测故障的最大测试图形长度的输入变量概率的优化问题。,当Pd=0.05时，N=160。 表明：随机测试图形的长度取决于故障检测概率。,例8.2 一组合电路中，2个故障的检测率pd均为0.001，为保证对 这两个故障随机检测时未被检测的概率小于0.001，则所需测试图形长度为：,假定难测故障的检测率为Pd，解决难测故障问题的方法就是寻找概率优化的输入变量，以保证检测到最难检测故障。即， 故障检测概率最小的难测故障的检测率取得尽可能大的值。,pd(y 1)=1-Pn,Pd(y0)=Pn,Pd(xi 1)=pn-1-pn,P,Pd,分析Pd和p之间的关系，可以得到： 当n=2、p=0.5 以

12、及 n=3、p=2/3=0.6666 时， maxpmin(pn-1-pn，1-pn，pn)成立。,例如：对n输入与门的故障检测率pd分别绘制曲线： 取n=2 pd(y 1)=1-Pn（曲线1） Pd(y0)=Pn（曲线2） Pd(xi 1)=pn-1-pn（曲线3）,南京航空航天大学 信息科学与技术学院 电子工程系,表示(pn-1-pn，1-pn，pn)中的最小值pn-1-pn 取得最大。即， 与pd(y 1) )=1-Pn 以及 Pd(y0)=Pn 相比， Pd(xi 1)=pn-1-pn是难检故障，概率值小，但它有个最大值。,南京航空航天大学 信息科学与技术学院 电子工程系,进一步分析表

13、明：对于随机数n，1出现在n输入与门的输入端的优化概率P0可由以下定理给出。,定理8.2 1出现在n输入与门的输入端的优化概率为P0= (n-1)/n。,证明：优化概率P0应保证对最难检测的故障（即，故障检测概率最小的难测故障）的检测率取得尽可能大的值。 对于n输入与门，有3个故障检测概率pn-1-pn，1-pn和pn，因此当P=P0时，maxpmin(pn-1-pn，1-pn，pn)成立。 显然，maxpmin(pn-1-pn，1-pn，pn) maxp(pn-1-pn) 根据p所得的maxp(pn-1-pn)满足等式, (n-1)P(n-2)-nPn-1=0 p=(n-1)/n,对于n输入

14、的或门，可以用类似的方法得到优化概率P0=1/n。,南京航空航天大学 信息科学与技术学院 电子工程系,与门和或门的优化概率P0可以用在确定任意的随机电路的优化概率算法中。,优化概率算法的思想是确定输入的概率 此概率的选择应保证电路中每一个单元的输入取得优化的概率值。,优化方法是计算电路中每一个单元的输入的优化概率值，以它们的平均值作为优化的概率值。,算法步骤： (1)对电路的每一个单元的输入，按照最小的测试图形长度确定优化概率； (2)按照向后跟踪的方法，推算出电路原始输入的概率； (3)把电路中的每一个单元的输入概率值，置入特殊的表； (4)对于电路中的每一个原始输入，推算节点概率的平均值。

15、,4,南京航空航天大学 信息科学与技术学院 电子工程系,例8.3 对于图8.4所示的电路，计算节点的概率值。,解：此电路包含4个元件，（1）首先对第4个元件(与门)选择优化的输入概率值，按照定理8.2得：,p(f2=1)=p(f3=1)=0.5,（2）对于元件2和元件3(或门)：,为了从f2和f3推算门2和门3输入的概率值，必须采用电路元件中输入变量的概率值和输出变量的概率值之间的关系: ,（3）对于元件1： p(x2=1)=p(x3=1)=p(x4=1)=p1/n =0.63（n=3）,p(x1=1)= 1-(1-p)1/n =0.293 p(x5=1)=p(x6=1)= 1-(1-p)1/

16、n =0.206 ( n=2，n=3) f1是扇出节点 p(f1=1)=(0.293+0.206)/2=0.25,南京航空航天大学 信息科学与技术学院 电子工程系,对于非重聚的扇出电路，假定共有k个扇出信号，每个扇出信号的概率分别为pi(i=1，k)，则公共节点的概率p为:,反相器， 1出现在输入端的概率 pi=1-p ;,4,南京航空航天大学 信息科学与技术学院 电子工程系,同理，可以计算出电路中元件的其他信号的概率值，所有结果列于表8.2。,表8.2 图8.4各个节点的概率值,前面已求出,p(x1=1)=0.5,不考虑f1的扇出, Pi=(0.5)1/3=0.794,p(x5=1)=0.3

17、33,不考虑f1的扇出, Pi=(0.333)1/3=0.693,1出现在n输入与门输入端的优化概率为(n-1)/n=2/3.,1出现在n输入或门输入端的优化概率为1/n。,p(f2=1)=p(f3=1)=0.5,南京航空航天大学 信息科学与技术学院 电子工程系,对于电路的每一个原始输入，表8.2所列的概率的平均值就是其优化值，因此： p(x1=1)=(0.293+0.5)/2=0.397 p(x2=1)=p(x3=1)=p(x4=1)=0.696 p(x5=1)=p(x6=1)=0.27,表8.2 图8.4各个节点的概率值,结论：对于图8.4所示电路的故障x20，按照等概率的随机测试，其故障

18、检测率为Pd=0.078。运用式(8.9)计算出的测试图形长度N=85(Pn(N)=0.001)。在同样的条件下，按照优化的概率分布，测试图形长度N=22。,南京航空航天大学 信息科学与技术学院 电子工程系,8.2 伪随机序列,生成伪随机序列通常用两种方法： （1）同余法； （2）用无输入的线性反馈移位寄存器构成伪随机序列生成电路.,伪随机测试向量生成器产生所有可能测试向量的子集： 生成规则的测试向量可重复性； 具有随机方法的所有描述的特性； 不需要覆盖所有2n 输入组合, 确定性ATPG测试序列长度穷举测试； 高的故障覆盖率需要长的序列。 伪随机测试在内建自测试中用的特别广泛,8.2.1 同

19、余伪随机序列（自看！）,南京航空航天大学 信息科学与技术学院 电子工程系,8.2.2 反馈移位寄存器和异或门构成的伪随机序列生成电路,同余法生成的伪随机序列的最大问题是周期性问题。,结论：m位的LFSR ，最多可产生(2m-1)个不同的状态。,用无输入的线性反馈移位寄存器LFSR构成伪随机序列生成电路，所生成的序列只与寄存器的初始状态和反馈方式有关。,这种数字序列是伪随机的：每一个向量生成的概率是相等的，同样的序列还重复。,如果一个序列发生器正好产生这(2m-1)个不同的状态后才重复产生此序列，则此序列发生器称为最大长度序列发生器。包含且只包含这(2m-1)个不同状态的序列称为最大长度序列。,

20、南京航空航天大学 信息科学与技术学院 电子工程系,LFSR的有两种连接方式：异或门内接的LFSR，简称IE型LFSR； 异或门外接的LFSR ，简称EE型LFSR。,如何使得序列发生器生成最大长度的序列?,ai(i=1,2,m)： 寄存器(D触发器) ci (i=1,2,n)： 有无异或门反馈连接， ci=1反馈接入， ci=0不存在反馈.,Q1,Q3,Q2,Qm,a0,设ai为当前状态，则有： c0a0=c1a1c2a2c3a3cm-1am-1cmam 设 xi 表示i个时钟的延时，则有：a1=xa0 a2=x2a 0 ak=xka0 am=xma0 c0x0a0=c1xa0c2x2a0cm

21、-1xm-1a0cmxma0,图8.5和图8.6所产生的函数表达： c0x0+c1x1+c2x2+cmxm （特征多项式）,Q1,Q3,Q2,Qm,a0,设k为当前状态，则有： a1(k)=c1a1(k-1)c2a2 (k-1) cmam (k-1) a2 (k) =a 1 (k-1) am (k) =am-1 (k-1),例8.5 对于图8.7(a)和图8.7(b)所示的EE型LFSR，写出对应的多项式，并求出寄存器初始状态为1111的伪随机序列。,1+c1x1+c2x2+cmxm,x1 x2 x3 x4,a0 a1 a2 a3,x1先变化(x2x4)再移入，其余只移位,LFSR状态变化特点

22、：CLK到来时，移入的状态是经异或运算并在前次CLK移入的结果。,x1 x2 x3 x4,a0 a1 a2 a3,图8.7所示电路产生的伪随机序列不是最大长度，用它们测试故障时会大大降低故障覆盖率。,特征多项式可以再分解： 1+x2+x4=( 1+x+x2)(1-x+x2) 1+x+x2+x3+x4=？,例8.6 对于4位寄存器，对应的不可分解的多项式为： x4+x+1 或 x4+x3+1 试根据这样多项式连接伪随机电路，写出前17个序列，并进行分析。,南京航空航天大学 信息科学与技术学院 电子工程系,用线性反馈移位寄存器LFSR如何才能生成最大长度的序列呢？,可以证明：基于非本原多项式的系数

23、连接而成的伪随机电路，所生成的伪随机序列不是最大长度的。,本原多项式：可以分解的多项式不是本原多项式,基于本原多项式的系数连接而成的伪随机电路，能生成最大长度的伪随机序列。,x4+x3+1,对于4位线性反馈移位寄存器，根据本原多项式x4+x3+1的系数连接反馈所形成的电路： （1）可以生成最大长度的伪随机序列（24-1）=15； （2）序列的每一位不具有周期性。,x4+x3+1,x4+x+1,8.3 LFSR的数学基础,8.3.1 根据本原多项式优化伪随机序列发生电路,对于任意一个m位的线性反馈移位寄存器，根据本原多项式c0x0+c1x1+c2x2+cmxm的系数ci (i=0,1,2,m)，

24、连接异或门反馈所形成的伪随机序列发生电路，均可生成最大长度为(2m-1)的序列，称之为M序列。,南京航空航天大学 信息科学与技术学院 电子工程系,f(x)满足以下条件则为本原多项式： （1）f(x)是既约多项式（不能再分解因子）； （2）f(x)可以整除xm-1(m=2n-1); （3）f(x)除不尽xq -1，qm。,表8.3 多项式个数 与m的关系,对于不同的m值（线性反馈移位寄存器的位数），对应的本原多项式的个数，如表8.3所示。,随着m的增加而快速增加,对于每一个m，总会存在项数最少而且每项系数为1的本原多项式，列表如下：,即，本原多项式的反也是本原多项式。,南京航空航天大学 信息科学

25、与技术学院 电子工程系,本原多项式具有这样的特征：,根据本原多项式的反的系数连接而成的伪随机列生成电路，也能够生成最大长度的序列。,例：多项式x4+x3+1的反是： x4(x-4+x-3+1) = 1+x+x4 两者都是本原多项式，由它们的系数连接而成的为随机序列生成电路，都可以产生最大长度序列。,根据本原多项式的系数连接异或门反馈而成的伪机序列生成电路，硬件实现简单。,电路中只包含m位移位寄存器和反馈回路中一系列异或门。 通常，移位寄存器存储m位编码，一次CLK只移一位，反馈回路中的异或门计算所连接的寄存器的时序值，并送给相应的寄存器。 移位寄存器的状态可用m维的向量表示： A(k)=a1(

26、k)a2(k)a3(k)am(k) ， k=0,1,2，ai(k)0,1,对于EE型LFSR，移位寄存器的状态关系表达如下,设k为当前状态，则有： a1(k)=c1a1(k-1)c2a2 (k-1) cmam (k-1) a2 (k) =a 1 (k-1) am (k) =am-1 (k-1),第一个是反馈异或，其余是前一级的移位.,简化可写成：A(k)=VA(k-1),a1(k)=c1a1(k-1)c2a2 (k-1) cmam (k-1) a2 (k) =a 1 (k-1) am (k) =am-1 (k-1),对应的矩阵V为：,由移位寄存器状态的矩阵表达式，可以推出关系式：,或者,例如，

27、对于多项式,南京航空航天大学 信息科学与技术学院 电子工程系,c1=c2=0，c3=c4=1,（K+S）时刻的状态是K时刻状态移位S次。,8.3.2 LFSR的运算,1. 异或运算 异或运算的真值表如表所示。,南京航空航天大学 信息科学与技术学院 电子工程系,根据本原多项式的系数连接异或门反馈形成的M序列生成电路，以及LFSR的状态可用矩阵运算来表达，这些为数学分析LFSR电路提供了基础。 本节讨论LFSR的运算，进而推导出一些特性。,在LFSR的运算中，只包含模为2的运算，结果中不会有进位和借位部分，因此可以用“+”表示异或运算、加法运算和减法运算。,表8.5 模为2的运算,模为2的运算具有

28、这样的特性：xi+xi=0 或 xi-xi=0,多项式 P(x)=1+c1x1+c2x2+cNxN 的反定义为：,即，将P(x)的每一个系数ci用cN-i代替即得到P(x)的反。,南京航空航天大学 信息科学与技术学院 电子工程系,2. 多项式的反,前已述及：,例如，多项式P3(x)=x3+x+1的反就是P3R(x)=1+x2+x3 c1=1，c2=0，c3=1 c1=c2=0，c2=c1=1，c3=1,LFSR所基于的多项式运算均是模为2的运算，模为2的运算具有这样的特性： xi+xi=0 或 xi-xi=0 例：多项式（x4+x2+x1+1）*（x3+x2+1）,3. 多项式的运算,南京航空

29、航天大学 信息科学与技术学院 电子工程系,乘积的多项式表达式就是x7+x6+x5+x4+x1+1,所有项求和，并结合模2运算特性（指数相加）。,南京航空航天大学 信息科学与技术学院 电子工程系,x7x6 x5 x4 x2 1 x4 x7x6 x4 x5 x2 1 x2 x5 x4 x2 x4 1 x x4 x3 x x3 x 1 1 x3 x21 x2x,多项式的除法与多项式的乘法过程相似。 例如，多项式x7x6 x5 x4 x2 1 被多项式 p(x)=x3 x2 1相除，求商数多项式q(x)及余数r(x) 。,商数多项式为q(x)= x4 x2 x 1 ，余项多项式为r(x)= x2 x。

30、,南京航空航天大学 信息科学与技术学院 电子工程系,基于本原多项式的系数连接异或门反馈的m位LFSR电路，可生成M序列，具有如下特性： (1)M序列的周期是L=2m-1 (2)对于给定的本原多项式 ，可能生成L个不同的M序列（不同的初态），它们的相移不同。 (3)一个M序列ak中，k=0,1,2,L-1，可能出现多个“1”和多个“0”，“0”和“1”出现的概率分别为：,m增加时，上述概率均趋于1/2。,8.3.3 M序列的特性,当m=4时， ak的15个状态中，有8(23)个1，7(23-1)个0.,(5)对于任意s(1sL)，存在一个rs(1 rL)，使得 ak ak-s=ak-r， 这个特

31、性为“移位加”特性（加法的封闭性）。,(7)一个本原多项式 所对应的L个非零的M序列中，存在一个序列具有这样的特性ak=a2k(k=0,1,2,)，这样的序列称为特征化序列。,(4)一个M序列中，“0”与“1”出现的概率接近于随机序列中的概率。,(6)M序列的自相关函数定义为:,南京航空航天大学 信息科学与技术学院 电子工程系,(8)对应于m4的多项式，原多项式的反所对应的伪随机序列的顺序与原多项式对应的伪随机序列的顺序相反。,南京航空航天大学 信息科学与技术学院 电子工程系,(9)任何一个长度为(2m-1)的M序列中，都会有一组长度为m 的“1”和一组长度为(m-1)的“0”。 (10)任何

32、一个长度为(2m-1)的M序列中，可把相同的向量划分为一组，这样就可把序列分为多组向量，其中(2m-1)/2组向量的长度为1， (2m-1)/4组向量的长度为2。,例子表明，伪随机序列中的每一位具有一定的“成组”分布特性。此外，伪随机序列中不同的位具有自相关特性。因此，伪随机序列并不能够检测抗随机图形故障。,例如，对应于本原多项式为1+x2+x5、初始状态为00001的伪随机序列生成电路，最后一个寄存器的输出序列为： S(t)=(10000 10010 11001 11110 00110 11101 0)10000 1 而对于多项式1+x3+x5（1+x2+x5的反）、初始状态为10000的伪

33、随机序列生成电路，最后一个寄存器的输出序列为： SR(t)=10000 1(01011 10110 00111 11001 10100 10000 1) SR(t)是S(t)的反(8)； SR(t)的长度为25-1=31，共包含16个“1”和15个“0”，有一组长度为5的“1”(9)、一组长度分别为2和3的“1”和5组长度为1的“1”。,南京航空航天大学 信息科学与技术学院 电子工程系,采用D触发器和异或门构成外接型PRSG的电路如图8.9(a)所 示。外接型PRSG的功能关系式：,8.4 基本的伪随机测试序列生成电路,伪随机测试序列生成电路(PRSG)，最常用的结构是线性反馈移位寄存器(LF

34、SR)。 一个m级的LFSR根据本原多项式的系数连接异或门反馈，产生m位数字的周期性伪随机序列。 根据异或门的连接方式，PRSG可分为外接型、内接型和混合连接型等几种基本形式。,8.4.1 外接型PRSG,南京航空航天大学 信息科学与技术学院 电子工程系,(8.20),南京航空航天大学 信息科学与技术学院 电子工程系,在按本原多项式系数连接的情况下，一般cm=c0=1，异或门的个数不超过3个(P191)，硬件简单。,对于k个反馈线，就会有k-1个门延迟。,南京航空航天大学 信息科学与技术学院 电子工程系,(b)本原多项式p(x)=x4+x3+1、初始化向量为1000的PRSG及其时序图,采用D

35、触发器的外接型PRSG,(8.23),式中，k=1,2,ci0,1，是本原多项式的系数。,同外接型PRSG相比，内接型PRSG的速度高，但实现起来较为复杂。构成内接型PRSG的电路如图8.10所示，对应的关键表达式为：,南京航空航天大学 信息科学与技术学院 电子工程系,8.4.2 内接型PRSG,南京航空航天大学 信息科学与技术学院 电子工程系,(8.23),异或门加到具有反馈环节的输入上，结果最多只会有一个异或门的延迟。,(b)本原多项式p(x)=x4+x+1、初始化向量为1000的PRSG及其时序图,采用D触发器的内接型PRSG,南京航空航天大学 信息科学与技术学院 电子工程系,(8.24

36、),8.4.3 混合连接型PRSG,混合连接型PRSG，是既采用异或门内接又采用异或门外接的PRSG，当前状态和先前状态的关系如下：,南京航空航天大学 信息科学与技术学院 电子工程系,构造PRSG比较好的方法是采用混合连接型PRSG。,1 2 j-1 j j+1 m-1,(8.25),分析上式，得到：,前(j-1)位和外接异或门的连接关系根据系数 确定,最后一位和内接异或门的连接关系由 和 决定,可以变换为：,定理8.3 假如原始生成多项式,系数 和 通过一个外接异或门与第r个自动机位相连接，如图8.11所示，这样就会产生一个最大长度序列。反之亦成立。,南京航空航天大学 信息科学与技术学院 电

37、子工程系,混合连接型PRSG的特征多项式为：,此类PRSG按以下定理生成最大长度的序列(M序列) 。,系数 、 和 取值0或1 ( ， )，则下面的生成多项式可以建立同步自动机（自动生成M序列）：,例8.8 根据本原多项式,可以看出，混合连接型PRSG所需异或门的数目比单纯采用内接型或外接型PRSG所需异或门的数目少，但混合连接型PRSG的速度比单纯采用内接型PRSG的速度慢，因为串接到外接异或门的信号会有延迟效应。,设计一个混合连接型PRSG。,M序列在科学和工程方面有广泛的应用。 还有其他多种序列，它们的特性类似于M序列，采用PRSG硬件和硬件实现都相当容易。,南京航空航天大学 信息科学与

38、技术学院 电子工程系,8.5.1 与M序列相关的序列的生成方法,（2） U1 在序列子集U0 中找出一类具有“成组”特性的序列子集U1。其“成组”特性为：对于周期为(2m-1)的二进制序列，存在2m-2-i组长度为i的“1”或“0”序列、1组长度为(m-1) 的“1”或“0”序列。,对周期为L=2m-1的二进制序列进行分类：,（1） U0 满足“1”和“0”等概率的子集，在其周期内包含(L+1)/2个“1”和(L-1)/2个“0”，该序列子集标记为U0,其周期为L.,（3）U2 包含长度为m，可能有(2m-1)个分割方法的所有序列的集合，这个子集不包括零序列(长度为m、全为“0”的序列)。,8

39、.5 其它类型伪随机序列的生成方法,比较M序列的特性与序列子集U0，U1，U2，U3和U4的特性可以看出：M序列只属于序列子集U2和U4的交集，此类交集标记为U5。,南京航空航天大学 信息科学与技术学院 电子工程系,（4）U3 在序列集合U0中还可以分割出这样一类序列子集U3，其特性序列值之间存在移位特性。,图8.13 序列子集之间的关系,（5）U4 序列子集U3中又包含序列子集U4，特性是在其周期内循环移位的序列之间不相关，即当移位值 时，自相关函数的值接近于0。,Ford序列可以通过对序列子集U2添加零序列得到，其周期为2m，特征是在一个周期内会出现长度为m的各种编码，而且一种编码只出现一

40、次。Ford序列在VLSI的离线测试中比较常用。,南京航空航天大学 信息科学与技术学院 电子工程系,一些序列不属于这些序列子集，但特性与这些序列子集的特性类似，这一序列称为与M序列相关的序列。,1. Ford序列,其中，最容易实现的就是Ford序列、De Bruijn序列和Gold序列等。,南京航空航天大学 信息科学与技术学院 电子工程系,通过对编码 xk=(b1,b2,b3,bm) 移位，形成长度为（m+1)的编码 xk=(b1,b2,b3,bm,1) ，可以构成m个长度为m的编码，选择其中值最大的编码 ，如果 则： ， 否则： 。 零序列 可以选择为Ford序列的起始编码,m=4时，For

41、d序列生成举例见下页。,南京航空航天大学 信息科学与技术学院 电子工程系,(8.27),其中： ， (i=2m)是对应于生成De Bruijn序列的多项式 的系数； 是De Bruijn序列的一个单元，在第(k+1)个时钟操作中按生成电路的第一个存储单元处理。,2. De Bruijn序列,De Bruijn序列是对M序列插入零图形所形成的序列，零图形是通过对(00001)译码得到的，由于包含(m-1)个“0”的图形在一个周期只出现一次，因此可以用(m-1)输入的或非门来实现(00001)译码成零图形这种组合逻辑。,基于译码器的De Bruijn序列分析表达式为：,例，选择多项式对应De Br

42、uijn序列的生成电路。 按照式(8.27)所生成的序列的逻辑关系式为： a1(k+1)=a2(k)a5(k)a1(k)+a2(k)+a3(k)+a4(k) (8.28) a2(k+1)=a1(k) a3(k+1)=a2(k) a4(k+1)=a3(k) a5(k+1)=a4(k),南京航空航天大学 信息科学与技术学院 电子工程系,设计的De Bruijn序列生成电路如图8.14。 该电路能够生成完全测试集。,当a1a2a3a4a5=00001时： a0=a2a5或非门输出 =0 11=0 所以，在下一个CLK有： a1a2a3a4a5=00000 再下一个CLK有： a1a2a3a4a5=1

43、0000 该电路能够生成完全测试集,8.5.2 加权伪随机序列,8.5.3 细胞自动机,南京航空航天大学 信息科学与技术学院 电子工程系,8.6 低功耗测试序列,（1）随机测试图形大量的、不断变化的位码，会使测试功耗大大增加。,（2）伪随机测试中常用的是固定型故障模型，此模型难以描述CMOS深亚微米技术中的缺陷。有效的方法是设计一种“全能”的测试生成电路，可同时生成检测固定型故障以及CMOS其他类型故障的测试图形。,新的BIST技术的核心电路就是输入单个位变化的伪随机测试生成电路(RSIC)。,8.6.1 RSIC序列生成原理,RSIC序列生成电路的典型结构如图所示。,南京航空航天大学 信息科

44、学与技术学院 电子工程系,传统的结构化的伪随机生成方法存在诸多问题需要解决。,南京航空航天大学 信息科学与技术学院 电子工程系,例，对于一个8位代码转换电路，植入种子向量00000000，实现的转换关系是按M序列的每一向量对应的十进制值选中某位，然后对该位求反，得到的RSIC序列如表8.8所列。,（1）在任意时刻t，m位伪随机序列生成电路生成向量A(t)=a1(t)am(t)； （2）将此向量输入到预先植入种子向量的代码转换电路中，代码转换电路根据向量A(t)的值以一定的关系每次只选中一位，使得该位值发生变化，得到向量V(t)=V1(t)VN(t)； （3）将V(t)加到被测电路CUT上。,南

45、京航空航天大学 信息科学与技术学院 电子工程系,表8.8 按照图8.15 产生的一个RSIC序列,该RSIC序列每次只变化一位，因而测试功耗小。 但RSIC序列的生成与种子向量、电路实现的转换关系紧密相关。,假定时刻t，伪随机生成电路产生的向量A(t)=a1(t)am(t)，对应的十进制值为k，代码转换电路将实现这种转换，并只映射到代码转换电路输出的第k位，然后对该位求反，产生RSIC向量V(t)=V1(t)VN(t)，上述关系用逻辑关系可表示为：,8.6.2 RSIC序列的数学表达,南京航空航天大学 信息科学与技术学院 电子工程系,一般，假定m位伪随机序列生成电路生成的并非M序列，而是周期为

46、N的任意形式的随机序列，显然有： A(1+N)=A(1),(8.30),南京航空航天大学 信息科学与技术学院 电子工程系,南京航空航天大学 信息科学与技术学院 电子工程系,对于给定的RSIC生成电路，其特征序列C和特征矩阵是固定的，它们反映出电路的固有特性； 但生成的RSIC序列的形式则随种子向量变化，对于一个N位的RSIC生成电路，种子向量共有2N种植入方法，相应的就有2N种RSIC序列。,因此有：,可以简写为：,(8.33),对应一种RSIC序列,南京航空航天大学 信息科学与技术学院 电子工程系,8.6.3 RSIC序列的特性,(1)RSIC序列必须满足以下条件： 周期为N的伪随机序列必须

47、满足关系式N=2m(即,包括零序列); 在V(t)和A(t)之间的代码转换必须是一对一转换； 序列SV(1)V(2)V(i)V(L)的周期不小于测试图形长度L; 伪随机序列位数m、周期N与RSIC序列的周期L，必须遵循2N=L，2(2m-1) L，那么由适当结构所产生的随机单输入变化序列的周期应该为2(2m-1) ，因此伪随机序列位数m应该满足下面的关系式： 2(L/2+1) 2(L/2) (8.34),(2)对于给定的N位RSIC序列电路，生成的RSIC序列的每一个向量都从以下的集合中取值： V=V0,V1,Vj,V2N-1 (8.35) j是向量(x1,x2,xn)对应的十进制值，显然上述集合与N输入的穷举测试集完全相同。,南京航空航天大学 信息科学与技术学院 电子工程系,(3)随机电路产生的序列长度N，则每一个RSIC序列的最大长度为2N。 这个特性说明，要用RSIC序列生成足够长