如何将Galois LFSR转换为Fibonacci LFSR？

Question

我刚刚找到了Galois类型LFSR输出的序列，见这里。

现在我知道有一个斐波那契型LFSR能够输出同样的序列，但是我怎么能找到这个LFSR的前六种状态呢？

Answer 1

在这个答案中，我将考虑在这个问题上提到的Galois：Galois型LFSR序列输出，见下图。

首先，我们假设位的5个位置从左到右编号:0。4.

Galois代表的情况如下：

+--------------------------------------------------------------+
|                         |           |           |            |
|    +-----+     +-----+  |  +-----+  |  +-----+  |  +-----+   |
|    |     |     |     |  v  |     |  v  |     |  v  |     |   |
+--->+  1  +---->+  0  +--+->+  0  +--+->+  0  +--+->+  0  +-------> ...
     |     |     |     |     |     |     |     |     |     |
     +-----+     +-----+     +-----+     +-----+     +-----+

如果我们迭代LFSR 10轮，就会得到：

1 0 0 0 0 : initial state
0 1 0 0 0 -> 0
0 0 1 0 0 -> 0
0 0 0 1 0 -> 0
0 0 0 0 1 -> 0
1 0 1 1 1 -> 1

1 1 1 0 0 -> 1
0 1 1 1 0 -> 0
0 0 1 1 1 -> 0
1 0 1 0 0 -> 1
0 1 0 1 0 -> 0

假设现在我们有一个Fibonacci LFSR，但是我们想知道水龙头在哪里。我们将迭代lfsr并用字母命名unkowns。解决这一问题涉及两个技巧：

• 一个字母一旦设置，以后就不会修改(相对于Galois版本)。
• 使用初始10000状态将显示水龙头的位置。

所以我们有：

1 0 0 0 0 : initial state
a 1 0 0 0 -> 0            (i)
b a 1 0 0 -> 0
c b a 1 0 -> 0
d c b a 1 -> 0
e d c b a -> 1

那我们就能解决了。

f e d c b -> a = 1

通过(i)，我们可以推断出位置0对输出的影响:所有其他位置都为空。

g f e d c -> b = 0 -> b

只要位置0有影响，b就是1。因此，位置1也影响它使其回到0。

h g f e d -> c = 0

只要位置0和1有影响，c就是0。位置2也是影响它使其回到0。

i h g f e -> d = 1

d是它应该是的值，因此位置3没有影响。

j i h g f -> e = 0

e是它应有的价值，就像有反馈一样。

如果我们继续对这两个模型的下5个输出，我们有以下流：01111

最后，LFSR的Fibonacci表示如下：

+-------------+-----------+-----------+------------------------+
|             ^           ^           ^                        |
|    +-----+  |  +-----+  |  +-----+  |  +-----+     +-----+   |
|    |     |  |  |     |  |  |     |  |  |     |     |     |   |
+--->+  1  +---->+  0  +---->+  0  +---->+  0  +---->+  0  +-------> ...
     |     |     |     |     |     |     |     |     |     |
     +-----+     +-----+     +-----+     +-----+     +-----+

这里是一个小的python代码，用于检查两者之间的等价性。