引言

电路的日益复杂和集成度的不断提高，测试已成为集成电路设计中费用最高、难度最大的一个环节。本文主要讨论了测试中伪随机测试矢量的生成，并提出了改进其周期的办法，从而能大大提高故障的覆盖率。最后通过硬件描述语言Verilog 在QuartusⅡ软件下进行仿真，验证了其正确性。

伪随机测试矢量生产

生产伪随机测试序列通常有两种方法，第一种方法采用同余法，第二种方法采用线性反馈移位寄存器。

同余伪随机序列

同余伪随机序列采用的关系：

X_{k}=AX_{k}+B(MODE) (k=1,2,3…) (1)

这里X_{0}>0,A>0,B≥0,M>X_{0},M>A,M>B。

当B＝0时，此方法又称为倍增同余（multiplicative congruential）；当B≠0时，称为混合同余（mixed congruential）。

如果选择合适值使得M=r^{m}，这里r是表示m位伪随机数X_{k}的基（basis），则式(1)可写为：

X_{k}=AX_{k-1}+B(MODr^{m}) (k=1,2,3…) (2)

更深入的研究表明，当B=0时，根据X_{0}，A，B，r及m的值及关系式（1），在所产生的伪随机数字序列{X_{k}}中，第 位数字的周期L_{k}， ∈{1，2，3，…，m}为：

maxL_{ }=r^{ -1}(r-1) (3)

当B≠0时，第 数字的周期L_{ }， ∈{1，2，3，…，m}为：

maxL_{ }=r^{2 -1}(r-1) (4)

根据式（3）和式（4）可以看出，伪随机序列的位都具有周期性，而且不可消除，影响伪随机数字序列的质量，这样的序列用于数字电路测试时，周期性大大降低了测试的覆盖率，因此涉及的倍增方法的实现与修改是相当复杂的。

线性反馈移位寄存器

线性反馈移位寄存LFSR（linear feedback shift register）电路是由一串D触发器和异或门组成，它的设计是基于循环编码理论中的多项式算法原理。

当产生测试矢量时，通常使用没有外部输入的独立的线性反馈移位寄存（ALFSR）。一个n级的ALFSR产生一个n位二进制数的周期性伪随机序列。如果序列包含所有2^{n}-1非零值，那么周期便是2^{n}-1（全零值的模式时不允许出现的），此序列称为最大长度序列。序列的生产函数叫做原始多项式，根据异或门的连接方式可分位外接型和内接型。

外接型

图1(a)给出了外接型ALFSR电路的结构，电路中a_{n-1…}a_{0}是n位移位寄存器的n个触发器的输出，a_{n}是移位寄存器的输入，等于反馈信号的异或；即

a_{n}=\sum_{n-1}^{i=0^{⊕}}a_{i}c_{i}

=a_{0}c_{0}⊕a_{1}c_{1}⊕…⊕a_{n-1}c_{n-1}

图1 外接型ALFSR电路结构（略）

系数c_{n-1}…c_{0}选择生成原始多项式p(x)，如果c_{i}=1，触发器 的输出通过异或门电路反馈到移位寄存器的输入；如果c_{i} =0，触发器a_{i}的输出没有连接到反馈电路。

图1(b)给出了一个基于如下原始多项式的4位ALFSR电路。

p(x)=x^{4}+x+1

输出a_{0}是a_{1}在一个时钟周期之后的值，a_{2}是在两个时钟周期后的值，以此类推。输出序列通常用多项式的形式表示，如：

f(x)=a_{4}x^{4}+a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}

式中x^{k}代表k个时钟周期的延时。其中a_{4}=a_{1}⊕a_{0}且a_{4}⊕a_{1}⊕a_{0}=0，相应于原始多项式 p(x)=x^{4}+x+1 如果寄存器的4起始状态为1000，那么它的序列如表1所示。

内接型

内接型ALFSR结构如图2（a）所示，这类ALFSR通常有两个或更多个反馈分支。与第一类结构一样，c_{i}代表是否存在相对应的分支。使用这类4位的ALFSR电路如图2（b）所示，它的原始多项式是为：

p(x)=x^{4}+x^{3}+1

图2 内接型ALFSR结构（略）

这个多项式起源于图1(b)，是把图1(b)的多项式中的x^{j}用x^{n-j}替换所得。这种结构中，反馈连接的输入和每个触发器之间放置一个异或门。这样，在一个周期内最多只有一个异或门延时发生。但在第一类结构中，所有异或门都包含在反馈路径中，结果k 根反馈线就有k-1个门延时。

LFSR的改进

在上面的LFSR设计中，伪随机序列的长度不大于2^{n}-1。在绝大多数的应用中，长度为n的LFSR能生成长度为2^{n}-1的伪随机数序列，这已经满足了大多数需求。但是，某些特殊的场合可能需要产生长度为2^{n}的伪随机数序列。正如前面所述，如果节点反馈用到的是XOR门，LFSR不能达到全0的状态，从而不会遍历所以的状态。其实，只要在原有电路结构的基础上对电路稍稍的改进就能满足要求，产生长度为2^{n}的伪随机数序列。

图3是改进后的伪随机数发生器，它的长度为8，能产生长度为256的伪随机数序列。这种改进只是在原来相邻状态之间添加了一个附加的状态，即全0的状态。改进之前的初始状态输出为0000 0001时，下一个状态输出为1011 1000。改进之后，当LFSR的初始状态输出为0000 0001时，它的下一个状态输出为0000 0000，在之后的输出才为1011 1000。对于其他的当前状态输出，相应的后续状态并不改变。这样，原有的长度为2^{n}-1的伪随机序列就变成了长度为2^{n}的伪随机数序列。

仿真验证

本文用硬件描述语言Verilog 在QuartusⅡ软件下进行仿真，来验证改进电路的正确性。

Q uartusⅡ是Altera公司推出的新一代可编程逻辑器件设计环境，Verilog HDL(Hardware Description Language)是一种硬件描述语言，其语法与C语言类似。Verilog HDL允许在同一电路模型内进行不同抽象层次的的描述，可以从开关、门、RTL或行为等各个层次对电路模型进行定义。

改进后外接型伪随机测试矢量产生器（n=8）Verilog的实现代码：

module LFSR_8bits(clock,reset,random);
input clock,reset;
output[7:0]random;
integer i;
parameter[7:0]taps=8'b10001110;
wire feedback,bits0_6_zero;
wire[7:0] radom;
reg[7:0] lfsr_reg;
always@(negedge reset or posedge clock)
begin
if(!reset)
lfsr_reg=8'b0;
else
begin
for(i=0;i<=6;i=i+1)
if(taps[i]==1)
lfsr_reg[i+1]<=lfsr_reg[i]^feedback;
else
lfsr_reg[i+1]=lfsr_reg[i];
end
end
assign bits0_6_zero=~|lfsr_reg[6:0];
assign feedback=lfsr_reg[7]^bits0_6_zero;
assign random=lfsr_reg;
endmodule

仿真后波形如下图：

图4 改进后的伪随机数发生器仿真波形（略）

结束语

本文介绍了伪随机测试矢量产生的方法，着重介绍了LFSR作为伪随机测试矢量生成器的原理和电路，并对电路加以改进，长度为n的LFSR就能够产生长度为2^{n}的随机序列，增大了测试矢量的长度提高了错误的覆盖率，并用硬件描述语言Verilog对电路模型进行仿真验证，此方法在内建自测试中有很重要的应用。LFSR还有很多应用，包括：计数器、数据的加密和解密、数据的完整性检查及数据压缩技术等。