非线性反馈移位寄存器_crc数字逻辑_线性反馈移位寄存器与梅森旋转算法

  本文关键词：线性移位寄存器，由笔耕文化传播整理发布。

今天主要是来研究梅森旋转算法，它是用来产生伪随机数的，实际上产生伪随机数的方法有很多种，比如线性同余法，

平方取中法等等。但是这些方法产生的随机数质量往往不是很高，而今天介绍的梅森旋转算法可以产生高质量的伪随

机数，并且效率高效，弥补了传统伪随机数生成器的不足。梅森旋转算法的最长周期取自一个梅森素数，

由此命名为梅森旋转算法。常见的两种为基于32位的MT19937-32和基于64位的MT19937-64。

由于梅森旋转算法是利用线性反馈移位寄存器（LFSR）产生随机数的，所以我们先来认识线性反馈移位寄存器。

首先，移位寄存器包括两个部分

    （1）级，每一级包含一个比特，比如11010110是一个8级的移位寄存器产生的

    （2）反馈函数，线性反馈移位寄存器的反馈函数是线性的，非线性反馈移位寄存器的反馈函数是非线性的

一个，当然这个最大周期跟反馈函数有很大关系，线性反馈函数实

际上就是这个级的移位寄存器选取“某些位”进行异或后得到的结果，这里的“某些位”的选取很重要，得到线性反馈

函数之后，把这个移位寄存器的每次向右移动一位，把最右端的作为输出，把“某些位”的异或结果作为输入放到最左

端的那位，这样所有的输出对应一个序列，这个序列叫做M序列，是最长线性移位寄存器序列的简称。

上面“某些位”的选取问题还没有解决，那么应该选取哪些位来进行异或才能保证最长周期为，这是一个很重要

的问题。选取的“某些位”构成的序列叫做抽头序列，理论表明，要使LFSR得到最长的周期，这个抽头序列构成的多项

式加1必须是一个本原多项式，也就是说这个多项式不可约，比如。

下面以一个4位的线性反馈移位寄存器为例说明它的工作原理。

如果的值分别是1 0 0 0，反馈函数选取，那么得到如下序列

可以看出周长为15。在这一个周期里面涵盖了开区间内的所有整数，并且都是没有固定顺序出现的，有

很好的随机性。

之前说过，梅森旋转算法的周期为，那么说明它是一个19937级的线性反馈移位寄存器，实际上基于32位

的MT19937-32只需要用到32位，那么为什么要选择周长为的算法呢？ 那是因为这样做随机性很好。

梅森旋转算法是基于线性反馈移位寄存器的一直进行移位旋转，，周期为一个梅森素数，果然是名副其实。

代码：

  本文关键词：线性移位寄存器，由笔耕文化传播整理发布。