基于FPGA的伪随机序列发生器设计

摘要：讨论了应用移位寄存器在Ahera的FPGA芯片中实现线性和非线性伪随机序列的方法，该算法基于m序列本原多项式来获得线性m序列和非线性m子序列移位寄存器的反馈逻辑式。文中给出了以Altera的QuartusⅡ为开发平台，并用VHDL语言实现的m序列的仿真波形。
关键词：伪随机序列；m序列；m子序列；移位寄存器；VHDL语言编程

0 引言
    伪随机序列现已广泛应用于密码学、扩频通讯、导航、集成电路的可测性设计、现代战争中的电子对抗技术等许多重要领域。伪随机序列的伪随机性表现在预先的可确定性、可重复产生与处理。伪随机序列虽然不是真正的随机序列，但是当伪随机序列周期足够长时，它便具有随机序列的良好统计特性。在已有的序列中，m序列的应用最为成熟和广泛，为此，本文给出线性m序列和基于m序列的非线性m子序列的FPGA实现方法。由于FPGA的内部逻辑功能是通过向内部静态存储器单元加载配置数据来实现的，其配置文件决定了逻辑单元的逻辑功能以及模块间或与I／O间的连接，故可最终决定FPGA实现的功能。FPGA的这种结构允许多次编程，并享有快速有效地对新设计进行优化的灵活性，为此，本文选用了altera的cyclone系列FPGA芯片。EPlCl2-240PQFP，该芯片内部有12060个逻辑单元、239616 bit RAM、两个锁相环(PLL)。本文应用移位寄存器理论来产生序列，其算法的关键是找到线性m序列和非线性m子序列移位寄存器的反馈逻辑式。

1 m序列的实现
1．1 基于FPGA的m序列实现
    利用反馈移位寄存器产生0、1序列时，其n位反馈移位寄存器的逻辑功能如图1所示。

    图中，xi表示寄存器所处的状态，通常用0和1来代表两个可能的状态，并且把0和1看成是有限域GF(2)的两个元素。f(x0，x1，…，xn-1)刻划了移位寄存器反馈逻辑的功能，它可以看成一个定义在GF(2)上并且在GF(2)中取值的n元函数，当f(x0，x1，…，xn-1)可以表示成一线性齐次函数时，即GF(2)，相应的反馈移位寄存器是线性的，而由线性移位寄存器产生的序列就称为线性移位寄存器序列。m序列就是线性移位寄存器序列。
    对于一个n级m序列移位寄存器来说，它在每一时刻的内部状态都可以看做有限域GF(2)上的一个n维向量，而反馈函数就是刻划了从每一时刻的状态到下一时刻状态的转移规律，或者说反馈函数定义了n维向量空间上的一个线性变换。
    通常可以用Vn(F)代表域GF(2)上全体n元数组构成的n维向量空间，a=(a0a1a2…an-1…)代表n级移位寄存器产生的m序列。n级m序列移位寄存器的状态可以看做Vn(F)中的向量。设f(λ)=λn+Cn-1λn-1+…+C0是多项式环F[λ]中的一次n多项式，那么，对于G(f)中的线性移位寄存器序列，从状态(akak+1…ak+n-1)到下一个状态(ak+1ak+2…ak+n)的转移就可以看成是Vn(F)的一个线性变换。由于ak+n=cn-1ak+n-1+cn-2ak+n-2+…+coak，于是，状态转移变换用矩阵写出来就是：

 称为线性移位寄存器的状态转移矩阵，显然，状态转移矩阵T和初始状态完全刻画了线性移位寄存器所产生的序列。它在此建立起了反馈
    =GF(2)之间的关系，这样就可以直接从m序列本原多项式出发，在FPGA中实现m序列移位寄存器结构并产生m序列。

    若本原多项式的m序列移位寄存器反馈逻辑为，则本原多项式的m序列的VHDL语言实现代码如下：

图2所示是该序列在QuaitusⅡ开发平台中的仿真波形。

    
    其中，斜体0、1代码表示序列又一周期的开始，周而复始。
1．2序列伪随机性分析
    对本原多项式是的m序列伪随机性进行分析时，主要是分析其平衡性和游程特性。首先是平衡性。通常在一个周期中，m序列的l出现的次数为2n-1次；0出现的次数2n-1-1次。其次是游程特性。即对于O<k≤n-2，其长度为k的0游程出现2n-k-2次；长度为k的l游程也出现2n-k-2次；长度为n-1的0游程出现1次；长度为n的l游程出现1次。以上就是其中出现的全部游程。
    平衡性和游程特性分析表明该序列符合m序列的统计特性。

2 非线性m子序列实现
    m子序列是与m序列具有同周期、相同平衡性和不同局部游程的序列，m子序列移位寄存器的反馈多项式与m序列移位寄存器的反馈多项式的关系，可以根据m子序列的构造思想来计算，其中交换一对共轭状态的后继意味着反馈函数f(x)在共轭状态处取补，其中s=(s0s1…sn-1)，，即f(x)’=f(x)+1。其它状态处反馈函数不变，即f(x)’=f(x)+0。因此，可由布尔函数理论推知：

    
    现以本原多项式所对应的移位寄存器为出发点，以周期29-1的某一m子序列为例，给移位寄存器赋以初始值{000000001}，并在此交换两对共轭状态的后继，其中；
那么，由布尔函数理论及式(1)和式(2)有：m子序列移位寄存器反馈逻辑为：
，
若将线性m序列和非线性m子序列整合在一起，那么，在Quartus中生成的序列发生器模块如图3所示。

    图3中，L_prsg模块是线性伪随机序列发生器(m序列发生器)，NL_prsg模块是非线性伪随机序列发生器(m子序列发生器)。时钟clk选用2 MHz。根据SEL[0．．2]端子可选择不同周期的序列，m序列发生器中R序列周期可选；m子序列发生器中的序列周期可选。若N_L_SEL端子取1，则选择非线性伪随机序列发生器，SEL[0. .2]端子取101，则选择周期是29-1的m子序列。图4所示是序列发生器模块的仿真波形图。

    比较周期是29-1的某一m子序列与同一周期的m序列可知，其两者具有相同的周期、平衡性、相近的自相关性以及不同的局部游程和不同的线性复杂度。QUARTUS中的仿真报告表明，L_prsg模块将耗费96个Logic Elements，NL_prsg模块则耗费35个Logic Elements。

3 结束语
    伪随机序列在通信、密码学、雷达、导航、芯片内建自测试方面具有广泛的应用，本文给出了线性m序列和基于m序列的m子序列的FPGA实
现方法。本方法应用移位寄存器理论。从m序列的本原多项式出发，其算法核心是找到m序列本原多项式与线性m序列和m子序列移位寄存器反
馈逻辑式之间的关系，然后采用VHDL语言编程，并借助Qualt usⅡ开发平台实现序列。
    文中通过对伪随机性分析表明：其所产生的序列符合m序列的统计特性。m子序列也具有优良的伪随机特性，从而验证了该算法的正确性。