孩子都能学会的FPGA：第二十一课——用线性反馈移位寄存器实现伪随机序列

（原创声明：该文是作者的原创，面向对象是FPGA入门者，后续会有进阶的高级教程。宗旨是让每个想做FPGA的人轻松入门，作者不光让大家知其然，还要让大家知其所以然！每个工程作者都搭建了全自动化的仿真环境，只需要双击top_tb.bat文件就可以完成整个的仿真（前提是安装了modelsim），降低了初学者的门槛。如需整个工程请留言（WX：Blue23Light），不收任何费用，但是仅供参考，不建议大家获得资料后从事一些商业活动！）

前面的仿真一直说到仿真的数据用到的是随机数，verilog仿真的时候有提供产生随机数的命令random，很多读者可能会问，既然FPGA这么强大，用FPGA不能产生随机数吗？这个当然是可以的，用FPGA产生真正的随机数可能会相对麻烦一些，但是产生伪随机数还是非常简单的。

FPGA产生伪随机序列可以用线性反馈移位寄存器来实现，线性反馈移位寄存器（linear feedback shift register, LFSR）是指给定前一状态的输出，将该输出的线性函数再用作输入的移位寄存器。异或运算是最常见的单比特线性函数：对寄存器的某些位进行异或操作后作为输入，再对寄存器中的各比特进行整体移位。

寄存器的初始值叫做“种子”，因为线性反馈移位寄存器的运算是确定性的，所以，由寄存器所生成的数据流完全决定于寄存器当时或者之前的状态。而且，由于寄存器的状态是有限的，它最终肯定会是一个重复的循环。然而，通过本原多项式， 线性反馈移位寄存器可以生成看起来是随机的且循环周期非常长的序列。移位寄存器结构简单，运行速度快，实用的密钥流产生器大多基于移位寄存器，移位寄存器理论也成了现代流密码体制的基础。

线性反馈移位寄存器的应用包括生成伪随机数，伪随机噪声序列，快速数字计数器，还有扰频器。线性反馈移位寄存器在硬件和软件方面的应用都非常得普遍。循环冗余校验中用于快速校验传输错误的数学原理，就与线性反馈移位寄存器密切相关。

上面说到了本原多项式，可以理解成我们常说额特征多项式，如下所示，gm为多项式的系数，对于二进制，多项式系数只能为1或0。

LFSR结构如下图所示，每一位的值等于前一位的移位值与最后一位反馈值取异或，即Q(k)=Q(k-1)^(gk*Q(n))。

由LFSR的结构图可以看出LFSR的FPGA实现非常简单，我们来实现X^7+X^6+X^5+X^4+1这个本原多项式。整个代码如下所示，非常的简单。

在仿真里面设置初始值是7，双击sim目录下的top_tb.bat，modelsim的仿真结果如下所示，rand_out取无符号的整数，基本上是符合随机数分布的。

如果想让数据的随机性更强一些，可以不定时的改变移位寄存器的初始值，如下所示，定义了一个寄存器cnt用于减法计数，每计数到0就取当前的rand_out重新组合后进行计数，进一步增加了cnt随机性。

modelsim的仿真如下所示。

读者也可以自己设计，多加入一些随机的因素，让数据更加的随机，同时也可以试试不同的本原多项式，或者取不同长度的移位寄存器，看看生成随机数的效果。