线性反馈移位寄存器？

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 = 伽罗瓦域）。刚刚完成代数课程后，我将以数学方式解释这一点。

我们首先以 GF(2⁴) 为例，它等于 {a₄x⁴ + a_{3< /sub>x³ + a2x² + a1x¹ + a0x⁰ | a0, a1, ..., a4 ∈ Z2} （澄清一下，Z< sub>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 模 P(x)。

由于我们处于有限的范围内，模数运算可能会产生影响，但只有当生成的 A_i(x) 至少具有因子 x⁴（我们的最高P(x) 中的因子）。请注意，由于我们处理的是 Z₂ 中的数字，因此执行模运算本身无非就是通过将两个 a_i 相加来确定每个 a_i 是否变为 0 或 1 P(x) 和 A_i(x) 的值在一起（即，0+0=0、0+1=1、1+1=0，或“异或”这两个值）。

每个多项式都可以写成一组位，例如 x⁴+x¹+x⁰ ~ 10011。 0(x)可以看作种子。 “乘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”必须出现在第 0 个位置，以确保您的比特流不会以 0000 位模式结束，或者最后一位将变为未使用（如果所有位都向左移动，您将一次转换后，第 0 个位置处也会有一个 0）。

并非所有 P(x) 都一定是 GF(2^k) 的生成器（即，并非所有 k 位掩码都生成所有 2^k-1-1 数字） 。例如，x⁴ + x³ + x² + x¹ + x⁰ support> 生成 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）遵循哥伦布随机性假设，该假设表明该输出位“足够”随机。

因此，这些位的序列在密码学中具有用途，例如在 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)-对。

Answer 2

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

CRC32 是一种非常常见的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 库之一 - pylfsr 来实现 LFSR。我试图使其高效，可以处理任何长度的 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

为了使其真正优雅和 Python 化，请尝试创建一个生成器，从 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

这里有一段代码，您可以在其中选择您的种子、位数和您想要的抽头：

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))

Answer 8

如果我们假设种子是一个整数列表而不是一个字符串（如果不是字符串则将其转换），那么下面的代码应该更优雅地完成您想要的操作：

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 9

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 10

此类提供了一个易于使用的 LFSR 生成器对象

import numpy as np

class lfsr:
    
    def __init__(self, seed=1, nbits=8, taps=(0,1, 5, 6)): # different taps may not work well. I suggest looking for a standard configuration
        self.seed0 =seed
        self.seed = seed
        self.nbits = nbits
        self.bmask = (2**nbits)-1
        self.taps = taps

        
    def next_rnd(self):
        b_in = 0
        for t in self.taps:
            o = 2**t                                                
            b_in ^= (o&self.seed)>>t                                         
        
        self.seed =(self.seed >> 1) | (b_in << (self.nbits-1))
        self.seed = self.seed & self.bmask          
        return self.seed
        
        
    def print_s(self):
        print(self.seed)        
              
        
    def get_rnd_array(self, seed=None):
        self.seed = seed if seed is not None else self.seed        
        arr = np.zeros((2**self.nbits))      
        for i in range(2**self.nbits):
            arr[i] = self.next_rnd()
            
        return arr

    def get_double_rnd_array_circular(self, seed=None): # ref.: Compact and Accurate Stochastic Circuits with Shared Random Number Sources
        k = int(self.nbits/2)
        self.seed = seed if seed is not None else self.seed        
        arr0 = np.zeros((2**self.nbits)) 
        arr1 = np.zeros((2**self.nbits)) 
        
        for i in range(2**self.nbits):
            rnd = self.next_rnd()            
            arr0[i] = rnd                         
            rnd_p0 = rnd >> k            
            rnd_p1 = (rnd & (2**k-1)) << k                      
            rnd_p2 = rnd_p1 | rnd_p0                    
            arr1[i] = rnd_p2            
        return arr0, arr1
    
    
l = lfsr(1, 4, (0,1))


print(l.get_rnd_array(11))
print(l.get_double_rnd_array_circular(11))