最近，我反复碰到LFSR的概念，我发现它很有趣，因为它与不同领域的联系也很吸引人。我花了些力气才明白，最终的帮助是这个非常好的page，比起初的wikipedia entry更好。所以我想为像LFSR一样工作的程序编写一些小代码。更准确地说，这以某种方式表明了LFSR的工作原理。经过一些长时间的尝试（Python），这是我能想到的最干净的东西：
def lfsr(seed, taps):
sr, xor = seed, 0
while 1:
for t in taps:
xor += int(sr[t-1])
if xor%2 == 0.0:
xor = 0
else:
xor = 1
print xor
sr, xor = str(xor) + sr[:-1], 0
print sr
if sr == seed:
break
lfsr('11001001', (8,7,6,1)) #example
我将XOR函数的输出命名为“ xor”，不是很正确。但是，这仅是为了说明它如何遍历其可能的状态，实际上您已经注意到该寄存器由字符串表示。没有太多的逻辑一致性。
可以很容易地把它变成一个好看的玩具，你可以看几个小时（至少我可以看一下：-）
def lfsr(seed, taps):
import time
sr, xor = seed, 0
while 1:
for t in taps:
xor += int(sr[t-1])
if xor%2 == 0.0:
xor = 0
else:
xor = 1
print xor
print
time.sleep(0.75)
sr, xor = str(xor) + sr[:-1], 0
print sr
print
time.sleep(0.75)
然后让我震惊的是，这在编写软件时有什么用？我听说它可以生成随机数；是真的吗怎么样？因此，如果有人可以：
而且，由于关于这部分逻辑和数字电路的教学方法不多，如果这可以成为一个笨拙的人（像我一样）更好地理解此thing的地方，那还是很好的，或者更好地理解它是什么以及在编写软件时它如何有用。应该使它成为社区Wiki吗？
就是说，如果有人想打高尔夫球……不客气。
实际上，基于LFSR的算法非常普遍。 CRC实际上直接基于LFSR。当然，在计算机科学课程中，人们谈论的是多项式，而当他们谈论输入值应如何与累加值进行异或运算时，在电子工程学中，我们谈论的是抽头。它们是相同的，只是术语不同。
CRC32是非常常见的一种。它用于检测以太网帧中的错误。这意味着当我发布此答案时，我的电脑使用了基于LFSR的算法来生成IP数据包的哈希值，以便我的路由器可以验证其传输的内容是否未损坏。
Zip和Gzip文件是另一个示例。两者都使用CRC进行错误检测。 Zip使用CRC32，Gzip使用CRC16和CRC32。
CRC基本上是哈希函数。它足以使互联网正常工作。这意味着LFSR是相当不错的哈希函数。我不确定您是否知道这一点，但是一般来讲，好的哈希函数被认为是好的随机数生成器。但是，LFSR的问题在于选择正确的抽头（多项式）对于哈希/随机数的质量非常重要。
您的代码通常是玩具代码，因为它对一串一和零进行运算。在现实世界中，LFSR处理字节中的位。推入LFSR的每个字节都会更改寄存器的累加值。该值实际上是您通过寄存器推送的所有字节的校验和。使用该值作为随机数的两种常见方式是使用计数器，然后将数字序列推入寄存器，从而将线性序列1,2,3,4转换为某种哈希序列，例如15306、22、5587， 994，或将当前值反馈到寄存器中，以看似随机的顺序生成新数字。
应注意，由于必须一次处理位，因此使用位摆弄的LFSR天真地执行此操作相当慢。因此，人们想出了使用预先计算的表来一次做到八位甚至一次达到32位的方法。这就是为什么您几乎从来没有在野外看到LFSR代码的原因。在大多数生产代码中，它会伪装成其他形式。
但是有时候，普通的位纠结LFSR可能会派上用场。我曾经为PIC单片机编写了一个Modbus驱动程序，该协议使用了CRC16。预先计算的表需要256个字节的内存，而我的CPU只有68个字节（I'm not kidding）。所以我不得不使用LFSR。
因为我一直在寻找Python中的LFSR实现，所以我偶然发现了这个主题。但是我发现以下内容根据我的需求更加准确：
def lfsr(seed, mask):
result = seed
nbits = mask.bit_length()-1
while True:
result = (result << 1)
xor = result >> nbits
if xor != 0:
result ^= mask
yield xor, result
上述LFSR生成器基于GF（2 k）模数计算（GF = Galois Field）。刚刚完成了代数课程，我将以数学方式对此进行解释。
让我们以GF（2 4）开始，它等于{a 4 x 4 + a 3 x 3 + | a 2 x 2 + a 1 x 1 + a 0 x 0 | a 0，a 1，...，a 4∈Z 2}（为澄清起见，Z n = {0,1 ,. 。，n-1}，因此Z 2 = {0,1}，即一位）。这意味着这是第四级所有多项式的集合，其中所有因子都存在或不存在，但是没有这些因子的倍数（例如，不存在2x [k）。 x 3，x 4 + x 3，1和x 4 + x 3 + x 2 + x +1均为示例该组成员的数量。
[我们将此设定模数设为四次多项式（即P（x）∈GF（24
）），例如P（x）＝ x 4 + x 1 + x 0。在组上的该模运算也表示为GF（2 [4]）/ P（x）。供您参考，P（x）描述了LFSR中的“抽头”。我们还采用3或更低阶的随机多项式（这样它就不受我们的模数的影响，否则我们也可以直接对其执行模数运算），例如A 0（x）= x0。现在，通过将其乘以x来计算每个后续A [i
（x）：A i（x）= A i-1（x）* x mod P（x）。 由于我们处于有限的领域，所以模运算可能会起作用，但仅当所得的A i（x）至少具有因数x 4时（我们在P（ X））。请注意，由于我们正在处理Z2
中的数字，因此执行模运算本身仅是通过将P（x）中的两个值相加来确定每个a i变为0还是1。和A i（x）一起（即0 + 0 = 0、0 + 1 = 1、1 + 1 = 0或“异或”这两个）。每个多项式都可以写为一组位，例如x 4 + x 1 + x0
〜10011。A 0（x）可以是被视为种子。 “ times x”操作可以看作是左移操作。模运算可以看作是位掩码操作，掩码是我们的P（x）。因此，[上述算法生成有效的四位LFSR模式（的无限流）。例如，对于我们定义的A 0（x）（x 0）和P（x）（x 4 + x 1
+ x 0），我们可以在GF（2 4）中定义以下第一个产生的结果（请注意，直到第一轮结束才产生A 0-数学家通常从“ 1”开始计数）： i Ai(x) 'x⁴' bit pattern
0 0x³ + 0x² + 0x¹ + 1x⁰ 0 0001 (not yielded)
1 0x³ + 0x² + 1x¹ + 0x⁰ 0 0010
2 0x³ + 1x² + 0x¹ + 0x⁰ 0 0100
3 1x³ + 0x² + 0x¹ + 0x⁰ 0 1000
4 0x³ + 0x² + 1x¹ + 1x⁰ 1 0011 (first time we 'overflow')
5 0x³ + 1x² + 1x¹ + 0x⁰ 0 0110
6 1x³ + 1x² + 0x¹ + 0x⁰ 0 1100
7 1x³ + 0x² + 1x¹ + 1x⁰ 1 1011
8 0x³ + 1x² + 0x¹ + 1x⁰ 1 0101
9 1x³ + 0x² + 1x¹ + 0x⁰ 0 1010
10 0x³ + 1x² + 1x¹ + 1x⁰ 1 0111
11 1x³ + 1x² + 1x¹ + 0x⁰ 0 1110
12 1x³ + 1x² + 1x¹ + 1x⁰ 1 1111
13 1x³ + 1x² + 0x¹ + 1x⁰ 1 1101
14 1x³ + 0x² + 0x¹ + 1x⁰ 1 1001
15 0x³ + 0x² + 0x¹ + 1x⁰ 1 0001 (same as i=0)
请注意，您的掩码必须在第四个位置包含'1'，以确保LFSR生成四位结果。还要注意，在第0个位置必须存在一个“ 1”，以确保您的位流不会以0000位模式结束，否则最后一位将变为未使用状态（如果所有位都向左移动，则一班后在第0个位置也以零结尾）。并非所有P（x）都必须是GF（2 k）的生成器（即，并非所有k位掩码都生成所有2 k-1-1个数字）。例如，x
4
+ x3
+ x 2 + x 1 + x 0分别生成3组，每组5个不同的多项式，或“ 3个循环周期5”：0001,0010,0100,1000,1111; 0011,0110,1100,0111,1110;和0101,1010,1011,1001,1101。请注意，永远不会生成0000，也不能生成任何其他数字。通常，LFSR的输出是'移出'的位，如果执行模数运算，则为'1'，否则则为'0'。周期为2 k-1] -1的LFSR，也称为伪噪声或PN-LFSR，遵循Golomb的随机性假设，该假设表明此输出位是随机的“足够”。 因此，这些位的序列已在加密中使用，例如在A5 / 1和A5 / 2移动加密标准或E0蓝牙标准中。但是，它们并不像人们希望的那样安全：Berlekamp-Massey algorithm可用于对LFSR的特征多项式（P（x））进行逆向工程。因此，强加密标准使用Non-linear FSR或类似的非线性函数。与此相关的主题是AES中使用的S-Boxes。请注意，我已经使用了int.bit_length() operation。直到Python 2.7才实现。如果只想使用有限位模式，则可以检查种子是否等于结果，然后中断循环。您可以在for循环中使用我的LFSR方法（例如int.bit_length()），也可以对方法的结果重复调用for xor, pattern in lfsr(0b001,0b10011)操作，每次都返回一个新的.next()对。
LFSR有许多应用。其中之一就是产生噪声，例如SN76489及其变体（用于Master System，Game Gear，MegaDrive，NeoGeo Pocket等）使用LFSR产生白/周期性噪声。 SN76489的LFSR (xor, result)的描述非常好。
yield进行比较也是不必要且令人困惑的。如果我们假设seed是一个int列表，而不是一个字符串（或者如果不是，则将其转换），那么下面的代码应该可以做些您想要的事情，并且更加优雅：
def lfsr(seed, taps) :
while True:
nxt = sum([ seed[x] for x in taps]) % 2
yield nxt
seed = ([nxt] + seed)[:max(taps)+1]
for x in lfsr([1,0,1,1,1,0,1,0,0],[1,5,6]) : print x