# [sdiy] Long LFSRs (Was Psych Tone)

ASSI Stromeko at nexgo.de
Tue Jan 8 20:15:31 CET 2019

```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.

> 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: