Mixing LFSRs

Posted on August 28, 2011 by webmaster

This was a topic of minor importance that came up recently with a college.  LFSR’s have been discussed here in the past.  One of the interesting aspects of LFSR’s is that the XOR of any two (or more) bits within the LFSR will not create a unique pattern — merely shift the current pattern in phase.

This seems like an odd statement — an LFSR is pseudorandom and has low autocorrelation at time shifts.  It would seem like XOR-ing two such bits would result in something unique.

The proof against this is actually quite simple.  In the below, A is a matrix with entries in GF2.  It describes the LFSR shift-by-one operation.  A maximal length sequence implies A^{2^N-1} = I, where I is the identity matrix.  Here it is assumed that a fibbonacci implementation is used, but this is unimportant overall.

  • x_{n+1} = A x_{n}
  • y_{n+1} = A x_{n} + A^k x_{n}

These are the system equations.  The first equation relates the next state of x as an LFSR shift applied to the current state of x.  The second relates the output, y, as a sum of different amounts of LFSR-shifts applied to the current state.  This gives:

  • x_{n+1} = A^{n+1} x_{0}
  • y_{n+1} = A^{n+1} x_{0} + A^{n+k+1} x_{0}

From which it is fairly clear from algebra that:

  • y_{n+1} = A^{n+1} ( (I+A^k) x_0 )

This clearly shows that the output looks just like the original LFSR sequence.  The only difference is that, instead of being initialized by x_0, it is actually initialized by ( (I+A^k) x_0 ).  This is merely a phase shift of the original LFSR, as ( (I+A^k) x_0 ) will exist as some valid state within the LFSR.

There is of course a degenerate case, when A^k = I the addition in GF2 will result in 0.  This case is equivalent to writing y_{n+1} = A^{n+1} x_0 + A^{n+1} x_0.  In which case the addition in GF2 forces the output to zero.

The above can easily be expanded to XOR’s with multiple bits of the current LFSR state.  The fibbonacci implementation makes it a bit easier to see why selecting a bit other than the msb as an output would also result in a shift of the LFSR.

There is also the case where the complement of a tap is added.  eg y_{n+1} = A x_n + A^{n+1} x_0 + (A^{n+1+k} x_0 + b).  This can be done by adding a constant term to the output equation.  For the 1b output LFSR generators, this ends up giving the potential for 2 different sequences.  The second sequence is simply the original sequence but with the 1’s and 0’s swapped.

This entry was posted in Math. Bookmark the permalink.

Comments are closed.