线性反馈转移寄存器？

Question

最近，我反复碰到LFSR的概念，因为它与不同的领域有联系，并且本身也很有趣，因此我发现非常有趣。我花了一些努力才能理解，最后的帮助是这真的很好 页, ，比（起初）隐秘要好得多 Wikipedia条目. 。因此，我想为像LFSR一样工作的程序编写一些小型代码。更确切地说，以某种方式展示了LFSR的工作原理。这是我经过一些Lenghtier尝试（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。当然，在计算机科学课程中，人们谈论多项式时，他们谈论输入值应该如何与累计值相关，而在Electorners工程中，我们谈论的是TAPS。它们只是不同的术语。

CRC32是非常普遍的。它用于检测以太网帧中的错误。这意味着，当我发布此答案时，我的PC使用基于LFSR的算法来生成IP数据包的哈希，以便我的路由器可以验证其传输未损坏的内容。

zip和gzip文件是另一个示例。两者都使用CRC进行错误检测。 ZIP使用CRC32，GZIP同时使用CRC16和CRC32。

CRC基本上是哈希功能。这足以使互联网工作。这意味着LFSR是相当不错的哈希功能。我不确定您是否知道这一点，但总的来说，好哈希功能被认为是良好的随机数生成器。但是LFSR的目的是选择正确的TAP（多项式）对于哈希/随机数的质量非常重要。

您的代码通常是玩具代码，因为它在一串和零上运行。在现实世界中，lfsr在字节中工作。您按LFSR推动的每个字节都会更改寄存器的累积值。该值实际上是您通过寄存器推动的所有字节的校验和校验和。使用该值作为随机数的两种常见方法是使用计数器并通过寄存器推动数字序列，从而将线性序列1,2,3,4转换为某些哈希序列，例如15306,22,5587， 994，或将当前值馈送到寄存器中以以看似随机的序列生成一个新数字。

应当指出的是，由于您必须一次处理位，因此使用fitddling LFSR天真地进行此操作非常慢。因此，人们提出了使用预估算的表一次进行八个甚至32位的方法。这就是为什么您几乎从未在野外看到LFSR代码的原因。在大多数生产代码中，它都伪装成其他东西。

但是有时候，略带扭转的LFSR可能会派上用场。我曾经写过 modbus PIC Micro的驱动程序，该协议使用CRC16。预计表需要256个字节的内存，而我的CPU只有68个字节（我不是在开玩笑）。所以我不得不使用LFSR。

Answer 2

由于我正在寻找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 = 加洛伊斯球场）。刚刚完成代数课程后，我将以数学方式解释这一点。

让我们从例如GF开始（2⁴），等于{₄X⁴ + a₃X³ + a₂X² + a₁X¹ + a₀X⁰ |一种₀, ， 一种₁, ， ...， 一种₄ ∈Z₂}（要澄清，Z_n = {0,1，...，n-1}，因此z₂ = {0,1}，即一点点）。这意味着这是第四级的所有多项式的集合，所有因素是否存在，但没有这些因素的倍数（例如，没有2x^k）。 X³, ， X⁴ + x³, ，1和x⁴ + x³ + x² + x + 1都是该组成员的示例。

我们将此集模量视为四度的多项式（即，p（x）∈Gf（2⁴），例如p（x）= x⁴+x¹+x⁰. 。该组上的模量操作也表示为GF（2⁴） / p（x）。对于您的参考，p（x）描述了LFSR中的“水龙头”。

我们还采用3度或更低度的随机多项式（因此它不受模量的影响，否则我们可以直接在其上直接执行模量操作），例如A₀（x）= x⁰. 。现在每个后续的_一世（x）通过将其乘以x：a来计算_一世（x）= a_I-1（x） * x mod p（x）。

由于我们处于有限的领域，因此模量操作可能会产生效果，但只有当结果a_一世（x）至少有一个因子x⁴ （我们在p（x）中的最高因素）。请注意，由于我们正在使用Z中的数字₂, ，执行模量操作本身无非是确定每个a是否_一世 通过添加P（X）和A的两个值，成为0或1_一世（x）在一起（即0+0 = 0，0+1 = 1，1+1 = 0，或“ Xoring”这两个）。

