`[<<][math][>>][..]`
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.

Equations:
( 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.

```
`[Reply][About]`
`[<<][math][>>][..]`