lfsr(线性反馈移位寄存器)提供了一种在微控制器上快速生成非顺序数字列表的简单方法。生成伪随机数只需要右移操作和异或操作。图1显示了一个5位LFSR。图2显示了用C语言实现的LFSR，图3显示了用8051汇编实现的16位LFSR。

lfsr和多项式

LFSR完全由其多项式指定。例如，每个项都存在的6(th)次多项式表示为方程x(6) + x(5) + x(4) + x(3) + x(2) + x + 1。这种大小的多项式有2((6 - 1))= 32种不同的可能。就像数字一样，有些多项式是素数或原数。我们对原始多项式很感兴趣因为它们会给我们移动时最长的周期。一个n次的最大长度多项式会有2(n) - 1种不同的状态。每次转换后都会转换到一个新的状态。因此，一个6次多项式将有31种不同的状态。1到31之间的每个数字在重复之前都会出现在移位寄存器中。在原始的6(th)次多项式的情况下，只有6个。表1列出了所有原始的6(th)次多项式和它们各自的多项式掩码。多项式掩码是通过取多项式的二进制表示并截断最右边的位来创建的。在实现多项式的代码中使用掩码。它需要n位来实现n(th)次多项式的多项式掩码。

每个原始多项式都有奇数个项，这意味着每个原始多项式的掩码都有偶数个1位。每个原始多项式也定义了第二个原始多项式，它的对偶。对偶可以通过从多项式的次数中减去每一项的指数来找到。例如，给定6(6)次多项式x(6) + x + 1，其对偶是x(6-6) + x(6-1) + x(6-0)，等于x(6) + x(5) + 1。在表1中，多项式1与2、3与4、5与6互为对偶。

表2列出了每种不同大小的多项式的周期以及每种大小存在的原语多项式的数量。表3为每个不同大小的多项式列出了一个多项式掩码。它还显示了当LFSR初始化为1时，连续移位后LFSR将保持的前四个值。这个表应该有助于确保实现是正确的。

LFSR的结构

LFSR的值永远不会为零，因为LFSR为零的每次移位都会使其为零。LFSR必须初始化，即播种到一个非零值。当LFSR保持1并且移位一次时，它的值将始终是多项式掩码的值。当寄存器除最高有效位外全为零时，接下来的几次移位将显示高位移位到低位，并填充零。例如，任何具有基本多项式的8位移位寄存器最终将生成序列0x80、0x40、0x20、0x10、8、4、2、1，然后是多项式掩码。

用LFSR生成伪随机数

一般来说，基本的LFSR不能产生很好的随机数。一个更好的数字序列可以通过选择一个更大的LFSR和使用随机数的低位来改进。例如，如果你有一个10位的LFSR并且想要一个8位的数字，你可以取寄存器的底部8位作为你的数字。使用这种方法，在LFSR完成一个周期并重复之前，您将看到每个8位数字四次，零三次。这解决了得到零的问题，但数字仍然没有表现出很好的统计特性。相反，您可以将LFSR的子集用于随机数，以增加数字的排列并改进LFSR输出的随机特性。

在得到随机数之前多次移动LFSR也可以改善其统计特性。将LFSR移动其周期的一个因子将使总周期长度减少该因子。表2列出了各时期的因素。

相对较短的lfsr周期可以通过将两个或多个不同大小的lfsr的值叠加在一起来解决。这些xor lfsr的新周期将是周期的LCM(最小公倍数)。例如，一个基本的4位LFSR和一个基本的6位LFSR的LCM是LCM(15,63)，即315。当以这种方式加入lfsr时，请确保只使用lfsr的最小位数;使用更少的量是更好的做法。对于4位和6位的lfsr，不应该使用超过底部4位。在图2中，底部16位来自32位和31位lfsr。注意，XORing两个相同大小的lfsr不会增加周期。

lfsr的不可预测性可以通过在反馈项上增加一点“熵”来增加。在这样做的时候应该小心一些——随着熵位的增加，LFSR有很小的可能会全部归零。如果周期性地增加熵，LFSR的归零会自我修正。这种用反馈项XORing位的方法就是计算循环冗余检查(crc)的方法。

多项式不是生来相等的。有些多项式肯定会比其他的好。表2列出了位大小为31位的可用基本多项式的数量。尝试不同的多项式，直到你找到一个满足你需要的。表3给出的口罩是随机选择的。

用于测试随机数生成器的所有基本统计测试都可以在Donald Knuths, the Art of Computer Programming, Volume 2, Section 3.3中找到。可以使用NIST的统计测试套件进行更广泛的测试。NIST也有一些描述随机数测试的出版物，并参考了其他测试软件。