每个多项式都可以写成一组位，例如x⁴+x¹+x⁰ 〜10011。₀（x）可以看作是种子。 “ Times X”操作可以看作是左侧操作。模量操作可以看作是一些掩盖操作，蒙版为我们的P（x）。

因此，上面描述的算法会生成（无限流）有效的四位LFSR模式。例如，对于我们的定义₀（X） （X⁰) 和p（x） （X⁴+x¹+x⁰), ，我们可以定义以下第一次产生的结果（2⁴）（请注意₀ 直到第一轮结束时才能产生 - 数学家通常开始计数为“ 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生成四位数结果。另请注意，必须在零位置存在一个“ 1”，以确保您的bitstream不会以0000位模式最终出现，或者最终的位将不使用（如果所有位都向左移动，您将最终在一次班次后的0位位置为零。

并非所有p（x）一定是GF的发电机（2^k）（即，不是所有k位的口罩都会生成全部2个^K-1-1个数字）。例如，x⁴ + x³ + x² + x¹ + x⁰ 每组3组，分别为5个不同的多元素，或“ 3个周期5”：0001,0010,0100,1000,1111； 0011,0110,1100,0111,1110;和0101,1010111,1001,1101。请注意，0000永远无法生成，也不能生成任何其他数字。

通常，LFSR的输出是“移动”的位，如果执行模量操作，则是“ 1”，而当不进行模量操作时，则是“ 0”。 LFSR的时间为2^K-1-1，也称为伪噪声或pn-lfsr，遵守Golomb的随机性假设，这说出该输出位是随机的“足够”。

因此，这些位的序列在密码学中使用，例如在A5/1和A5/2移动加密标准或E0蓝牙标准中。但是，它们并不像人想要的那样安全： Berlekamp-Massey算法 可用于逆转LFSR的特征多项式（p（x））。因此，强大的加密标准使用 非线性FSR的或类似的非线性函数。与此相关的话题是 S-box 用于AES。

---

请注意，我已经使用了 int.bit_length() 手术. 。直到Python 2.7才实施。
如果您只喜欢有限的位图案，则可以检查种子是否等于结果，然后打破循环。
您可以在循环中使用我的LFSR方法（例如 for xor, pattern in lfsr(0b001,0b10011)），也可以反复致电 .next() 在方法的结果上操作，返回新的 (xor, result)- 每次。

Answer 3

LFSR有很多应用。其中之一是产生噪音，例如SN76489和变体（用于主系统，游戏装备，Megadrive，Neogeo Pocket，...）使用LFSR来产生白色/周期性噪声。 SN76489的LFSR有一个很好的描述 在此页面中.

Answer 4

为了使其真正优雅和pythonic，请尝试创建一个发电机， yield- 来自LFSR的连续值。另外，与浮点相比 0.0 是不必要和令人困惑的。

LFSR只是在计算机中创建伪随机数的众多方法之一。伪随机，因为没有数字 真的 随机 - 您可以通过从种子（初始值）开始并进行相同的数学操作来轻松重复它们。

Answer 5

以下是使用整数和二进制运算符而不是字符串的代码上的变体。它还按照某人的建议使用产量。

def lfsr2(seed, taps):
    sr = seed
    nbits = 8
    while 1:
        xor = 1
        for t in taps:
            if (sr & (1<<(t-1))) != 0:
                xor ^= 1
        sr = (xor << nbits-1) + (sr >> 1)
        yield xor, sr
        if sr == seed:
            break

nbits = 8
for xor, sr in lfsr2(0b11001001, (8,7,6,1)):
    print xor, bin(2**nbits+sr)[3:]

Answer 6

如果我们假设种子是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

Answer 7

list_init=[1,0,1,1]
list_coeff=[1,1,0,0]
out=[]
for i in range(15):
    list_init.append(sum([list_init[i]*list_coeff[i] for i in range(len(list_init))])%2)
    out.append(list_init.pop(0))
print(out)

#https://www.rocq.inria.fr/secret/Anne.Canteaut/encyclopedia.pdf