Fri Jun 27 13:31:59 CEST 2008

reverse LFSR

What happens if you reverse an LFSR sequence? This is most easily seen
by expressing the LFSR as f(x[i] ...) = 0. The only thing that happens
is the reversal of the coefficients. So 100101 -> 101001

Now, the question is, are there LFSR equations that are symmetric in
this sense? This would also mean the sequence itself is symmetric
around every point, which doesn't look like it's possible.

Next step: is it possible to relate an LFSR to its inverse? After all,
all galois fields of order 2^N are isomorphic.

It might be interesting to cast the equation into exponential form to
work with multiplicative generators g^i. Are all LFSR sequences of a
certain order related by mere re-arranging, like taking every 3rd bit?
Hmm... getting confused.

Let's view this in a transformed domain. The LFSR sequence is the
coefficient of the sequence of polynomials generated by
multiplications by x, the 'shift' operator. (This turns the modulo
operation into a simple XOR.)

In matrix/vector terms, given an LFSR polynomial a of order N, pick an
initial point in the state space e = {e1,...,eN). Take the update
equation of the LFSR, and call its matrix g. This is the
multiplicative generator for the sequence.

 Q: Another thing to think about: to compute eigenvalue decomposition
    in |C one needs complex eigenvalues (the splitting
    field). However, there exists a 'real form' of this which has
    blocks of 2D rotations instead of complex diagonal forms. Is this
    possible for LFSR?

 Q: how many different sequences are there for a given Galois field?
    (number of automorphisms)