下载文档原格式
随机序列是一种重要的数据分析和加密技术，它能够在很多领域发挥重要作用。
然而，在计算机科学中，由于计算机系统是以确定性方式工作的，因此无法真正地产生真正的随机序列。
相反，计算机系统能够生成的是伪随机序列。
本文将详细介绍伪随机序列生成的原理。
在计算机系统中，伪随机序列是通过伪随机数发生器（Pseudo Random Number Generator，简称PRNG）产生的。
PRNG是基于特定的确定性算法设计的，它以一个称为种子（seed）的起始值作为输入，然后通过一系列的数学运算生成伪随机数序列。
种子是PRNG生成随机数的起始点，同样的种子将会生成同样的伪随机数序列。
PRNG的设计基于一个重要的原则，即一个好的PRNG在产生伪随机数时应具有良好的统计特性。
简而言之，这意味着生成的伪随机数序列应该在统计上符合一些随机性质。
例如，均匀分布是一个重要的统计特性，即生成的伪随机数应该均匀地分布在一个给定范围内。
其他常用的统计特性包括独立性（每个生成的数与前面的数无关）和周期性（序列重复的间隔）等。
常见的PRNG算法包括线性同余发生器（Linear Congruential Generator，简称LCG）和梅森旋转算法（Mersenne Twister）等。
LCG是最早出现的PRNG算法之一，它通过以下公式来递归生成伪随机数：Xn+1 = (a*Xn + c) mod m其中，Xn表示当前的伪随机数，Xn+1表示下一个伪随机数，a、c和m是事先确定的常数。
LCG算法的特点是简单、高效，但由于其线性特性，容易产生周期较短的伪随机数序列。
梅森旋转算法则是一种更复杂的PRNG算法，它具有更长的周期和更好的随机性质。
梅森旋转算法的原理基于一个巨大的素数，在该算法中，一个大的状态空间被旋转和变换，从而生成伪随机数。
梅森旋转算法由于其良好的统计特性和随机性质，广泛应用于计算机图形学、模拟和密码学等领域。
尽管PRNG能够生成伪随机序列，但由于其基于确定性算法，因此不适用于要求真正随机性的应用，例如密码学中的密钥生成和加密等。
电子信息工程专业课程设计任务书1 需求分析伪随机信号既有随机信号所具有的优良的相关性,又有随机信号所不具备的规律性. 因此,伪随机信号既易于从干扰信号中被识别和分离出来,又可以方便地产生和重复,其相关函数接近白噪声的相关函数, 有随机噪声的优点,又避免了随机噪声的缺点. 伪随机序列具有可确定性、可重复性,易于实现相关接受或匹配接受,故有很好的抗干扰性能. 因此伪随机序列在相关辩识、伪码测距、导航、遥控遥测、扩频通信、多址通信、分离多径、误码测试、线形系统测量、数据加扰、信号同步等方面均有广泛的应用. m 序列是伪随机序列中最重要的一种，是最长线性移位寄存器序列，m 序列易于实现，具有优良的自相关特性，在直扩通信系统中用于扩展要传递的信号。
可以通过移位寄存器,利用MATLAB 编程产生m 序列。
2 概要设计m 序列是最长线性反馈移位寄存器序列的简称，m 序列是由带线性反馈的移位寄存器产生的.由n 级串联的移位寄存器和和反馈逻辑线路可组成动态移位寄存器，如果反馈逻辑线路只由模2和构成，则称为线性反馈移位寄存器。
带线性反馈逻辑的移位寄存器设定初始状态后，在时钟触发下，每次移位后各级寄存器会发生变化。
其中任何一级寄存器的输出，随着时钟节拍的推移都会产生一个序列，该序列称为移位寄存器序列。
n 级线性移位寄存器的如图1所示：图1 n 级线性移位寄存器图中i C 表示反馈线的两种可能连接方式，i C =1表示连线接通，第n-i 级输出加入反馈中；i C =0表示连接线断开，第n-i 级输出未参加反馈。
因此，一般形式的线性反馈逻辑表达式为112201(mod 2)n n n n n i n i i a C a C a C a C a ---==⊕⊕⊕=∑L将等式左面的n a 移至右面，并将00(1)n n a C a C ==代入上式，则上式可改写为100n i n i C a -==∑定义一个与上式相对应的多项式()ni i i F x C x ==∑其中x 的幂次表示元素的相应位置。
c语言伪随机数生成算法C语言中常用的伪随机数生成算法包括线性同余发生器、梅森旋转算法和龙模算法等。
1. 线性同余法:线性同余发生器是一种基于线性递归的伪随机数生成器。
其算法基本原理是将当前数值与一个常数a相乘再加上一个常数c，再对m取模，得到下一个数值。
具体伪代码如下:seed = 设置初始种子a = 设置常数ac = 设置常数cm = 设置常数mnext = (seed * a + c) % mseed = next2. 梅森旋转算法:梅森旋转算法是一种基于循环移位的伪随机数生成算法，它利用梅森素数进行计算。
具体伪代码如下:state = 种子数W = 计算梅森素数function generateRandomNumber():if state < W:state = 计算下一个数else:state = 计算下一个数return state3. 龙模算法:龙模算法是一种结合线性同余发生器和移位发生器的伪随机数生成算法。
具体伪代码如下:state = 初始种子a = 设置常数ac = 设置常数cm = 设置常数mw = 设置常数wfunction generateRandomNumber():state = (state * a + c) % mrandomBits = state >> wstate = ((state & 0xFFFFFFFF) << (32-w)) randomBitsreturn randomBits需要注意的是，这些算法都是伪随机数生成算法，因为它们的结果是通过确定性的计算得到的，并不是真正的随机数。
python伪随机数生成算法标题：Python伪随机数生成算法一、引言在计算机科学中，伪随机数生成器（PRNG）是一种程序或算法，它可以生成看起来像是随机的数字序列。
这些数字是“伪随机”的，因为它们实际上是通过一个确定的算法产生的。
在Python中，我们有多种方法来生成伪随机数。
二、Python中的伪随机数生成算法Python提供了一个名为random的标准库，其中包含了许多用于生成伪随机数的函数。
1. random.random()：这个函数返回0.0到1.0之间的浮点数，包括0.0但不包括1.0。
2. random.randint(a, b)：这个函数返回a和b之间的一个整数，包括a和b。
3. random.choice(seq)：这个函数从非空序列的元素中随机选择一个返回。
4. random.shuffle(x)：这个函数将列表x中的元素顺序打乱。
三、Python伪随机数生成算法的工作原理Python的random模块使用了Mersenne Twister算法，这是一种非常高效的伪随机数生成算法。
它基于一个线性同余发生器（LCG），该发生器使用了一个巨大的周期长度（约为2^19937-1），并且具有良好的统计特性。
四、如何设置随机数种子Python的random模块提供了seed()函数来设置随机数种子。
如果不设置随机数种子，那么每次程序运行时都会生成相同的随机数序列。
如果设置了随机数种子，那么只要种子值相同，无论何时何地运行程序，生成的随机数序列都是一样的。
五、总结Python的伪随机数生成算法为我们提供了一种方便的方式来模拟随机事件。
理解这些算法的工作原理可以帮助我们更好地使用它们，并且可以让我们能够控制随机数的生成过程。
伪随机数生成算法代码-回复【伪随机数生成算法代码】伪随机数生成算法是一种通过既定的算法和种子值来模拟真随机数序列的生成过程。
它在计算机科学和统计学等领域中广泛应用，并被用于模拟、密码学、随机化算法等领域。
以下是一个基于线性同余法的伪随机数生成算法代码：pythonseed = 0 初始化种子值def pseudo_random():global seeda = 22695477 乘数m = 232 模数c = 1 增量seed = (a * seed + c) m 更新种子值return seed生成随机数序列示例for _ in range(10):print(pseudo_random())在上述代码中，`seed`代表种子值，是一个存储当前随机数状态的变量。
`pseudo_random`函数是主要的伪随机数生成器，它基于线性同余法计算生成随机数。
其中，`a`、`m`和`c`是预先定义的常数，用于控制随机数生成的产生规则。
下面，我们将逐步解析这个伪随机数生成算法的工作原理。
1. 初始化种子值：`seed = 0`。
由于随机数生成需要一个初始值作为起点，我们选择0作为种子值。
2. 定义常数：`a`、`m`和`c`。
`a`是乘法的乘数，`m`是模数，`c`是增量。
这些常数的选择是根据具体需求和算法特性进行调整的。
3. 生成随机数：伪随机数生成器的核心逻辑是`seed = (a * seed + c) m`。
它通过不断地更新种子值，生成下一个随机数。
乘法和加法是线性同余法的两个要素，``运算符是用来确保生成的数范围在0到`m-1`之间。
4. 返回随机数：`return seed`语句将生成的随机数作为结果返回。
通过以上步骤，我们就得到了一个简单的基于线性同余法的伪随机数生成器。
接下来，我们来讨论一些与这个算法相关的注意事项和改进方法。
首先，伪随机数生成算法是依赖于种子值的。
不同的种子值将产生不同的随机数序列。
信息科学与技术学院通信原理课程设计课题名称：伪随机m序列发生器的设计学生姓名：张昕灏2018508087学信息科学与技术学院院：专业年级：电子信息项目2018级指导教师：田敏副教授二O—三年七月十二日完成日期：目录前言1第一章设计内容及要求21.1设计内容21.2设计要求21.3方案选择2第二章m序列的特性分析42.1m序列的原理42.2均衡特性52.3游程分布52.4线性叠加性62.5自相关特性6第三章m序列设计83.1设计流程图83.2特征多项式确定83.3本原多项式确定103.4 m 序列的最终产生＜以五阶移位寄存器举例）11 第四章设计成果分析及总结134.1仿真结果分析134.2设计总结14 心得体会15 参考文献16 附录matlab 程序17 附录51 单片机实现方法18电路图18设计说明18结果验证18C51 代码及与对应matlab 代码20 数模转换输出代码：20 反馈链接状态及波形输出控制代码22 使用器件、八、-前言扩展频谱通信是一种不同于常规通信系统的新调制理论和技术，简称扩频通信[1]。
其设计思想是将待传输的信息信号用特定的扩频码扩展频谱后成为宽带信号进行传输，接收时再采用相应的技术手段将频谱压缩，恢复原来待传信息信号的带宽，从而实现通信。
扩频通信具有两个特点：传输信号的带宽远大于原始信息信号的带宽；传输信号的带宽主要有扩频码决定，此扩频码通常是伪随机码。
伪随机码(pseudo randomcode> 简称PN 码，可以人为产生与复制，具有类似白噪声的性质，相关函数具有尖锐的特性，功率谱占据很宽的频带，易于从其他信号或干扰中分离出来，具有优良的抗干扰特性，其特点是：具有尖锐的自相关函数；互相关函数值应足够小；有足够长的码周期，以确保抗侦破与抗干扰的要求；码的数量足够多，以实现码分多址的要求；平衡性好，以满足抗干扰的要求；项目上易于产生、加工、复制与控制[2]。
扩频通信的优势主要来自于伪随机码具有白噪声的统计特性。
伪随机码的生成及自相关函数的计算1.函数seq=ms_generator(registers,connections)是m序列的生成函数，其中参数registers给出了以为寄存器的初始状态，connections给出了m序列的发生器。
m序列生成的程序如下：function seq=ms_generator(registers,connections)registers=[0 0 0 0 1];connections=[1 0 0 1 0 1];n=length(connections);L=2^(n-1)-1;seq(1)=registers(n-1);for i=2:L;sum=0;for m=1:(n-1)sum=mod(sum+registers(m)*connections(m+1),2);endfor k=(n-1):-1:2registers(k)=registers(k-1);endregisters(1)=sum;seq(i)=registers(n-1);sprintf('seq=%d',seq(i));End运行结果：ans =Columns 1 through 151 0 0 0 0 1 0 0 1 0 1 1 0 0 1Columns 16 through 301 1 1 1 0 0 0 1 1 0 1 1 1 0 1Column 31（2）函数auto_corr()计算二进制序列seq的自相关函数，并画出函数曲线。
程序代码如下：function auto_correlation=auto_corr(seq)registers=[1 0 0 0 0];connections=[1 0 1 0 0 1];seq=ms_generator(registers,connections);seq=-1*(seq*2-1);len=length(seq);temp=[seq seq];for i=0:len-1auto_correlation(i+1)=seq*(temp(i+1:i+len))';endauto_correlation;plot(0:len-1,auto_correlation);运行结果：ans =Columns 1 through 1531 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1Columns 16 through 30-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1Column 31-1函数曲线图：（3）函数cross_corr()计算二进制序列seq1和seq2的互相关函数。
两种常见的伪随机数算法伪随机数是计算机生成的一系列看似随机的数字序列。
虽然伪随机数并不是真正的随机数，但它们的使用仍然非常广泛，并且在计算机科学和密码学等领域都有重要的应用。
在本文中，我将介绍两种常见的伪随机数算法：线性同余生成器和梅森旋转算法。
1. 线性同余生成器（Linear Congruential Generator，LCG）：线性同余生成器是一种简单的伪随机数生成器，它的计算公式为：X_{n+1} = (a * X_n + c) mod m其中，X_n是当前伪随机数，X_{n+1}是下一个伪随机数，a、c和m是预先设定的常数。
LCG算法的优点是简单易实现，并且具有较好的随机性。
通过选择合适的参数值，它可以产生高质量的伪随机数。
然而，LCG算法也有一些缺点。
当参数选择不当时，会导致周期较短或重复出现相同的伪随机数序列。
此外，在密码学等关键领域中，LCG算法的安全性较低，易受到攻击。
2. 梅森旋转算法（Mersenne Twister）：梅森旋转算法通过一个大型的位向量来保存当前状态，并通过一系列数学计算来生成下一个伪随机数。
为了提高性能，它使用了位操作和快速模运算等技术。
梅森旋转算法在实践中表现出色，具有较好的均匀性、分布特性和随机性。
目前，它广泛应用于计算机图形学、模拟与建模、游戏开发和密码学等领域。
总结：线性同余生成器和梅森旋转算法是两种常见的伪随机数生成算法。
线性同余生成器简单易实现，但有一定的局限性。
梅森旋转算法复杂、高效，并具有优秀的随机性能。
在选择伪随机数算法时，应根据具体应用需求和安全性要求进行评估和选择。
同时，为了增加随机性，可以采用多种算法的组合或使用更复杂的算法。
序列伪随机码产生及应用仿真matlab一、概述随机序列是一种具有随机性质的数字序列，可用于信息传输、通信系统、密码学、雷达等领域。
伪随机序列是一种经过数学算法产生的序列，其具有类似与随机序列的统计特性，但实际上是确定性的。
在通信系统中，伪随机序列广泛应用于码分多址技术、扩频通信、混沌通信等领域。
本文将介绍伪随机码的产生原理，并使用matlab进行仿真实现，以加深对该技术的理解。
二、伪随机码的产生原理伪随机码的产生主要包括线性反馈移位寄存器（LFSR）、加法（XOR）运算和乘法（AND）运算等步骤。
下面以LFSR为例，介绍伪随机码的产生原理。
1. LFSR原理LFSR是一种利用移位寄存器和反馈逻辑电路构成的伪随机码产生器。
在LFSR中，存在一个移位寄存器和一个反馈逻辑电路。
移位寄存器中存储了若干比特的信息，经过时钟信号的控制完成信息的移位操作。
而反馈逻辑电路则根据寄存器中的信息产生反馈信号，从而实现伪随机序列的产生。
2. 伪随机码的产生过程（1）初始化LFSR。
将移位寄存器中的初始状态设置为一个非零的值。
（2）循环移位寄存器。
根据时钟信号的控制，移位寄存器中的信息进行移位操作。
（3）根据反馈逻辑电路的输出，生成伪随机序列。
通过反馈逻辑电路生成的反馈信号，即为伪随机序列的一部分。
三、matlab仿真实现matlab是一种功能强大的科学计算软件，具有丰富的绘图和仿真功能。
下面将使用matlab进行伪随机码的产生和仿真实现。
1. 产生伪随机码在matlab中，可以使用shiftregister函数实现LFSR的移位寄存器功能。
结合matlab的位运算功能，可以方便地实现伪随机码的产生。
以下是一个简单的matlab代码示例：```matlab定义LFSR的初始状态state = [1 0 1 0 1];定义LFSR的反馈多项式polynomial = [5 2];产生伪随机码for i = 1:10获取LFSR的输出output = state(end);计算新的状态new_state = mod(sum(state(polynomial)), 2);更新状态state = [new_state, state(1:end-1)];显示输出disp(output);end```上述代码中，通过定义LFSR的初始状态和反馈多项式，使用循环产生了10个伪随机码的输出。
伪随机数生成原理
伪随机数生成原理是指通过一定的算法和种子，生成看似随机的数字序列。
这种序列与真正的随机序列有所不同，因为它们是通过计算机程序生成的。
在实际应用中，伪随机数可以用于密码学、模拟、游戏等领域。
伪随机数生成算法通常包括线性同余法、梅森旋转算法、拉格朗日插值法等。
其中，线性同余法是最简单的算法，通过如下公式生成： X(n+1) = (a * X(n) + c) mod m
其中，a、c、m为常量，X(n)为上一个随机数种子，X(n+1)为新生成的随机数种子。
在实际应用中，伪随机数生成原理的安全性和随机性都受到极大的关注。
因此，需要严格控制种子值的生成和算法的选择，以确保生成的随机数序列不易被猜测和攻破。
同时，还需要对生成的随机数序列进行统计分析，以检验其随机性和分布情况。
总之，伪随机数生成原理是计算机科学中一个重要的概念，它涉及到许多领域的应用和研究。
在实际应用中，我们需要理解伪随机数生成原理的基本原理和技术，以便更好地应用和优化算法。
- 1 -。
m序列的原理
M序列（Maximum Length Sequence）是一种伪随机序列生成
方法，也称为伪随机二进制序列。
它具有自相关性和互相关性很小的特点，并且具有最长周期。
M序列的生成原理基于反馈移位寄存器（Feedback Shift Register，FSR）。
FSR是由多个D触发器（D Flip-Flop）组
成的，每个D触发器的输出作为下一个D触发器的输入，并
形成移位链。
M序列的开始状态可以是任意的，并通过逻辑运算（如异或
运算）将连续的寄存器输出进行组合，生成伪随机序列。
M
序列的周期取决于FSR的长度，理论上可以达到2的n次方-1，其中n为FSR的长度。
生成M序列的特点如下：
1. 周期最长：当FSR的长度为n时，M序列的周期为2的n
次方-1。
2. 互相关性和自相关性较小：M序列具有较小的相互相关性
和自相关性，适合用于通信系统中的扩频技术。
3. 均匀性：M序列的值为+1或-1，每个值出现的概率相等，
具有较好的均匀性。
4. 硬件实现简单：使用FSR和逻辑运算可以很容易地生成M
序列，不需要复杂的计算。
M序列在通信系统中的应用广泛，主要用于扩频通信中的伪
随机序列生成、同步检测以及信号捕获等方面。
m序列快速生成算法摘要：一、引言1.背景介绍2.研究目的二、m序列概述1.m序列定义2.m序列性质3.m序列应用场景三、快速生成算法原理1.传统生成算法2.快速生成算法优势四、算法实现1.算法框架2.核心算法步骤五、实验与分析1.实验环境2.实验结果3.结果分析六、结论与展望1.算法应用成果2.未来研究方向正文：一、引言1.背景介绍在数字通信、密码学等领域，m序列作为一种重要的伪随机序列，广泛应用于信道编码、同步和加密等领域。
随着对m序列需求的增长，如何快速生成m序列成为了一个亟待解决的问题。
2.研究目的本文旨在提出一种高效的m序列快速生成算法，相较于传统生成方法，该算法在保证序列质量的同时，显著提高生成速度。
二、m序列概述1.m序列定义m序列是一种线性反馈移位寄存器（LFSR）生成的伪随机序列，其具有周期性、非周期性和多相位等特点。
2.m序列性质m序列具有以下性质：周期性、平衡性、相关性、遍历性和稳定性等。
3.m序列应用场景m序列在通信、密码、仿真等领域具有广泛应用，如信道编码、同步码、加密和解密等。
三、快速生成算法原理1.传统生成算法传统m序列生成算法主要包括线性反馈移位寄存器（LFSR）和查表法等，但这些方法存在生成速度慢、效率不高等问题。
2.快速生成算法优势本文提出的快速生成算法利用了m序列的性质，通过优化生成过程中的计算方法，提高生成速度。
四、算法实现1.算法框架本文提出的算法分为预处理、核心生成和后处理三个阶段。
2.核心算法步骤（1）预处理：对输入参数进行优化处理，减少计算复杂度。
（2）核心生成：根据m序列生成原理，采用优化算法生成序列。
（3）后处理：对生成的m序列进行质量评估和调整，提高序列性能。
五、实验与分析1.实验环境本文实验基于某处理器平台，使用Python编程语言实现。
2.实验结果实验结果表明，相较于传统算法，本文提出的快速生成算法在保证m序列质量的同时，提高了生成速度。
3.结果分析分析实验结果，可知快速生成算法在减少计算复杂度和优化生成过程方面取得了显著效果。
伪随机数生成算法 java伪随机数生成算法（Pseudorandom Number Generation Algorithm）是计算机科学中常用的一种算法，用于生成看起来像是随机分布的数列。
伪随机数生成算法是基于一定的初始条件和一系列的计算步骤生成随机数序列的。
与真正的随机数生成算法不同，伪随机数生成算法是可以被重复得到相同的随机数序列的。
在Java中，伪随机数生成算法主要是通过Random类来实现的。
Random类是Java中提供的一个伪随机数生成器。
下面是一个使用Random类生成伪随机数的示例：```javaimport java.util.Random;public class RandomNumberGenerator {public static void main(String[] args) {Random random = new Random();// 生成一个随机的整数int randomNumber = random.nextInt();System.out.println("随机整数: " + randomNumber);// 生成一个范围在[0, 10)的随机整数int randomInRange = random.nextInt(10);System.out.println("随机范围内整数: " + randomInRange);// 生成一个随机的浮点数double randomFloat = random.nextDouble();System.out.println("随机浮点数: " + randomFloat);// 生成一个范围在[0, 1)的随机浮点数float randomFloatInRange = random.nextFloat();System.out.println("随机范围内浮点数: " + randomFloatInRange);}}```上述代码中，我们首先通过`Random`类创建了一个实例`random`。
线性反馈移位寄存器实现产生伪随机数M序列-----在CN03平台上，主要体现为Random功能的实现。
什么是线性反馈移位寄存器？数学解释这里就不作介绍了，这里我们主要理解两个词语就行，一个是线性，它是指量与量之间的一种按比例、成直线的关系。
这里面有一点点的数学知识，就是说在ai∈(0,1)的存储单元，ai的个数表示为反馈移位寄存器的级，在某一个时刻，这些寄存器会有一个状态，共有2^n个状态，每个状态对应于域GF(2)上的一个N维向量,用(a1,a2,a3,……an)表示。
作为某一个时刻的状态，可以用一个函数f(a1,a2,a3…..an)来表示，从而称为该反馈寄存器的反馈函数，因此线性的意思，就是指如果这个反馈函数是a1,a2,a3….an的线性函数，那么这个反馈移位寄存器，就叫做线性反馈移位寄存器，比如f(a1,a2,a3,…an)=kna1⊕kn-1a2⊕….⊕k2an-1⊕k1an,其中系数ki∈{0，1}i=(1,2,3,…,n)。
另外一个词，就是反馈，这个词在我理解，就是说需要获得下一个状态就需要通过获得一个反馈值来实现。
这个反馈的值可以在接下来的两种实现LFSR的方式的解释过程中得到更深刻的理解。
为什么要使用线性反馈移位寄存器？使用线性反馈移位寄存器的作用：在很多领域上都有使用到LFSR，譬如说密码学、白噪声，还有我们这里的随机功能实现，之所以把它使用到我们的radio的随机功能里面，除了它可以产生伪随机数序列实现随机播放功能之外，更重要的是我们利用了它的两个特点。
其一，只需要在代码中开辟几个byte的位置，就能够实现随机序列的产生，需要的空间很少。
其二，是它的记忆功能，我们在随机的功能里面，选择了下一曲，则上一曲可以通过调整抽头数的序列来从新获得，而不需要开辟空间进行存储。
怎样产生伪随机数M序列？M序列的意思就是最大序列，专业点来说就是周期，就是这些不同的伪随机数在什么时候才会回到初始的输入状态，M序列的最大值为2^n-1，因为全0的初始状态不起作用，所以不能以全0的状态作为初始输入。
m-M 文档
1 相关概念
随机序列：可以预先确定又不能重复实现的序列 伪随机序列：具有随机特性，貌似随机序列的确定序列。
n 级线性移位寄存器，能产生的最大可能周期是21n p =-的序列,这样的序列称为m 序列。
n 级非线性移位寄存器，能产生的最大周期是2n 的序列，这样的序列称为M 序列。
图1线性移位寄存器
线性移位寄存器递推公式
11221101
n
n n n n n i
n i
i a c a c a c a c a c a
----==++++=
∑
线性移位寄存器的特征方程式
010
()n
n
i
n i
i f x c c x c x c x
==+++=
∑ ,ci 取值为0或1
定义 若一个n 次多项式f (x )满足下列条件：
(1) f (x )为既约多项式(即不能分解因式的多项式)； (2) f (x )可整除(x p +1), p =2n -1; (3) f (x )除不尽(x q
+1), q <p 。
则称f (x )为本原多项式。
定理 线性反馈移位寄存器能产生m 序列的充要条件为：反馈移位寄存器的特征多项式为本原多项式。
2 (2)GF 上本原多项式的实现算法 2.1二元域(2)GF 上的本原多项式
由于产生伪随机序列的反馈移位寄存器，其特征多项式系数C i 的取值为0或1，因此所寻找的本原多项式为(2)GF 上的多项式。
在二元域内不可以分解因式的多项式称为既约多项式，和普通代数一样，对于多项式
()0f α=，则称α为多项式的根。
输出a k
由抽象代数理论可以证明，若α是n 次本原多项式()f x 的根，则集合2
2
{0,1,}n
F α-= 可
构成一个有限的扩域(2)n G F 。
F 中的任一元素都可表示为1110n n a a a αα--+++ ，这样n 个分量的有序序列110(,,,)n a a a - 就可表示F 中的任一元素。
若既约多项式()f x 的根能够形成扩域(2)n G F ，则该多项式是本原多项式，否则不是本原多项式。
2.2 二元域(2)GF 上的本原多项式算法实现
(2)GF 上n 次多项式的通式为 1
2
1210()...n
n n n n f x x a x
a x
a x a ----=++++，系数是二元域上的元素（0,1）
既约多项式既不能整除,1x x +，0和1不可能是()f x 的根，即0a =1, ()f x 的项数一定为奇数。
另外，一个既约多项式是否能形成(2)n G F ，从而判断它是否为本原多项式。
N 次多项式的扩域，其中，120,1,,,n ααα 一定在扩域中，需要判断的是12
2
,n
n αα+- 是否也在扩域
中，从而形成全部扩域(2)n G F ，若在，则该n 次既约多项式是本原多项式，否则不是。
（1）给定二元多项式
1
2
1210()...n
n n n n f x x a x
a x a x a ----=++++，01a =
设α是f(x)扩域中的一个元素，且f(α)=0则有： n
n-1
n-11=a ++a +1αα
α （1）
（2）从n
α开始，计算α的连续幂。
在计算过程中，当遇到α的幂次为n 时，将（1）代入，一直计算到n
2
-2
α
（形成GF （2n ）），再计算n
2
-1
α。
若n
2-1
α
=1，则证明()f x 能被n
21
x
1-+整
除，而不能整除1q
x +（21n
q <-），判定为本原多项式。
在计算α的连续幂过程中，若
q
x =1（21n
q <-），则证明()f x 能被1q
x +整除，判定为非本原多项式，停止计算。
在计算机实现时，n 个分量的有序序列110(,,)n a αα- 与α的任一连续幂有着一一对应的
关系，可以用有序序列110(,,)n a αα- 来表示α的任一连续幂。
q
α用110(,,)q q q n a αα- 来
表示，n α用110(,,)n n n n ααα- 来表示，则1q α+可用110(,,)q q q n ααα- 左移一位来实现，若移位前最高位1q n α-=1，表示出现了n α，则1q α+的有序序列表示为
1
1
1
1
11
10
0(,,)n q n q n
n n αααααα+++--+++ ，加法为模2相加，这样可以得到α的连续幂。
在计算过程中，若q α=1（21n q <-），则判定为非本原多项式。
若q α（21n q <-）都不为1，且21
n
α-为1，则判定()f x 为本原多项式。
图2寻找本原多项式总流程图
图3判断当前多项式是否为本原多项式流程图
3 m 序列实现
本原多项式系数可确定反馈逻辑
11221101
n
n n n n n i
n i
i a c a c a c a c a c a
----==++++=
∑
4 M 序列实现
M 序列是一种非线性的伪随机序列，是由非线性移位寄存器产生的码长为2n 的周期序列。
其构造方法，只要在m 序列适当的位置插入一个0状态，即可完成码长为2n -1的m 序列向码长为2n 的M 序列的转换。
其反馈逻辑
1212121(,,)(,,)n m n n n f x x x f x x x x x x --=+ ，即
1122110121121
1
n
n n n n n n n i
n i
n n i a c a c a c a c a a a a c a
a a a --------==+++++=
+∑。
