3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – fgrieu Mar 1 at 8:15
5
$\begingroup$

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.

As a final note, Fibonacci LFSRs are vastly preferable to Galois LFSRs because the latter require Exclusive-OR gates between the "cells" of the LFSR while the former don't. Some modern hardware implementations of Fibonacci LFSRs don't actually store the data in the cells in a shift-register where the data goes ka-chunking from cell to cell as the register shifts (each transition costs energy!) even though that's what is always shown in illustrations and diagrams in textbooks and papers. Instead, each cell content is stored in sRAM and accessed as and when needed (e.g. to participate in a XOR to be fed back to the "left-most" cell). What changes from clock cycle to clock cycle is the mental image (or memory map) of where the LFSR contents are stored in sRAM. The data itself does not move at all though one sRAM storage cell (the current "left-most" cell as per the memory map) gets its contents modified in each clock cycle. In a Galois LFSR implementation, many cells would need to be modified in each clock cycle leading to vastly increased complexity if everything is done in parallel or slowing down of the implementation so that the updates can be done sequentially in the time available for one "clock cycle" of the LFSR.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.