0

我使用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) 以外的 Galois 字段，但我不明白关于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) ]
4

2 回答 2

1

我建议您熟悉多项式环的概念（尽管 Wikipedia 的那篇文章技术性太强，无法做出最好的介绍）。您似乎遇到的最基本的问题是您试图过于接近地模仿二进制移位寄存器，当您将其视为离散动态系统而不是电路时，无法完全理解正在发生的事情。

二进制移位寄存器是一个巧妙的电路，它计算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。对于一个字段（正如我假设的那样），这是一些 number c。所以余数是g - cf，它是一个度数为 的多项式k-1。剩下的就是你的新状态。

（表达式cf是理解 Wikipedia 文章中让您感到困惑的部分的关键。您可能想说服自己，您可以将多项式除f以其前导系数a_k得到另一个多项式，该多项式生成的序列只是第一的。）

于 2012-11-20T06:25:05.500 回答
0

您可以在 math.stackoverflow.com 上询问有关 Galois 字段下的乘法，但其要点是，每个“位”不是“位”，其中每个位是 0 或 1 (GF_2)，每个“位”实际上是一个数字符号数——确切的数字取决于字段的大小。

要从二进制 LFSR 到 Galois LFSR，您必须概括“位”和“乘法”的概念，以便在该领域有意义。字段中的乘法运算Addition 也代替了app()函数中的 XOR。

在二进制版本中，乘法是隐式的；输出位乘以 0 或 1，具体取决于是否存在抽头。在一般字段中，抽头本身可以具有与之关联的任何字段元素，然后将其乘以输出。

于 2012-11-15T22:51:04.193 回答