How to convert a Galois LFSR to a Fibonacci LFSR? 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?
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  |     |   |
+---&gt;+  1  +----&gt;+  0  +--+-&gt;+  0  +--+-&gt;+  0  +--+-&gt;+  0  +-------&gt; ...
     |     |     |     |     |     |     |     |     |     |
     +-----+     +-----+     +-----+     +-----+     +-----+


If we iterate the LFSR for 10 rounds we get:

1 0 0 0 0 : initial state
0 1 0 0 0 -&gt; 0
0 0 1 0 0 -&gt; 0
0 0 0 1 0 -&gt; 0
0 0 0 0 1 -&gt; 0
1 0 1 1 1 -&gt; 1

1 1 1 0 0 -&gt; 1
0 1 1 1 0 -&gt; 0
0 0 1 1 1 -&gt; 0
1 0 1 0 0 -&gt; 1
0 1 0 1 0 -&gt; 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 -&gt; 0            (i)
b a 1 0 0 -&gt; 0
c b a 1 0 -&gt; 0
d c b a 1 -&gt; 0
e d c b a -&gt; 1


Then we can solve it.

f e d c b -&gt; a = 1


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

g f e d c -&gt; b = 0 -&gt; 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 -&gt; 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 -&gt; d = 1


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

j i h g f -&gt; 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:

+-------------+-----------+-----------+------------------------+
|             ^           ^           ^                        |
|    +-----+  |  +-----+  |  +-----+  |  +-----+     +-----+   |
|    |     |  |  |     |  |  |     |  |  |     |     |     |   |
+---&gt;+  1  +----&gt;+  0  +----&gt;+  0  +----&gt;+  0  +----&gt;+  0  +-------&gt; ...
     |     |     |     |     |     |     |     |     |     |
     +-----+     +-----+     +-----+     +-----+     +-----+


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