什么是伪随机序列?

什么是伪随机序列?

[拼音]：weisuiji xulie

[外文]：pseudorandom sequence

序列元素间有确定关系存在，但具有与随机序列类似性质的一种特殊的离散信号形式，可表示为…，ɑ-1，ɑ0，ɑ1，ɑ2，…

其中ɑi可取值0，1或1，-1；也可以取符号域GF(q)（见分组码）中的元素。前者叫二元序列，后者叫 q元序列。但实用中最主要的还是前者。序列长度可以为有限，也可以为无穷。后者主要着重的是周期序列，即存在最小正整数夞，使对一切i有ɑp＝ɑp+i，p为周期。

序列的各元素为相互独立且具有相同分布的随机变量时，称为随机序列。实际应用的主要是伪随机序列。它指序列元素间有确定关系存在，但具有与随机序列类似的下列性质：

（1）在有限长度或一周期内各元素的个数相差不超过1，即接近等概率；

（2）出现 l个相同值或称l长游程的概率接近1/ql；

（3）相关函数

(1)

在τ＝0时为p，τ厵0时不超过±1，式中p为序列的长度或周期。实际上有时将大体满足以上条件的序列也称为伪随机序列。

发展概况

相关函数接近冲激函数的信号是相关检测系统中比较理想的形式。为了构造这样的信号，1953年R.H.巴克首先找到长度为有限的一些二元序列具有上述特点，称之为巴克序列。可惜，已知的巴克序列最大长度为13，且已证明不存在比13更长的奇长巴克序列，对于偶长巴克序列长度应为4v2，已证明2＜v＜54的序列也不存在，故难以满足要求较高的场合。为了获得长度较长、性能较好且数量较多的序列，理论上较易解决的是可用反馈移位寄存器实现的无限周期序列。这主要有M序列和L序列等，前者为线性移位寄存器序列，后者为非线性移位寄存器序列。

应用中除了要求单个序列有好的性能外，还希望不同序列间的互相关函数小，理论上解决较好的有戈尔德序列族和嵩忠雄序列族，均为线性族。非线性的则有弯函数序列族或称OSW序列族。

序列的构造

伪随机序列可用图中 ɑ的反馈移位寄存器得到。图中f(ɑn+i-1，ɑn+i-2，…，ɑi)表示反馈函数。n 级移位寄存器只能有2n（一般为qn）种状态， 故经一定时间后会回到原来的某一状态， 产生周期性输出， 若反馈函数的输出ɑn+i与各输入ɑn+i-1，…，ɑi间有线性关系存在，则为线性移位寄存器，否则为非线性移位寄存器。图中b和c分别是三级线性和非线性反馈移位寄存器。

对于线性移位寄存器序列有

ɑn+i＝c0ɑn+i-1＋c1ɑn+i-2＋…＋cn-1ɑi (2)

(i＝0，1，…)

它当初始值 ɑ0，ɑ1，…，ɑn-1全为零时输出恒为零。除去这种全零状态外，它最多可能取遍所有2n-1个非零状态，故最大周期为2n-1。一般情况下周期是2n-1的因子。

周期达到2n-1的序列称为最长线性移位寄存器序列，简称M序列，图中b就是三级M序列，它的输出为…，0，0，1，0，1，1，1，…。M序列完全满足伪随机序列的三点要求，特别是它的相关函数为

(3)

因而是典型的伪随机序列。

M序列的周期一定是2n-1，实用上还需要有其他的周期，这可用非线性移位寄存器序列得到。n级非线性移位寄存器序列的周期不大于2n，达到2n的序列称M序列。

一般M序列的相关函数不完全接近冲激函数。接近冲激函数的非线性移位寄存器序列主要有二次剩余或称勒让德序列，简称L序列，以及孪生素数序列。两者的相关函数均如式(3)。L序列是周期为形如4k-1的素数时所构造的序列，k为自然数。前几个L序列的周期为3，7，11，19，23，…。当周期不超过任一大的正整数时，L序列的种类比M序列多得多。孪生素数序列是周期为k(k+2)的伪随机序列，在此k与k+2均为素数，前几个序列的周期为15，35，143，…。

伪随机序列族

应用中有关的全部序列叫序列族，且通常取周期相同的一族序列。既有良好的自相关特性又有良好的互相关特性的线性伪随机序列族，主要有戈尔德序列族和嵩忠雄序列族等。

戈尔德序列族是由适当选择的一对n级M序列线性组合构成，在此n呏1(mod 4)或n呏2(mod 4)。序列族中共有2n+1个序列，周期均为2n-1，两两之间的互相关函数最大值为2[(n+2)-2]+1，此处[X]表示不超过x的最大整数。n为偶数时戈尔德序列的性能较差，而嵩忠雄序列却可达到最佳。后者由n级M序列和相应的n/2级M序列的线性组合构成。它的周期也是2n-1，但序列只有2


个，互相关函数最大值是2


+1。

应用

伪随机序列作为一种信号形式，具有良好的相关特性，可作为雷达测距、同步和线性系统测量的信号。它还具有伪随机性，因而可用于加密系统和伪随机跳频等场合。这时常将序列经非线性变换，即构造前馈序列；或者用多个序列组合后输出以增加保密性。它还可用以产生伪随机数适于计算机的系统模拟和在数字系统中作为误码测试信号等。伪随机序列还可用于扩频，在多址系统中作为地址信号等。伪随机序列有多方面的应用，对它的要求也很不相同。例如用于多址信号时不但要求它通常的互相关函数要小，而且和在中间任意一位处反相后的互相关函数也要小；又如用于加密系统时，不但要考虑它的分析，而且要考虑它的综合和计算复杂性。关于非线性移位寄存器序列，尚有许多问题没有完全解决。

参考书目

万哲先、代宗铎、刘木兰、冯绪宁：《非线性移位寄存器》，科学出版社，北京，1978。S.W.Golomb， Shift Register Sequences，Holden-Day， San Francisco，1967.