4.2线性反馈移位寄存器序列

**学院
本科实验报告
（2011-2012学年下学期）
课程名称：
任课教员：
系：
专业：
二0一一年
《》课程实验报告
实验项目名称：线性反馈移位寄存器设计
系：专业：指导教员：
姓名：学号：成绩：
同组姓名：
实验地点：实验室实验日期：
线性反馈移位寄存器的设计一、实验目的和要求
学习线性反馈移位寄存器的设计、分析和测试方法。

二、实验内容和原理
（1）实验内容
按图设计一个,使之生成多项式430
++。

x x x
（2）实验原理
即线性反馈移位寄存器，它由寄存器加上生成，不同的决定了不同的生成多项式。

三、操作方法与实验步骤
1、分析线性反馈移位寄存器的工作原理，设计基本框架。

2、在Ⅱ中建立线性反馈移位寄存器工程，进行程序编写、调试、编译、仿真。

四、实验数据记录与处理
五、实验结果与分析
本实验需注意理清各端口的关系，正确选择端口类型。

六、心得与体会
通过此次实验,我学会线性反馈移位寄存器在实际中的应用，可以较清楚的控制各个端口之间的关系，程序代码清晰明了。

七、程序代码
( );
[3:0]Q;
, ;
;
([2] [0]); ([1] [0]);
1 (Q[3] [0] );
2 (Q[2] [3] );
3 (Q[1] , e );
4 (Q[0] , f );
( );
q ;
, ;
q;
@( )
q<;
()
q<=1'b0;。

线性反馈移位寄存器LFSRverilog实现⼀、什么是LFSR？线性反馈移位寄存器（linear feedback shift register, LFSR）是指，给定前⼀状态的输出，将该输出的线性函数再⽤作输⼊的移位寄存器。

异或运算是最常见的单⽐特线性函数：对寄存器的某些位进⾏异或操作后作为输⼊，再对寄存器中的各⽐特进⾏整体移位（百度百科定义）。

线性反馈移位寄存器反馈分为两种，⼀种是IE型的LFSR，即异或门内接的线性反馈移位寄存器：另⼀种是异或门外接的线性反馈移位寄存器，简称EE型LFSR：gi表⽰接不接⼊反馈，只能为0或1，为1即为接⼊，为0不接⼊。

关于线性反馈移位寄存器（LFSR）数学原理更加详细的介绍，可以参考下⾯这篇⽂章。

本⽂主要是介绍如果使⽤verilog来实现LFSR电路的编写。

需要注意的是，LFSR是伪随机的，这意味着它只是接近随机，并不是完全随机的。

这是因为其实从LFSR的任何状态，你都可以预测下⼀个状态。

有⼀些重要的移位寄存器属性需要注意：LFSR是伪随机的，从LFSR的任何状态，都可以预测下⼀个状态。

影响下⼀个状态的⽐特位叫做抽头。

当抽头使⽤XOR门时，全0状态不会出现，这是因为0与0异或将始终产⽣0，此时LFSR将停⽌运⾏。

当抽头使⽤XNOR门时，全1状态不会出现，这是因为1与1同或（异或⾮）将始终产⽣1，此时LFSR将停⽌运⾏。

任何LFSR的最⼤可能迭代次数 = 2^N-1，N为级数，也就是寄存器bit位的个数。

那么怎样的LFSR才能遍历2^N-1个状态，产⽣最⼤的迭代次数呢？也就是到底寄存器的哪些位去组合然后反馈到输⼊端，才能使该LFSR的所有2^N-1个状态都出现呢？这⾥官⽅给了⼀个表，我们可以根据这个表来确定LFSR的结构：需要注意的是LFSR的每⼀位的索引是从1开始，然后到N，⼀共2^N-1个状态（因为使⽤异或反馈时要除去全0状态，使⽤异或⾮反馈时要除去全1状态）。

有趣的线性反馈移位寄存器(LFSR)最近一直在研究信道编码，发现在信道编码里面有一个电路比较重要也比较有趣，那就是线性反馈移位寄存器LFSR ，相信大家对LFSR 电路也不陌生了,在通信领域lfsr有着很广泛的应用,比如说M序列,扰码,信道编码,密码学这方面都有很广泛的应用,LFRS的结构一般如下图：其中他需要一个生成多项式为:这个多项式是一个本原多项式，然后知道这个电路有一些有意思的性质，下面我以m = 3 来做个例子具体的电路图如下所示：假设开始的时候（D2，D1，D0 ）= （0，0，1），那么每过一个时钟周期会进行跳变一次，可以看到具体的跳变如下所示：然后我们可以看到这个计数器循环起来了，很好玩吧，无论进入那样一个状态除了0之外，都可以循环着回来，其实这里就相当于了一个3bit的伪随机数，很有意思，不是所有的多项式都有这个特性，我们现在在从数学上面来看看这个问题,其实最上面的电路是可以看成是一个除法电路，在Galois域的一个除法电路。

