二元给定序列非线性移位寄存器的综合与产生

   摘要：依据非线性移位寄存器的原理，文中讨论二元给定序列非线性反馈移位寄存器的综合算法，用C语言编程，找到了产生该序列的非线性移位寄存器。借助EDA技术，以FPGA为硬件基础，经过设计优化构成定长序列和给定周期序列的伪随机序列发生器，并进行了仿直实验，用硬件实验证实了设计的合理性。

    关键词：非线性伪随机序列 非线性移位寄存器 现场可编程门阵列

1 引言

伪随机序列具有良好的随机性，在伪码测距、导航、遥控和遥测、扩频通信、多址通信、分离多径、数据加乱、信号同步、误码测试、线性系统测量、天线方向测量和各种噪声源等方面得以广泛的应用。伪随机序列的产生可以通过线性移位寄存器即m序列来实现，也可以通过非线性移位寄存器来实现。非线性移位寄存器比起线性移位寄存器具有许多优越性，非线性移位寄存器的总线比线性反馈移位寄存器的总数要多得多，给实际应用提供了充分的选择余地。但是非线性反馈移位寄存器一般比线性反馈移位寄存器在逻辑上要复杂得多，因而也在设备上带来了相应的复杂性。本文从非线性移位寄存器的综合问题发出，讨论给定序列的综合问题，并在大规模可编程逻辑器件上实现这种非线性伪随机序列发生器。

2 非线性移位寄存器的综合

关于非线性移位寄存器的综合问题可以有很多种提法，这里讨论产生定长非周期序列和给定周期序列的最短移位寄存器的方法。

    2．1 定长序列的综合

定长序列的综合寻求长为l给定二元序列（a1,a2,3,…al, …）的最短移位寄存器。产生上述定长二元序列的n(n<l)级反馈移位寄存器，其反馈函数为f(x1,x2,…，xn)，则序列的前项所形成的状态序列为S1，S2，…，Sl-n,Si=(ai+ai+1,…,ai+n+1)（i=1,2,…,l-n）必须具备下列条件之一：

（1）状态序列中诸顶点彼此互异；

（2）状态序列诸顶点中有相重者。

满足条件（1）时，则反馈函数为

满足条件（2）时，若n0为最小正整数（n1≤l-n），使Snl与它前面的一个状态Sn0相重(1≤n0≤n1≤l-n):Snl=Sn0

此时必须

状态Sl,S2,…，Sn0Sn0+1,…,Sl-n必须彼此互异，于是反馈函数可写成

寻求长为l给定序列的最短移位寄存器可归结为寻求满足条件（1）或（2）的最小自然数n(n<1)的问题，满足上述条件的最小自然数n(n<l-1)一定存在。

因此，寻求该序列之最短移位寄存器可以采用从n=1开始逐步搜索的方法来求得满足条件（1）或（2）的最小自然数n及相应的反馈函数f(x1,x2,…,xn),其算法框图如图1所示。

图3

    2．2 给定周期序列的综合

给定周期序列的综合即寻求产生给定周期序列（a1,a2,…,al,al+1,…）的最短移位寄存器。给定周期序列的综合被归结为寻求使l个状态Si=(ai,ai+1,…,ai+n-1)，i=1,2,A,l彼波互异的最小自然数n(n≤l)的问题。状态序列S1,S2,…，Sl,其中Si=(ai,ai+1,…,ain+1),1≤i≤l两两不同，则产生给定周期序列的移位寄存器的反馈函数为

其算法流程如图2所示。

图4

3 非线性伪随机序列的FPGA实现

FPGA为现场可编程门阵列逻辑器件，是倍受现代数字系统设计工程师欢迎的最新一代系统设计积木块。FPGA为逻辑门级编程，其芯片中有被互连网络包围的逻辑单元，芯片四周为可编程的输入/输出单元阵列，其互连模式亦是可编程的，用户可以通过现场编程决定每个单元的功能及它们的互连关系。FPGA具有集成度高，编程灵活，阵列引脚数多，功耗低，设计编程速度快等特点。Altera公司的FLEX10K系列中的EPF10K10LC84-4型FPGA，基于SRAM的在系统可编程结构，该FPGA可利用Altera公司的MAX+PlusII软件进行编程。MAX+PlusII软件有原理图输入法和硬件语言输入法，本设计采用原理图输入法，经过编译、时序仿真优化后，下载至EPF10K10LC84-4中。

3．1 定长序列的实现

以长为28序列为说明设计过程，给定序列为

（0,1,1,1,0,1,01,1,0,0,01,1,1,1,1,0,0,1,1,0,1,1,1,0） (1)


    输入l=28和（1）序列，C语言程序计算移位寄存器反馈函数为

f(x)=x1x2x3x6+x2x3x4x5+x1x2x3x5+x2x4x6(x3+x1x5)+x1x3x4x6+x1x3x5x2x4+x1x5x6x2x3x4+x4x5x6(x3+x1)+x1x2x6+x1x2x4x5

用原理图输入法构成图3所示的电路。其中cp端为时钟，start端为起始状态输入端，x28为序列输出端，其仿真波形如图4所示。

图5

    3．2 给定周期序列的实现

以周期15给定周期序列为例，其一个周期序列为

（0，1，1，1，，0，1，01，01，1，0，0，0，1） （2）

用C评议程序计算移位寄存器反馈函数为

f(x)=x1x2x3x4+x1x2x5(x4+x6)+(x2x4+x1x2x4)x3x5x4x6x2x3+x4x5x6x1x2+x1x3x6(x2+x4+x5)+(x4+x2)x1x3x5x6

用原理图输入法构成的电路如图5所示，仿真波形见图6。

将图3和图5电路下载到EPF10K10LC84-4中，用Tektronix TDS3052型示波器观察波形，其波形如图7所示。

图6、7

4 结论

本文从非线性伪随机序列的综合出发，对寻找给定序列非线性反馈移位寄存器反馈函数的算法进行了讨论，用C语言和Mathematica编程计算定长序列和给定周期序列的反馈函数。利用MAX+PlusII软件设计了定长有限序列和给定周期序列发生器，并在EPF10K10LC84-4中实现了该非线性伪随机序列发生器并进行验证。非线性伪随机序列发生器产生序列数多，给实际应用带来更多的选择。