# Relationship between Fibonacci LFSR and Galois LFSR

I'm studying about LFSR and have some troubles understanding LFSRs.

For Galois LFSR, it is clear that LFSR just multiplies $$x$$, the primitive element of $$GF(2^n)$$, so that it makes all the elements in $$GF(2^n)$$.

But for Fibonacci LFSR, it seems somewhat awkward.

In the answer at math.stackexchange, it says each register of Fibonacci LFSR is the dual basis of Galois LFSR, but can't we express it in the polynomial term?

And I also wonder whether the 'mirror' polynomial scheme, like $$x^4+x^2+x^1+1$$ vs $$x^4+x^3+x^2+1=x^4(x^{-4}+x^{-2}+x^{-1}+1)$$ can help to understand Fibonacci and Galois LFSR.

• I currently lack time to properly answer that. But this answer to a different question at least gives the equations for the output of a Fibonacci LFSR and Galois LFSR using consistent convention. – fgrieu Mar 1 at 8:15

Consider a Galois LFSR with feedback polynomial $$x^3 + x + 1$$ and initialization $$1 + 0x + 0x^2$$, that is, the shift register shifts its initial content $$(1,0,0)$$ rightwards, and the output bit (the rightmost bit) is fed back into the shift register into the $$1$$ and the $$x$$ position. The initial loading of the LFSR is the Galois field element $$1$$, and successive contents are as follows:
$$\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}$$ The LFSR output is the (periodic) sequence leaving the right end of the LFSR and is thus $$(0,0,1,0,1,1,1)$$ at which point the sequence repeats (the period is $$7$$). Notice that if we look at the successive contents of the leftmost bit in the LFSR, they are $$(1,0,0,1,0,1,1)$$ which is just the output sequence shifted right cyclically by 1 bit while the middle bit is $$(0,1,0,1,1,1,0)$$ which is just the output sequence shifted left cyclically by one bit.
With the Fibonacci LFSR, there are two conventions as to what the feedback polynomial means. We can take $$x^3+x+1$$ to mean that the LFSR shifts right while the (XOR) sum of the current values of the output cell and the leftmost cell are fed back into the leftmost cell, or that the XOR sum of the two rightmost cells is fed back into the leftmost cell. The corresponding LFSR contents are $$\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}$$
Note that in the righthand column, the output sequence is $$(0,0,1,0,1,1,1)$$ which is identical to the output sequence of the Galois LFSR while in the lefthand column, the output sequence is $$(0,1,1,1,0,1,0)$$ which is just a reversed and shifted version of the output sequence of the Galois LFSR. Now, all this can be explained in great generality with reference to dual polynomial bases etc (as I did in my answer to the math.SE question cited by the OP), but the point is that the Fibonacci LFSR produces the same sequences as those produced by the Galois field LFSR, and that the reciprocal polynomial can be useful in explaining why this is so depending on the convention used to map the polynomial onto the circuit connections.