现在假设的是R（x）是寄存器中剩余的数据，M(x)是输入的码字多项式，然后数学公式可以表示成：然后我分别计算出了Ｍ（ｘ）的各种情况，然后我们单独进行一下７次方的运算发现７次方的运算和０次的时候的余数是一样的然后我们发现其实在上面的电路中对多项式的除法也是可以循环起来的,可以验证的是把这个记成上面的式子是可以循环的,然后我又想到了CRC的计算,CRC的计算也可以通过一个除法电路来实现,假设码子多项式为生成多项式为那么CRC的码字为这样我们同样可以用LFSR电路来进行实现首先对M(x)乘以一个x的r次方,然后去去除G(x),在电路上的表现就是所以在输入码字以后还需要多输入r拍的0这样才能使最后的CRC码字数据.同理这个电路也可以进行CRC校验，把生成的数据全部都依次输入进这个。

【常⽤电路】线性反馈移位寄存器（LFSR）读华为技术⽂档《FIFO经验谈》看到的这个电路： FIFO的读写地址产⽣⽐较简单，当读使能有效时，在时钟作⽤下，读地址加1；当写使能有效时，写地址加1。

当FIFO深度较⼤时，同时FIFO的速度要求较⾼时，可以采⽤线性反馈移位计数器（LFSR）。

它的速度⾮常快，但是要牺牲⼀个地址。

针对同步的⼤FIFO，它们的读写地址完全可以使⽤线性反馈移位寄存器 LFSR 产⽣，⽽不是简单的加1操作，极⼤的提⾼了速度，如果对FIFO的利⽤率没有很⾼要求的时候，推荐使⽤该⽅法。

使⽤LFSR的优点是在XILINX的FPGA中布线，可以使⽤LUT直接完成。

1/************************************************************\2* *3* Generation of Read and Write address pointers. They use *4* LFSR counters, which are very fast. Because of the *5* nature of LFSR, one address is sacrificed. *6* *7\************************************************************/8wire read_linearfeedback, write_linearfeedback;910assign read_linearfeedback = ! (read_addr[8] ^ read_addr[4]);11assign write_linearfeedback = ! (write_addr[8] ^ write_addr[4]);1213always @(posedge clock or posedge fifo_gsr)14if (fifo_gsr) read_addr <= 9'h0;15else if (read_allow)16 read_addr <= { read_addr[7], read_addr[6], read_addr[5],17 read_addr[4], read_addr[3], read_addr[2],18 read_addr[1], read_addr[0], read_linearfeedback };1920always @(posedge clock or posedge fifo_gsr)21if (fifo_gsr) write_addr <= 9'h022else if (write_allow)23 write_addr <= { write_addr[7], write_addr[6], write_addr[5],24 write_addr[4], write_addr[3], write_addr[2],25 write_addr[1], write_addr[0], write_linearfeedback };。

第二节线性反馈移位寄存器序列1基本概念和性质反馈移位寄存器, 特别线性反馈移位寄存器是许多密钥序列生成器的重要部件, 这一节引进线性反馈移位寄存器的模型, 并用数学(特别是代数)工具描述线性反馈移位寄存器.2设n是正整数, n级反馈移位寄存器的模型见下图a k+n−1 a k+n−2……… a k+1a k输出f (x n,…, x2, x1)反馈函数其中f(x1,…, x n)是一逻辑函数, 即f(x1,…, x n)∈2[x1,…, x n]这里2= {0, 1}表示二元域, n≥ 1.3当f(x1,…, x n)是线性函数时, 即f(x1, x2, … , x n) =c1x1+c2x2+ … +c n x n, c i∈2,称对应的反馈移位寄存器为线性反馈移位寄存器(简称LFSR), 所产生的序列称为线性(反馈)移位寄存器序列, 简记为LFSR序列.45此时所产生的序列适合关系式a n +k = 10n i −=∑c n −i a k +i , k = 0, 1, 2, ….并称序列a = (a 0, a 1,…)为n 级线性递归序列。

