Fibonacci LFSR与Galois LFSR的关系

Question

我正在学习LFSR，并有一些困难，了解LFSR。

对于Galois，很明显，它只是将x ( GF(2^n)的原语元素)相乘，从而使GF(2^n)中的所有元素都是乘法的。

但对于斐波纳契LFSR来说，这似乎有点尴尬。

在math.stackexchange的回答中，它说Fibonacci的每个寄存器都是Galois的对偶基，但我们不能用多项式表示它吗？

我还想知道像x^4+x^2+x^1+1和x^4+x^3+x^2+1=x^4(x^{-4}+x^{-2}+x^{-1}+1)这样的“镜像”多项式方案是否能帮助理解Fibonacci和Galois。

Answer 1

考虑一个具有反馈多项式x^3 + x + 1和初始化1 + 0x + 0x^2的Galois，即移位寄存器将其初始内容(1,0,0)右移，输出位(最右位)反馈到移位寄存器到1和x位置。LFSR的初始加载是Galois字段元素1，后续内容如下：

\begin{array}[ccl]{3} (1,0,0) &= 1 + 0x + 0x^2 &= 1\\ (0,1,0) &= 0 + 1x + 0x^2 &= x\\ (0,0,1) &= 0 + 0x + 1x^2 &= x^2\\ (1,1,0) &= 1 + 1x + 0x^2 &= x^3 ~~~ \text{remember that} ~x^3 = x + 1\\ (0,1,1) &= 0 + 1x + 1x^2 &= x^4\\ (1,1,1) &= 1 + 1x + 1x^2 &= x^5\\ (1,0,1) &= 1 + 0x + 1x^2 &= x^6\\ (1,0,0) &= 1 + 0x + 0x^2 &= x^7~~~ \text{remember that} ~x^7 = 1\\ \end{array} ，LFSR输出是(周期)序列，离开LFSR的右端，因此是(0,0,1,0,1,1,1)，在这一点上，序列重复(周期是7)。注意，如果我们查看LFSR中最左边位的连续内容，它们是(1,0,0,1,0,1,1)，它只是循环地右移1位的输出序列，而中间位是(0,1,0,1,1,1,0)，也就是循环左移1位的输出序列。

对于Fibonacci LFSR，关于反馈多项式的含义有两个惯例。我们可以将x^3+x+1看作是当输出单元格和最左边单元格的当前值的( XOR )和反馈到最左边的单元格时，LFSR向右移动，或者两个最右边单元格的XOR和被反馈到最左边的单元格中。相应的LFSR内容如下

\begin{array}[ccc]{3} \text{output plus leftmost} & \quad & \text{two rightmost}\\ (1,0,0) & &(1,0,0)\\ (1,1,0) & &(0,1,0)\\ (1,1,1) & &(1,0,1)\\ (0,1,1) & &(1,1,0)\\ (1,0,1) & &(1,1,1)\\ (0,1,0) & &(0,1,1)\\ (0,0,1) & &(0,0,1)\\ (1,0,0) & &(1,0,0) \end{array}

注意，在右边的列中，输出序列是(0,0,1,0,1,1,1)，它与Galois的输出序列相同，而在左边的列中，输出序列是(0,1,1,1,0,1,0)，这是Galois输出序列的反转和移位版本。现在，所有这些都可以用对偶多项式基等来解释，但重点是Fibonacci产生的序列与伽罗瓦域LFSR产生的序列相同，而倒数多项式可以用来解释为什么这取决于将多项式映射到电路连接上的惯例。

最后，Fibonacci LFSR比Galois LFSRs要好得多，因为后者需要LFSR的“单元”之间的独占或门，而前者不需要。Fibonacci LFSR的一些现代硬件实现实际上并不将数据存储在一个移位寄存器中--当数据从一个单元单元转移到另一个单元单元时，数据会随寄存器转移而从一个单元到另一个单元(每次转换消耗能量！)尽管教科书和论文中的插图和图表都是这样的。相反，每个单元格内容都存储在sRAM中，并在需要时进行访问(例如，参与XOR以反馈到“最左边”单元格)。从时钟周期到时钟周期的变化是存储在sRAM中的LFSR内容的心理图像(或内存映射)。数据本身根本不移动，尽管一个sRAM存储单元(根据内存映射当前的“最左边”单元)在每个时钟周期中都会修改其内容。在Galois LFSR实现中，许多单元将需要在每个时钟周期中进行修改，如果所有的实现都并行或减速，那么每个时钟周期的复杂性就会大大增加，这样就可以在LFSR的一个“时钟周期”的可用时间内依次进行更新。