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

Question

最近我反复碰到 LFSR 的概念，我觉得这很有趣，因为它与不同的领域有联系，而且本身也很吸引人。我花了一些力气才明白，最后的帮助是这个非常好的页面，比（起初）神秘的维基百科条目要好得多。所以我想为一个像 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)

然后我就想到了，这在写软件有什么用？听说可以生成随机数；是真的吗？如何？所以，如果有人可以：

• 解释如何在软件开发中使用这种设备
• 提出一些代码，以支持上述观点，或者就像我的一样，以任何语言展示不同的方法

此外，由于没有太多关于这块逻辑和数字电路的教学内容，如果这可以成为一个让新手（像我一样）更好地理解这个东西的地方，或者更好地理解它是什么，那就太好了是以及在编写软件时它如何有用。应该让它成为一个社区维基吗？

也就是说，如果有人喜欢打高尔夫球……不客气。

Answer 1

由于我正在寻找 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 ⁴ ) 为例，它等于 {a ₄ x ⁴ + a ₃ x ³ + a ₂ x ² + a ₁ x ¹ + a ₀ x ⁰ | a ₀ , a ₁ , ..., a ₄ ∈ 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 ⁰。现在每个后续的 A _i (x) 都是通过将其乘以 x 来计算的：A _i (x) = A _i-1 (x) * x mod P(x)。

由于我们处于有限的领域，模运算可能会产生影响，但只有当得到的 A _i (x) 至少具有因子 x ⁴（我们在 P(x) 中的最高因子）时。请注意，由于我们正在处理 Z ₂中的数字，因此执行取模运算本身只不过是通过将 P(x) 和 A _i (x)中的两个值相加来确定每个 a _i是 0 还是 1 （即，0+0=0、0+1=1、1+1=0，或“异或”这两个）。

每个多项式都可以写成一组位，例如 x ⁴ +x ¹ +x ⁰ ~ 10011。A ₀ (x) 可以看作是种子。'times x' 操作可以看作是左移操作。模运算可以看作是位掩码运算，掩码就是我们的 P(x)。

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

并非所有 P(x) 都必然是 GF(2 ^k ) 的生成器（即，并非所有 k 位掩码都生成所有 2 ^k-1 -1 个数字）。例如，x ⁴ + x ³ + x ² + x ¹ + x ⁰生成 3 组，每组 5 个不同的多项式，或“周期 5 的 3 个周期”：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 算法可用于对 LFSR 的特征多项式（P(x)）进行逆向工程。因此，强大的加密标准使用非线性 FSR或类似的非线性函数。与此相关的主题是AES 中使用的S-Box 。

---

请注意，我已经使用了int.bit_length()操作。这直到 Python 2.7 才实现。
如果您只想要一个有限位模式，您可以检查种子是否等于结果，然后打破循环。
您可以在 for 循环（例如）中使用我的 LFSR 方法，for xor, pattern in lfsr(0b001,0b10011)或者您可以重复调用.next()方法结果的操作，每次都返回一个新(xor, result)的 -pair。

Answer 2

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

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

Zip 和 Gzip 文件是另一个示例。两者都使用 CRC 进行错误检测。Zip 使用 CRC32，而 Gzip 使用 CRC16 和 CRC32。

CRC 基本上是散列函数。它足以让互联网正常工作。这意味着 LFSR 是相当好的散列函数。我不确定你是否知道这一点，但一般来说，好的散列函数被认为是好的随机数生成器。但是 LFSR 的问题是，选择正确的抽头（多项式）对于散列/随机数的质量非常重要。

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

应该注意的是，天真地使用位摆弄 LFSR 执行此操作非常慢，因为您必须一次处理位。因此，人们想出了使用预先计算好的表格来一次处理 8 位甚至 32 位的方法。这就是为什么您几乎从未在野外看到 LFSR 代码的原因。在大多数生产代码中，它伪装成其他东西。

但有时一个简单的 LFSR 可以派上用场。我曾经为 PIC micro 编写了一个Modbus驱动程序，该协议使用 CRC16。预先计算好的表需要 256 字节的内存，而我的 CPU 只有 68 字节（我不是在开玩笑）。所以我不得不使用LFSR。

Answer 3

LFSR 有很多应用。其中之一是产生噪音，例如 SN76489 和变体（用于 Master System、Game Gear、MegaDrive、NeoGeo Pocket 等）使用 LFSR 来产生白/周期性噪音。此页面中对 SN76489 的 LFSR 有非常好的描述。

Answer 4

这是我的 python 库之一 -用于实现 LFSR的pylfsr 。我试图让它高效地处理任何长度的 LFSR 来生成二进制序列。

import numpy as np
from pylfsr import LFSR

#for 5-bit LFSR with polynomial  x^5 + x^4 +  x^3 + x^2 +1
seed = [0,0,0,1,0]
fpoly = [5,4,3,2]
L = LFSR(fpoly=fpoly,initstate =seed)
seq = L.runKCycle(10)

您也可以在步骤中显示所有信息，

state = [1,1,1]
fpoly = [3,2]
L = LFSR(initstate=state,fpoly=fpoly,counter_start_zero=False)
print('count \t state \t\toutbit \t seq')
print('-'*50)
for _ in range(15):
    print(L.count,L.state,'',L.outbit,L.seq,sep='\t')
    L.next()
print('-'*50)
print('Output: ',L.seq)

输出

count    state      outbit   seq
--------------------------------------------------
1   [1 1 1]     1   [1]
2   [0 1 1]     1   [1 1]
3   [0 0 1]     1   [1 1 1]
4   [1 0 0]     0   [1 1 1 0]
5   [0 1 0]     0   [1 1 1 0 0]
6   [1 0 1]     1   [1 1 1 0 0 1]
7   [1 1 0]     0   [1 1 1 0 0 1 0]
8   [1 1 1]     1   [1 1 1 0 0 1 0 1]
9   [0 1 1]     1   [1 1 1 0 0 1 0 1 1]
10  [0 0 1]     1   [1 1 1 0 0 1 0 1 1 1]
11  [1 0 0]     0   [1 1 1 0 0 1 0 1 1 1 0]
12  [0 1 0]     0   [1 1 1 0 0 1 0 1 1 1 0 0]
13  [1 0 1]     1   [1 1 1 0 0 1 0 1 1 1 0 0 1]
14  [1 1 0]     0   [1 1 1 0 0 1 0 1 1 1 0 0 1 0]
--------------------------------------------------
Output:  [1 1 1 0 0 1 0 1 1 1 0 0 1 0 1]

也可以像这样可视化

在此处查看文档

Answer 5

为了使它真正优雅和 Pythonic，尝试创建一个生成器，yield从 LFSR 中获取连续的值。此外，与浮点数进行比较0.0是不必要且令人困惑的。

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

Answer 6

下面是使用整数和二进制运算符而不是字符串的代码变体。它还像有人建议的那样使用产量。

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 7

如果我们假设种子是一个整数列表而不是一个字符串（或者如果不是，则转换它），那么下面应该更优雅地做你想要的：

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 8

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

Answer 9

这是一段代码，您可以在其中选择种子、位数和所需的抽头：

from functools import reduce 

def lfsr(seed=1, bits=8, taps=[8, 6, 5, 4]):
    """
            1 2 3 4 5 6 7 8 (bits == 8)
           ┌─┬─┬─┬─┬─┬─┬─┬─┐
        ┌─→│0│1│0│1│0│0│1│1├─→
        │  └─┴─┴─┴┬┴┬┴─┴┬┴─┘
        └──────XOR┘ │   │
                └──XOR──┘ (taps == 7, 5, 4)
    """
    taps = [bits - tap for tap in taps]
    r = seed & (1 << bits) - 1
    while(1):        
        tap_bits = [(r >> tap) & 1 for tap in taps]        
        bit = reduce(lambda x, y : x ^ y, tap_bits)
        yield r & 1
        r &= (1 << bits) - 1
        r = (r >> 1) | (bit << (bits - 1))