线性递归序列是LFSR 序列的数学描述, 但为书写简便, 以后在称谓上我们就用LFSR 序列.定义4.1 设a是LFSR序列, 称a的次数最小的特征多项式为a的极小多项式.定理4.1 设a是LFSR序列, 则a的极小多项式是唯一的.6进一步, 设m(x)是a的极小多项式, 则f(x)是a的一a(x)|f(x).个特征多项式当且仅当ma显然, LFSR序列的极小多项式刻画了生成该序列的最短LFSR,而定理4.1进一步说明, 这样的最短LFSR是唯一的.78设f (x )是F 2上n 次多项式, a =(a 0,a 1,a 2,…)是以f (x )为特征多项式的线性递归序列, 则a 由前n 比特a 0,a 1,…,a n −1唯一确定.例如: 设f (x )=x 3+x +1, a =(0,1,1,…)是以f (x )为特征多项式的线性递归序列, 则a =(0,1,1,1,0,0,1,0,1,1,1,…).定义4.2 对于F上序列a, 若存在非负整数k和正2整数T, 使得对任意i≥k, 都有a=a i, 则称a是准周i+T期序列, 最小这样的T称为a的周期, 记为per(a); 若k=0, 则称a是(严格)周期序列.注4.1 设per(a)=T, R是正整数, 若对任意i≥k, 有a i+R=a i, 则T|R.9显然, LFSR是一种有限状态机, 因此, 由LFSR生成的序列必然是准周期的. 下面的定理表明反之也是成立的, 即所有的准周期序列都可用LFSR来生成.定理4.2 a是准周期序列当且仅当a是LFSR序列.10利用序列的极小多项式可以判断序列是否严格周期.(x)是a的极小多项定理4.3 设a是LFSR序列, ma(0)≠0.式, 则a是周期序列当且仅当ma11进一步, 序列的周期由其极小多项式的周期完全确定.定理4.4 设a是周期序列, f(x)是它的极小多项式, 则per(a)=per(f(x)).12注4.2 若a是非严格周期序列, 定理4.4也成立. 由于非周期序列总可以转化成周期序列, 并且实际中使用的序列也都是周期序列, 故后面的讨论仅针对周期序列.13推论4.1 设f(x)是F上不可约多项式, 则以f(x)为2特征多项式的非零序列a有per(a)=per(f(x)).14最后, 我们给出LFSR序列的根表示.[x]是n次无重因子多项式,f(0)≠0, 定理4.5 设f(x)∈F2F2m是f(x)的分裂域, α1,α2,…,αn∈F2m是f(x)的全部根, 则,a1,…), 存在唯对任意以f(x)为特征多项式的序列a=(a一一组β,β2,…,βn∈F2m, 使得1a k=β1α1k+β2α2k+⋅⋅⋅+βnαn k, k≥0.15反之,设β,β2,…,βn∈F2m,若1a k=β1α1k+β2α2k+⋅⋅⋅+βnαn k∈F2, k≥0,,a1,…)以f(x)为特征多项式, 且f(x)是a的极则a=(a≠0, 1≤i≤n.小多项式当且仅当βi16m-序列注意到LFSR总是将0状态转化成0状态, 因此对于一个n级LFSR, 最多可输出周期为2n−1的周期序列.定义4.3 设a是n级LFSR序列, 若per(a)=2n−1, 则称a为n级最大周期序列, 简称为n级m-序列.17由定义显然有定理4.6 设a是n级LFSR序列, 则a是n级m-序列当且仅当a的极小多项式是n次本原多项式18定理4.7 若a是以n次本原多项式f(x)为极小多项式的m-序列, 则0, a, La,…, L2n−2a是以f(x)为特征多项式的序列全体.定理4.7说明, 由同一个本原多项式生成的两条m-序列彼此平移等价. 由定理4.7, 容易证明m-序列满足以下平移可加性.19定理4.8 设a是n级m-序列, 则对于非负整数s和t, 有L s a+L t a=L k a或0, 其中0≤k≤2n−2.注4.3 实际上, 定理4.8给出的平移可加性是m-序列的特有性质, 即对于周期为T的序列a, 非负整数s和t, 若L s a+L t a=L k a或0, 0≤k≤2n−2, 则a是m-序列.20m-序列是最重要的线性反馈移位寄存器序列, 不仅是因为m-序列的周期可达到最大, 而且因为m-序列的统计特性完全满足Golomb S.W.提出的三条随机性假设.2122(1) 元素分布设a 是周期为T 的序列, 将a 的一个周期依次排列在一个圆周上, 并且使得a 0和a T −1相邻, 我们称这样的圆为a 的周期圆.23引理4.1 设a 是n 级m-序列, 0 < k ≤ n , 则F 2上任意一个k 维向量(b 1,b 2,…,b k )在 a 的一个周期圆中出现的次数N (b 1,b 2,…,b k )为N (b 1,b 2,…,b k ) = 122, (,,,)(0,0,...,0)21,.n k k n k b b b −−⎧≠⎪⎨−⎪⎩…若，否则特别地, 分别取k=1和k=n, 有推论4.2 在n级m-序列的一个周期中1出现2n−1次, 0出现2n−1−1次.推论4.3 在n级m-序列的一个周期(圆)中每个(n维)非零状态出现且仅出现1次.2425(2) 游程分布设a 是周期序列, a 在一个周期圆中形如010...01全为 和 101...10全为的项分别叫做a 的0游程和1游程. 而0游程中连续0的个数及1游程中连续1的个数称为游程长度. m -序列具有非常理想的游程分布.定理4.9 设0<k≤n−2, 在n级m-序列的一个周期圆中, 长为k的0游程和1游程各出现2n−k−2次; 长度大于n的游程不出现; 长度为n的1游程和长度为n−1的0游程各出现一次; 长度为n的0游程和长度为n−1的1游程不出现; 游程总数为2n−1.2627(3) 自相关函数m-序列的自相关函数满足二值性, 即定理4.10 设a 是n 级m -序列, 则C a (t ) = 10(1)k k t T a a k +−+=−∑=1, 0(mod 21);21,0(mod 21).n n n t t ⎧−≠−⎪⎨−≡−⎪⎩若若.线性复杂度与Berlekamp-Massey算法线性复杂度的概念是针对LFSR结构提出的, 它衡量了用LFSR来生成给定序列的最小代价. 由于特征多项式完全刻画了生成序列的LFSR, 故自然有以下定义.28定义4.4 设a是周期序列, 称序列a的极小多项式的次数为a的线性复杂度, 记为LC(a).注4.4 对于周期序列a, 显然有LC(a)≤per(a)291969年提出的Berlekamp-Massey算法[14]解决了求序列极小LFSR的问题. 对于线性复杂度为L的序列a, 该算法在已知a的连续2L比特的前提下即可还原出整条序列, 计算时间复杂度仅为O(L2).30第四章序列密码因此, 好的伪随机序列必须具有高的线性复杂度. 对于上一小节介绍的n级m-序列, 其周期为2n−1, 是n 级LFSR能输出的最大周期序列, 但n级m-序列的极小多项式是n次本原多项式, 这意味着n级m-序列的线性复杂度等于n, 则在已知2n比特的条件下, 利用Berlekamp-Massey算法可还原出长为2n−1的原序列. 可见, n级m-序列绝不可单独作为密钥流序列使用.31。

移位寄存器寄存器在数字电路中，用来存放二进制数据或代码的电路称为寄存器。

寄存器是由具有存储功能的触发器组合起来构成的。

一个触发器可以存储一位二进制代码，存放N位二进制代码的寄存器，需用n个触发器来构成。

按功能可分为：基本寄存器和移位寄存器。

移位寄存器移位寄存器中的数据可以在移位脉冲作用下一次逐位右移或左移，数据既可以并行输入、并行输出，也可以串行输入、串行输出，还可以并行输入、串行输出，串行输入、并行输出，十分灵活，用途也很广。

目前常用的集成移位寄存器种类很多，如74164、74165、74166均为八位单向移位寄存器，74195为四位单向移存器，74194为四位双向移存器，74198为八位双向移存器。

反馈移位寄存器(一)、反馈移位寄存器的介绍1. 什么是反馈移位寄存器ai表示二值（0，1）存储单元，ai的个数n成为反馈移位寄存器的级。

在某一时刻，这些级构成该反馈移位寄存器的一个状态，共有2n个可能状态，每一个状态对应于域GF（2）上的一个n维向量，用（a1,a2,a3,…an）表示。

在主时钟周期的周期区间上，每一级存储器ai都将内容向下一级ai-1传递，并根据寄存器的当前状态f（a1,a2,a3,…an）作为an的下一时间内容，即从一个状态转移到下一个状态。

其中函数f（a1,a2,a3,…an）称为该反馈移位寄存器的反馈函数。

2. 线性反馈移位寄存器和非线性反馈移位寄存器如果反馈函数f（a1,a2,a3,…an）是a1,a2,a3,…an 的线性函数函数，则该反馈移位寄存器是线性反馈移位寄存器用LFSR表示，比如：f（a1,a2,a3,…an）=kna1⊕kn-1a2⊕….⊕k2an-1⊕k1an,其中系数ki∈{0，1}（i=1,2,3,…,n）。

相应的如果反馈函数f（a1,a2,a3,…an）是a1,a2,a3,…an 的非线性函数函数，则该反馈移位寄存器是非线性反馈移位寄存器。

(二)、反馈移位寄存器的性质1．移位寄存器序列反馈函数f（a1,a2,a3,…an）为n元布尔函数。

线性反馈移位寄存器原理
线性反馈移位寄存器是一种在数字电路中常用的元件，它能够将输入数据按照一定的顺序进行移位，并以一定的方式反馈部分数据到输入端。

它由多个触发器组成，每个触发器都能存储一个比特的数据。

实现线性反馈移位寄存器基本的原理是运用触发器的工作原理。

触发器是一种能够存储数据并在时钟信号的作用下改变输出状态的元件。

常见的触发器有D触发器和JK触发器等。

线性反馈移位寄存器的输入数据依次通过每个触发器，并从最后一个触发器的输出端输出。

同时，一部分触发器的输出被反馈到输入端，与输入数据进行异或运算后作为下一个触发器的输入。

这样，每次时钟信号到来时，输入数据随着触发器的工作状态向前移位，并根据反馈数据的异或结果产生新的输入数据。

通过合理选择反馈数据的位置和数值，线性反馈移位寄存器可以实现不同的功能。

例如，当反馈数据位于最后一个触发器和倒数第二个触发器之间，并且为1时，可以实现一个带有反馈的移位寄存器；当反馈数据为1并且位于最后一个触发器时，可以实现一个循环移位寄存器。

线性反馈移位寄存器广泛应用于数字通信、数据编码、序列生成等领域。

它具有简单、可靠、高效的特点，在现代的数字系统中扮演着重要的角色。

移位寄存器讲解1. 什么是移位寄存器？移位寄存器是一种基本的数字电路元件，用于将数据按位进行移位操作。

它由多个触发器（或者称为存储器元件）组成，可以在时钟的控制下，实现数据的输入、输出和移位操作。

2. 移位寄存器的分类根据移位方向和数据输入方式的不同，移位寄存器可以分为以下几种类型：2.1 串行输入的移位寄存器串行输入的移位寄存器每次只能输入一位数据，数据位依次串行输入到寄存器中。

这种类型的移位寄存器常用于串行数据通信和数据处理中。

2.2 并行输入的移位寄存器并行输入的移位寄存器可以同时输入多位数据，每位数据对应寄存器中的一个存储单元。

这种类型的移位寄存器常用于并行数据传输和存储器操作中。

2.3 串行输出的移位寄存器串行输出的移位寄存器每次只能输出一位数据，数据位依次串行输出到外部设备。

这种类型的移位寄存器常用于串行数据通信和数据处理中。

2.4 并行输出的移位寄存器并行输出的移位寄存器可以同时输出多位数据，每位数据对应寄存器中的一个存储单元。

这种类型的移位寄存器常用于并行数据传输和存储器操作中。

3. 移位寄存器的工作原理移位寄存器的工作原理可以分为两个方面：数据输入和数据移位。

3.1 数据输入对于串行输入的移位寄存器，数据从一个输入端口依次输入到寄存器中的各个存储单元。

每当时钟信号到来时，数据在存储单元之间进行移位操作，新的数据通过输入端口进入寄存器。

对于并行输入的移位寄存器，数据同时从多个输入端口输入到寄存器中的各个存储单元。

时钟信号到来时，数据保持不变，不进行移位操作。

3.2 数据移位无论是串行输入还是并行输入的移位寄存器，当时钟信号到来时，数据都会在存储单元之间进行移位操作。

移位的方向可以是向左移位（左移）或向右移位（右移），具体方向由控制信号决定。

移位寄存器的移位操作可以分为以下几种方式：3.2.1 逻辑右移逻辑右移是指将数据向右移位，最右边的位被丢弃，最左边的位用0填充。

3.2.2 逻辑左移逻辑左移是指将数据向左移位，最左边的位被丢弃，最右边的位用0填充。