线性反馈移位寄存器？

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)

然后我想到，这在编写软件中有什么用处？我听说它可以生成随机数；这是真的吗？如何实现？

因此，如果有人能：

- 解释如何在软件开发中使用这样的设备 - 提供一些代码，支持上述观点或类似于我的代码以展示不同的实现方式（任何语言）

由于关于这个逻辑和数字电路的教学材料不多，所以对于像我这样的新手来说，这可能是一个更好地了解这个“东西”的地方，或者更好地理解它是什么以及在编写软件时如何有用。这是否应该成为社区wiki？

话虽如此，如果有人想要挑战高尔夫......欢迎。

- MattiaG

---

如果你在 Stack Overflow 上搜索 lfsr，你会找到很多相关的内容... - Dr. belisarius

我做了，但不是我想要的那样。 - MattiaG

为什么将这个标记为代码高尔夫？ - Landei

@Landei：因为我也想看到它被压缩。如果这对标签来说还不够，抱歉。 - MattiaG

就在两天前，我使用LFSR将一个整数序列转换为半随机序列，然后再将其转换回来：https://dev59.com/fWHVa4cB1Zd3GeqPqMqp#9848014 - Karoly Horvath

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₃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 中的“触发器”。

我们还会选择一个三次或更低次数的随机多项式（这样它不会受到我们的模运算影响，否则我们可以直接对其进行模运算），例如 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)的两个值相加（即0+0=0，0+1=1，1+1=0或对这两个值进行异或）来确定每个a_i是否变为0或1。

每个多项式都可以写成一组位，例如x⁴+x¹+x⁰ ~ 10011。A₀(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”，以确保您的比特流不会以0000比特模式结束，或者最后一个比特将变为未使用（如果所有比特都向左移动，则在一次移位后，您也将在0号位置处得到零）。

并非所有的P(x)都一定是GF(2^k)的生成器（即，不是所有k位掩码都会生成所有2^(k-1)-1个数字）。例如，x^4 + x^3 + x^2 + x^1 + x^0生成了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-盒。

---

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

- ralphje

Answer 2

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

CRC32是一个非常常见的例子。它用于检测以太网帧中的错误。这意味着当我发布这个答案时，我的电脑使用基于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微控制器编写Modbus驱动程序，该协议使用了CRC16。一个预先计算的表需要256字节的内存，而我的CPU只有68字节（我不是在开玩笑）。因此，我不得不使用LFSR。

- slebetman

---

TCP/IP使用简单的校验和，而不是CRC32。其他协议可能有额外的检测错误的手段（例如：以太网具有FCS，我记得它是一个CRC）。 - ninjalj

@ninjalj：已经更正。感谢您的指出。 - slebetman

Answer 3

这是我的一个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]

也可以像这样进行可视化展示

在这里查看文档

- Nikesh Bajaj

Answer 4

LFSR有许多应用，其中之一是生成噪声。例如SN76489及其变体（用于Master System、Game Gear、MegaDrive、NeoGeo Pocket等）使用LFSR来生成白色/周期性噪声。关于SN76489的LFSR有一个非常好的描述，可参考此页面。

- ninjalj

---

最近我不得不编写一些软件来校准地震探测器。事实证明，至少有一家公司（Nanometrics）使用LFSR生成“噪声”信号用于测量频率响应（将此噪声馈送到探测器中，测量响应，然后将响应的FFT与输入的FFT进行比较；这给出了系统对一系列频率的响应）。 - andrew cooke

Answer 5

以下是您的代码的变体，使用整数和二进制运算符而不是字符串。它还使用了某人建议的yield。

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:]

- kriss

Answer 6

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

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

- Eli Bendersky

---

我会尝试，但现在我不确定如何做到这一点。我以为0.0会让我避免另一个表达式...事实上你是对的，它是无用的。所以它为每个状态生成一个数字，我的意思是，这些状态就是它生成的数字？它还有其他用途吗？ - MattiaG

@Mattia：你看到维基百科上的“应用程序”部分了吗？看起来信息很丰富。 - Eli Bendersky

虽然它很好，但它更偏向于硬件应用，我也希望能看到一些代码。 - MattiaG

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

- nowox

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

- Grass M.

---

请解释你的代码是做什么的以及为什么要这样做。在Stack Overflow上，仅仅发布代码通常不是一个好回答。 - dirkk

我的list_init是Anne PDF中所称的阶段，我的list_coeff是PDF中所称的LFSR反馈系数，并且结果存储在一个新的列表out中。特别地，这个列表包含了PDF中给出的例子的系数和阶段。谢谢，再见 :) - Grass M.

Answer 9

这个类提供了一个易于使用的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))

- George Nardes

Answer 10

如果我们假设种子是一个整数列表而不是字符串（或者在它不是时进行转换），那么以下代码应该以更加优雅的方式实现你想要的功能：

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

- Andrew

---

这对我来说真的很有趣，但出于某种原因我无法让它运行起来。你能给个使用示例吗？谢谢。 - MattiaG