[科普中国]-移位寄存器序列

移位寄存器序列(shift register sequence)是一类重要的码，它是数字通信中利用反馈移位寄存器产生的一种伪随机码，由初始状态(x₁，x₂，…，xn)依反馈逻辑函数xn+1=f(x₁，x₂，…，xn)产生的二元序列x₁，…，xn，xn+1，…，称为移位寄存器序列，简称移存器序列1。

基本介绍移位寄存器序列是数字通信中利用反馈移位寄存器产生的一种伪随机码，由初始状态(x1，x2，…，xn)依反馈逻辑函数xn+1=f(x1，x2，…，xn)产生的二元序列x1，…，xn，xn+1，…，称为移位寄存器序列，简称移存器序列。这里f是Fn2到F2的一个映射，它所产生的状态转移图是二元域上德布莱英-古德图的一个部分图，当f的多项式表示是x1，…，xn的线性齐次式时，相应的移存器序列称为线性的，否则称为非线性的，当状态转移图是两两不相交的圈的并时，相应的f及序列称为非奇的，移存器序列中最简单的两种是由f(x1，x2，…，xn)=x1及f(x1，x2，…，xn)=1+x1所产生的，分别称为纯轮换移存器及补轮换移存器。它们都是非奇的，其状态转移图中圈的总数分别是

及，

其中m为n的最大奇因子，这两种移存器在移存器序列理论中占重要地位。n级线性移存器序列中周期最长(等于2n-1)的一种称为m序列，它共有φ(2n-1)/n个，恰与F2上全部n次本原多项式一一对应，由于它具有很好的伪随机性，已得到充分研究和广泛应用，n级移存器中周期最长(等于2n)的一种称为M序列，它是非线性的，非奇的，它共有

个，恰与n级德布莱英-古德图的全部欧拉游一一对应，由于它具有巨大的数量和较好的伪随机性，已受到保密通信界的普遍重视，移存器序列是一类有着广泛应用的伪随机码，不但在保密通信中起加密的作用，在连续波雷达中可用作测距信号，在遥控系统中可用作遥控信号，在多址通信中可用作地址信号，在数字通信中可用作群同步信号，此外还可用作噪声源等1。

相关说明移位寄存器序列是指由移位寄存器输出的由“1”和“0” 构成的序列。相应的时间波形是指由“1”和“-1”构成的时间函数，如图1所示2。

产生移位寄存器序列的移位寄存器如图2所示，它是由时钟控制的n个串接的存储器、移位脉冲发生器、反馈函数和模2加法器组成构成。组成移位寄存器的存储器称为移位寄存器的级，从左至右为第一级、第二级、....第n级，移位寄存器内容为0或1，在某一时刻， 移位寄存器各级的存数按顺序排列所组成的序列称为该移位寄存器的状态。规定移位寄存器的状态是各级存数从右至左的顺序排列而成的序列，这样的状态叫正状态或简称状态。反之，称移位寄存器状态是各级存数从左至右的顺序排列而成的序列叫反状态。如果用an-i(i=1, 2, 3，..，n)表示第i级的状态(存数)，则an-i=0或1。反馈函数的输入端通过系数与移位寄存器的各级状态相联(ci=0断，或ci=1通)输出通过反馈线作为x1的输人。移位寄存器在时钟的作用下把反馈函数的输出存入x1，在下一个时钟周期又把新的反馈函数的输出存入x1而把原x1的内容移入x2，依次循环下去，xn不断输出。

根据反馈函数对移位寄存器序列的作用方式，可将序列发生器分为：

1)线性反馈移位寄存器序列产生器(LFSRSG)：如果为的模2加。

2)非线性反馈移位寄存器序列产生器(NLF-SRSG)：如果不是的模2加。

移位寄存器可有不同的初始状态和不同的反馈逻辑，产生不同的序列。这就是说，移位寄存器序列是由它的初始状态和反馈逻辑确定的。

可以得到下列结论：

1)线性移位寄存器的输出序列是一个周期序列。

2)当初始状态是0状态时，线性移位寄存器的输出都是0序列。

3)级数相同的线性移位寄存器的输出序列和反馈逻辑有关。

4)同一个线性移位寄存器的输出序列还和起始状态有关。

5)对于级数为n的线性移位寄存器，当周期p=2ⁿ-1时，改变移位寄存器初始状态只改变序列的初相。这样的序列称为最大长度序列或m序列2。

本词条内容贡献者为:

王海侠 - 副教授 - 南京理工大学