python - 线性反馈移位寄存器？

Question

最近，我反复碰到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)

然后让我震惊的是，这在编写软件中有什么用？我听说它可以生成随机数；是真的吗如何？
因此，如果有人可以:

解释如何在软件开发中使用这种设备

提供了一些代码，以支持上面的要点，或者像我的一样，以任何语言

展示了执行该操作的不同方法。

另外，由于关于这部分逻辑和数字电路的教学方法不多，因此如果这可以让菜鸟(像我一样)更好地理解或更好地理解它，那么这将是一个很好的选择。是以及在编写软件时它如何有用。应该使它成为社区Wiki吗？
就是说，如果有人想打高尔夫球……不客气。

Answer 1

实际上，基于LFSR的算法非常普遍。 CRC实际上直接基于LFSR。当然，在计算机科学类(class)中，人们谈论的是多项式，而当他们谈论输入值应如何与累加值进行异或运算时，在电子工程学中，我们所讨论的却是抽头。它们是相同的，只是术语不同。

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驱动程序，该协议(protocol)使用了CRC16。预先计算的表需要256个字节的内存，而我的CPU只有68个字节(I'm not kidding)。因此，我不得不使用LFSR。