Fri Jun 27 15:28:37 CEST 2008

LFSR resolving linear orientation ambiguity

 Q: What happens if the LFSR in one direction is XORed with its
    reverse? does that still give a proper sequence? That way it would
    be possible to have contribution of 2 directions, which then can
    be used to resolve ambiguity.

( with A'[i] = A[N-i-1] )

L[D+i]  = f( L[i] ... L[D-1+i] )     0 <= i < (N - D)
R'[D+i] = f( R'[i] ... R'[D-1+i] )   0 <= i < (N - D)
X[i]    = L[i] + R[i]                0 <= i < N
                                              3N  - 2D
Number of unknowns: 2N

          D <= N/2

The only problem then is to figure out whether the systems are
independent. Does this sum of sequence + reverse somehow reduce to
something of lower degree?

For one thing, it is reversal-symmetric around the initial state,
which can be taken not to ly in the surface of interest. Is there
anything else destroyed?

In terms of the unit element e, and the generators g and g^-1 the
sequence becomes a cosine instead of an exponential:

         e g^i + e g^{-i} = e (g^i + g^{-i})

This can no longer be written as an LFSR, because it has hidden state
(LFSR has a naked state). It is a more general form of linear system.

I don't se any reason why this can't be generalized to the 2D case.

 Q: Are there points where this XOR operation itself leads to
    ambiguities? In other words, are there XORed segments that have
    multiple parents? If so, then it is probably possible to find a
    small upper bound of the number of observations to take to
    eliminate this ambiguity. ( Since an large ub is probably easy to
    find: take one that reduces the search space for collisions to a
    small amount, i.e. one case. ) Note that if there are such
    ambiguities then a simple exhaustive search for soluble sets of
    equations in the non-symmetric 2D case might be a better approach.