How to convert a Galois LFSR to a Fibonacci LFSR?

Question

I have just found the sequence output by the Galois type LFSR, seen here.

Now I know there exists a Fibonacci-type LFSR capable of outputting this same sequence but how could I find what the first six states of this LFSR would be?

Answer 1

In this answer I will consider the Galois LFSR mentionned at this question: Sequence output by a Galois type LFSR see the image below.

First we assume that the 5 positions of bits are numbered from left to right: 0 .. 4

The Galois representation is as follows:

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

If we iterate the LFSR for 10 rounds we get:

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

Assuming now that we have a Fibonacci LFSR but we want to know where the tap are. We will iterate the lfsr and naming the unkowns by letters. There are two tricks involved to solve this:

• a letter is once set and never modified later (as opposed to the Galois version)
• using an initial 10000 state will reveal the positions of the taps.

So we have:

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

Then we can solve it.

f e d c b -> a = 1

By (i), we can deduce that position 0 influence on output: all the other positions are null.

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

b would be 1 if only position 0 had an influence. Thus Position 1 is also influencing making it back to 0.

h g f e d -> c = 0

c would be 0 if only position 0 and 1 had an influence. Position 2 is also influencing making it back to 0.

i h g f e -> d = 1

d is the value it should be thus position 3 is not influencing.

j i h g f -> e = 0

e is the value it should be as there is the feedback.

If we continue on the next 5 outputs on both models we have the following stream: 01111

To conclude the Fibonacci representation of the LFSR is the following:

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

Here is a small python code to check the equivalence between both.