非二进制线性反馈移位寄存器

Question

我使用Wikipedia上的指令用Python语言编写了一个伽罗瓦线性反馈移位寄存器：

def lfsr(coefficients, state):
    while 1:
        lsb = state.pop()
        state.insert(0, 0)
        if lsb:
            state = app(coefficients, state)

        yield lsb

def app(coefficients, state):
    return [ (coefficients[i]^state[i]) for i in range(len(state)) ]

L = lfsr([1,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,1], [0]*15+[1])
seq = [ str(L.next()) for i in range(2**16+16) ]

这可以很好地工作。我现在想做的是写一个通用的版本，它可以处理除GF(2)以外的伽罗瓦域，但我不理解关于non-binary LFSRs的部分。这部分对我来说没什么意义：“反馈位(输出位)乘以一个Q值(模Q)，该值对于每个特定的抽头点都是恒定的。”如何将单个输出位与每个分接点的值相乘？

这就是我想出来的，但是没有给出循环序列，输出很快就变得全0了：

# Multiplication table for GF(4)
mult_4 = [[0, 0, 0, 0],
          [0, 1, 2, 3],
          [0, 2, 3, 1],
          [0, 3, 1, 2]]

def lfsr(coefficients, state):
    while 1:
        lsb = state.pop()
        state.insert(0, 0)
        state = app(coefficients, state)

        yield lsb

def app(coefficients, state):
    return [ mult_4[coefficients[i]][state[i]] for i in range(len(state)) ]

L = lfsr([ 1, 0, 0, 0, 1, 2, 3 ], [1]*6)
seq = [ str(L.next()) for i in range(4**6+6) ]

Answer 1

我建议您熟悉一下polynomial rings的概念(尽管维基百科上的那篇文章太技术性，无法做最好的介绍)。你可能遇到的最基本的问题是，你试图太过接近地模仿一个二进制移位寄存器，当你把它看作一个离散的动态系统，而不是一个电路时，你没有完全理解它发生了什么。

二进制移位寄存器是一种聪明的电路，它计算X^N除以f(X)时的余数，其中f的所有系数都在Z/2Z环中，该环只包含0和1。这些余数是用欧几里得算法计算的，就像计算整数的余数一样。在这个模型中，LFSR的状态是比f的次数少的次数多项式。LFSR的第一个状态是1，第二个是X。LFSR中的每个周期都等同于乘以X，然后进行一步长除法。移位操作是乘法，抽头是长除法。在这里，部门确实是核心所在。

旁白:您可以使用任意环作为这种构造的系数，但是零因子作为除数多项式的前导系数的问题使事情变得复杂。既然你使用的是一个字段，我就把字段当作系数来讨论。

如果你使用的不是位的系数环，你需要考虑长除法的一个步骤是什么样子的。如果除数多项式f看起来像a_k X^k + ...，而新的状态g看起来像b_k X^k + ...，那么长除法的第一步就是计算b_k / a_k。对于一个字段(正如我假设的那样)，这是一些数字c。所以余数是g - cf，它是一个k-1次的多项式。剩下的就是你的新状态。

(表达cf是理解维基百科文章中令您困惑的部分的关键。您可能希望说服自己，可以用一个多项式f除以它的前导系数a_k来得到另一个多项式，它生成的序列只是第一个序列的倍数。)