[sdiy] Long LFSRs (Was Psych Tone)

[ASSI]

On Tuesday, January 8, 2019 1:51:53 AM CET Bernard Arthur Hutchins, Jr wrote:
> Achim followed with: “That is what allows an LFSR to implement a matrix
> multiplication with such low hardware complexity.”
> 
> I have no idea what that means – please elaborate.

The equation producing the next state of an LFSR is a matrix multiplication in 
GF(2).

> Matthew then replied:    “It's also addition, in a different encoding - and
> that's the reason for the LFSR to be called linear.  All these
> "polynomials" are polynomials defined over the field GF(2), in which the
> addition operation is the same thing as XOR on bits.”

True that, but the real point is that the "linear" moniker is directed at the 
state equation.  Just like "recursive" denotes the successive application of 
said state equation, which can then be denoted as matrix exponentiation if you 
wish.

> EXOR is still non-linear in the PRBS structure – the particular application
> under discussion here.

In general Boolean algebra it is non-linear, but not in GF(2) (nor in modular 
arithmetic for a modulus of 2), both of which can be implemented in terms of 
Boolean algebra.  That's not unlike the situation we have with translinear 
circuits, where the external transfer function is linear, but possibly all 
internal variables are governed by nonlinear equations.

https://link.springer.com/content/pdf/bbm%3A978-3-319-40341-0%2F1.pdf

> I was saying that you MULTIPLY the two sequences by EXOR.  The little guy
> simply “chops up” any misbehavior of the long sequence.   They are not
> added so the CLT does NOT apply.

Yes, I misread what you said.

> The EXORed output still has a uniform (1
> or 0) non-Gaussian distribution.  The spectrum is AS white as the PRBS’s
> themselves. [Meaning: technically the PRBS takes on the spectrum (sync
> low-pass roll-off) of the sample-and-hold that is inherent in the shift
> register].

…in which case the resulting spectrum is a mixing product that aliases back 
onto itself.  That should explain how prominent tonal spurs get distributed 
around the baseband as long as they aren't harmonically related.

Not sure you want to go there, but here's a treatment of that sort of mixing 
you were mentioning in the context of cryptanalysis:

https://www.rocq.inria.fr/secret/Anne.Canteaut/MPRI/chapter3.pdf

It only ever touches the subject of the spectrum by way of doing correlation 
analysis via an FFT.

I seem to remember a paper about the spectrum of sub-sequences of an LFSR (the 
spectrum is only ever guaranteed "white" to the degree possible if you look at 
multiples of the whole sequence), but can't seem to find it.  I also think 
that it was related to Bruijn sequences, but I may have misremembered that.

Anyway, it's known that non-maximal-length sequences have colored spectrum and 
there have been various attempts to use that property in (test) signal 
generation. There will generally be several possible sequences depending on 
the initial state if you implement this with an LFSR, at least two of them 
periodic.


Regards,
Achim.
-- 
+<[Q+ Matrix-12 WAVE#46+305 Neuron microQkb Andromeda XTk Blofeld]>+

SD adaptations for KORG EX-800 and Poly-800MkII V0.9:
http://Synth.Stromeko.net/Downloads.html#KorgSDada