# 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?

• the first 6 states of such LFSR should be the same as the ones with a Galois LFRS, the difference lies in the representation of the LFSR. – Biv Apr 10 '17 at 11:32
• What would the representation of the Fibonacci-type LFSR be? I've been having a go with trial and error but there must be a better way? – harry55 Apr 10 '17 at 11:39

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.

• Thank you so much, this is such a clear detailed answer! Just one thing, I'm reading some notes and it says "It can be shown that for every $M$-sequence output by a Galois-type LFSR, it is possible to construct a Fibonacci-type LFSR that outputs the same $m$-sequence. (It will, however, go through a different sequence of internal states to produce that output.)", which goes against what you have said, is this to say that the difference doesn't always lie only in the representation of the LFSR? but it just so happens in this one it does? – harry55 Apr 10 '17 at 15:46
• No it does not go against what i said i never said that the interval state had to be the same in both cases. As matter of fact this is impossible. – Biv Apr 10 '17 at 16:01
• The differences is the way you compute the internal state. – Biv Apr 10 '17 at 16:02
• This is your homework you have to figure this out by yourself. If you can't this means that you clearly don't understand how LFSR works even though I provided you examples in the two settings. – Biv Apr 10 '17 at 18:16