线性反馈移位寄存器？

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)

然后它让我印象深刻,这在编写软件时有什么用？我听说它可以生成随机数; 这是真的吗？怎么样？所以,如果有人可以:

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

另外,由于这个逻辑和数字电路没有太多的教学内容,如果这可以成为noobies(像我一样)的地方,以便更好地理解这个东西,或者更好,理解它是什么在编写软件时它是如何有用的.应该把它变成一个社区维基？

也就是说,如果有人感觉喜欢打高尔夫......那么欢迎你.

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(^2k)模数微积分(GF = 伽罗瓦域).刚完成代数课程后,我将以数学方式解释这一点.

让我们从例如GF(2 ⁴)开始,等于{a ₄ x ⁴ + a ₃ x ³ + a ₂ x ² + a ₁ x ¹ + a ₀ x ⁰ | 一个₀,一个₁,...,A ₄ ∈ž ₂ }(澄清,Z _Ñ = {0,1,...,N-1},因此ž ₂ = {0,1},即,一个比特).这意味着这是所有多项式的集合,其中所有因子都存在与否,但没有这些因子的倍数(例如,没有2x ^k).x ³,x ⁴ + x ^3,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来计算每个后续的A _i(x):A _i(x)= A _i-1(x)*x mod P(x).

由于我们处于有限的场中,因此模数运算可能会产生影响,但仅当得到的A _i(x)至少具有因子x ⁴(我们在P(x)中的最高因子)时.请注意,由于我们使用Z _2中的数字,执行模数运算本身只不过是通过将P(x)和A _i(x)中的两个值相加来确定每个_i是否变为0或1 (即,0 + 0 = 0,0 + 1 = 1,1 + 1 = 0,或'xoring'这两个).

每个多项式可以写成一组位,例如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生成四位结果.另请注意,第0个位置必须存在'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'.LFSR的周期为2 ^k-1 -1,也称为伪噪声或PN-LFSR,它遵循Golomb的随机性假设,即该输出位随机"足够".

因此,这些比特的序列可用于密码术,例如A5/1和A5/2移动加密标准,或E0蓝牙标准.然而,它们并不像人们想象的那样安全:Berlekamp-Massey算法可用于逆向工程LFSR的特征多项式(P(x)).因此,强加密标准使用非线性FSR或类似的非线性函数.与此相关的主题是AES中使用的S-Box.

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

Answer 2

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

CRC32是一个非常常见的.它用于检测以太网帧中的错误.这意味着当我发布这个答案时,我的PC使用基于LFSR的算法来生成IP数据包的散列,以便我的路由器可以验证它的传输内容是否已损坏.

Zip和Gzip文件是另一个例子.两者都使用CRC进行错误检测.Zip使用CRC32,Gzip使用CRC16和CRC32.

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

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

应该注意的是,使用bit-fiddling LFSR进行这种天真的操作非常慢,因为你必须一次处理位.因此人们已经想出了使用预先计算的表来一次做8位甚至32位的方法.这就是为什么你几乎从未在野外看到LFSR代码.在大多数生产代码中,它伪装成其他东西.

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