[sdiy] Long LFSRs (Was Psych Tone)

[Magnus Danielson]

Hi Bernie,


I find that a subject I looked at many years ago has re-surfaced here at 
Synth-DIY, fun times.


On 2019-01-13 20:45, Bernard Arthur Hutchins, Jr wrote:
>
> A Good Project ?
>
> I am not an abstract mathematician although I do understand 
> “engineering math” pretty well, and have thought a good deal how this 
> all applies to a particular “application”; a particular “receiving 
> system” – the human ear/brain.So to be more productive, let’s 
> transition from abstract math to engineering math (with its familiar 
> terminology) and thereafter to perceptual and aesthetic aspects of 
> PRBS generators (the design aspects being fairly clear).To discuss one 
> notion of some importance to us, what does the “spectrum” look like?Is 
> it “white”?
>
> Any perceived spectrum must pass the physical windows of being limited 
> in frequency to about 20 Hz to 15 kHz, and in time to a duration of 
> perhaps 100 milliseconds per “frame” (“time constant of the ear”). 
> Recognizing that reasonable length PRBS sequences (say N=24 so that 
> 2^N-1 approaches 17 million), and that a frame may need to be, say, 
> 4410 samples for 100 ms, we usually achieve a reasonably white hiss 
> for each frame.It works.[There is a slight roll-off (reaching -4db) at 
> half the sampling frequency due to the hold time of the shift register 
> clockings.
>
> Problems are expected if the shift register is too short (say only N=5 
> so that 2^N-1 is only 31 and thus repeats at something like a kHz – 
> strongly pitched.Or, as Richie’s N=127 demonstrated, apparently it can 
> be way too long to avoid very audible traps.And any remaining problems 
> can likely be handled by EXORing the longer sequence with a shorter 
> one, as discussed above.So the problem of getting a reliable white 
> noise generator is under control, and this noise can be additionally 
> filtered (perhaps with a bandpass VCF) as desired.
>
We must recall that any of these methods is only pseudo-random, and what 
is good enough so much depends on what we need it to do for us to 
perceive it as a good replacement of a true random source, where the 
benefit would be in implementation form and avoiding issues.


The repetition rate is one known limit, if it repeats to often, a form 
of beating pattern is experienced. Some of the older analog synths had 
that issue but later used pseudo-random patters being longer. I ended up 
listening to such patterns when working professionally to measure the 
impulse response of speakers, so it is all to apparent sound memory to 
me, I even miss it now.


The other end of the spectrum is the density, if it is not dense enough 
narrow filters sweeping slowly would pick out single spectrum tones 
rather than narrowband noise.


Both these is addressed by having long enough sequence, and long enough 
sequence isn't all that expensive to achieve, so there is no real 
excuse. The needed pattern to achieve it is a needed input, but that can 
be tabulated and we have seen some useful once passing by already.


A third aspect is to ensure that it goes high enough, and that is really 
down to clock frequency, and if you have a long enough pattern there is 
no real excuse to keep the frequency down either.


With these basic properties addressed we should have "white" noise, in a 
spectrum sense.


> NOW........
>
> That’s HALF the story: – white noise as raw material for processing 
> into musical SOUND.The other application is the use of a PRBS to 
> generate “random tunes” (melodies) like the Psych Tone.It is unlikely 
> that we are interested in melodies of only two pitches, nor of 
> sequences as long or longer than about a dozen.As importantly, we 
> should be concerned with the DEGREE OF CORRELATION BETWEEN SUCCESSIVE 
> PITCHES- what is “traditional”?Thus, several relevant factors come in:
>
> http://electronotes.netfirms.com/EN76.pdf
>
> First we probably use a much much slower PRBS clocking rate, since we 
> probably want notes coming out (likely as control voltages to a VCO) 
> at perhaps from about 2 to about 10 tones per second.And we want many 
> more possible pitch levels (perhaps 40 or so – half a piano keyboard 
> if conventionally configured).And, as suggested, a total trial 
> sequence length of perhaps at most a dozen tones – AND we prefer it to 
> be exactly reproducible.
>
>
> Getting more than just two output levels is almost certainly a matter 
> of adding up multiple register stages.For example, we could sum 12 
> stages (12 “taps”).[This we CAN do, perhaps offering nothing really 
> new, even if the sequence length is less than 12 by extending the 
> shift register in feed-forward beyond the lasts tap fed back – just 
> delayed values of the output.]The output is thus numbered as the sum 
> of from 1 to 12 (possibly 0 to 12) ones, not just a 0 or a 1. This 
> “running sum” produces tones approaching a Gaussian distribution and 
> one that is very HIGHLY CORRELATED (low- passed). This sum is NOT 
> white (it is often termed “Red Noise”). In fact, for the next output 
> value, the SUMMED bits on the registers can either stay the same, go 
> up by 1, or down by 1.No big jumps (melodically just arpeggio 
> phrases).Likely too boring.
>
>
You most likely want to achieve the Gaussian shaping, but this is not 
recommended when running the PRBS slow, the slow rate is better achieved 
by S/H of a PRBS running at a good rate. The filtering effect wears off 
due to the short time-span of the FIR-like shaping, which extends the 
length of the PRBS generator times the clock period.
>
> Alternatives to uniforms tap weights should be considered.Here it may 
> be useful to point out that we are talking about the 
> “impulse-response” of a digital FIR [Finite (length) Impulse Response] 
> filtering. For example, binary weighing (resistors in powers of 2 
> summing – a somewhat standard “D/A”converter) can be used, but why not 
> experiment?With this weighting, a particular 1 might enter the 
> converter as a MSB (big change) and leave as the LSB (small change). 
> The distribution still approaches Gaussian and is still not nearly 
> white, a degree of low-passing correlation still apparent.
>
> Neuvo and Ku (IEEE reference in link above) used an all-digital 
> similar approach to this summing issue. They added up a “frame” of M 
> samples of the PRBS generator, latched and converted this as a “word” 
> and then went on to the next M bits, keeping none of the previous 
> sample. Thus the successive words were uncorrelated and the generator 
> as a whole was white.This was a noise generator and was a 
> cement-block-like wire-wrapped TTL tour de force. Similar Psych Tone 
> speed approaches (and more!) in software seem quite doable.
>
One technique to do Gaussian is adding a number of uniformly shaped 
samples together. 12 of these gives the RMS value of 1, which is a trick 
used in many simulations. It fails to give the long tails, so the 
Box-Mueller form is used in simulations, but is unsuitable for simple 
analog/digital setups.
>
> Another way to avoid the excessive correlation of the moving sum (or 
> even the binary weighting would be to spread the taps further apart 
> and perhaps more randomly. Also, it is unclear what the use of 
> “non-minimal length” sequences might do to correlation. But just what 
> are we looking for?
>
You never really get away from it. Operating it at the slow rate is the 
core flaw, the polynomial doesn't really help.
>
> Well first keep in mind that we want some sort of weighting to give 
> many possible pitch levels.This we get, approaching Gaussian, through 
> the summation and courtesy of the Central Limits Theorem.
>
You should be happy that Central Limits Theorem works for you here, sort 
of, in several of the hairy things I work with, it no longer applies and 
Gaussian shape goes away... but for now we can assume it.


But, the Gaussian shape, which is a consequence of Central Limits 
Theorem assumed independent samples. Now, for a pseudorandom noise they 
are not truely independent, and for the short time-scale the Gaussian 
shaping attempts makes them for sure not independent, they will have a 
filtering effect. This is the key reason you must run the pseudo-random 
sequence at a much higher rate than you anticipate to use it and it's 
"Gaussian" shape.

> Correlation is a separate issue.“White” means noncorrelated.That is, 
> without correlation a particular current pitch offers no clue as to 
> what pitch is coming next. Each new pitch is a surprise and all 
> melodic intervals are about equally likely. Filtering (making the 
> spectrum non-white), as with the “running sum” above, gives us next 
> pitches that are either the same as the current one or one step up or 
> one step down. Neither of these contrasting cases resembles our 
> ingrained experience with musical melody which is a balanced mixture 
> of fulfilled expectation and surprise.
>
>
Well, white does not actually means non-correlated. You can have two 
white noises which is correlated with each other, so it's not a good way 
to describe it. It's called "white" as it contains "all colors" evenly, 
thus it has equal power to all frequencies. For thermal noise, also 
called Johnsson noise, it will be white up to it's natural bandwidth 
roll-off frequency. Regardless of source, often "white" noise is 
non-correlated, but it can be correlated regardless if it is true random 
noise or pseudo-random noise. For the impulse response measurement, we 
use the fact that the noise is both correlated and "white" to extract 
the impulse response. With modern processing you can actually use true 
random noise as trigger and then correlate the response with the 
original noise to extract the same impulse response. We could actually 
do that before too, because the mathematical tools haven't changed, just 
our ability to real-time process it.

> Voss and Clarke [J. Acoust. Soc. Amer., “ ‘1/f Noise’ in Music: Music 
> from 1/f Noise”, Vol. 63 (1978)] and subsequent authors indicated that 
> musical tradition with regard to melody (and many other things) showed 
> an inherent 1/f POWER spectrum. That is, it was neither flat (white - 
> uncorrelated) nor was it the 1/f (Amplitude – 1/f^2 in Power) typical 
> of an integrator/summation; but rather 1/sqrt(f) usually called “Pink 
> Noise”.So with regard to a secession of tones acceptable as a melody 
> we prefer to have expectation sometimes fulfilled as well as numerous 
> surprises.
>
> A search of the Internet will produce a good deal about 1/f and pink 
> sequence and generation algorithms.Any person experimenting with a 
> software version of Psych-Tone-like structures might do well to 
> consider how PRBS sequences might relate to 1/f.
>
The 1/f power spectrum density noise, also known as flicker noise, has 
been a keen interest to the time and frequency community. Dr. James 
"Jim" Barnes at NBS (now NIST) in Boulder did research in simulating the 
1/f spectrum from white noise. His work has since inspired the 
topologies used for analog synthesizers.

His peer Dr. David "Dave" Allan was able to make sense of the statistics 
of it.


If you want to experiment with noise-types, you can download the 
Stable32 software from IEEE UFFC for free. It's written by Dr. William 
"Bill" Riley and includes simulation of these noise-types.


When doing cross-correlation phase-noise measurements, the thermal noise 
causes destructive correlation, confusing measurments and it looked like 
you had about -300 Kelvin noise temperature, which is naturally not 
physical. We now resolved how that could appear and it was only when I 
presented the cross-correlation interferometric setup that NIST could 
start to make measurement at the noise-floor, but still very hard to 
achieve.


For noise simulation, the true master would be Dr. Charles "Chuck" 
Greenhall of JPL. It can be worth searching for his papers. One of the 
few real thinkers that does the deep thoughts of the time and frequency 
field.


Anyway, make sure to keep that clock rate up, running it low is not a 
good solution.


Cheers,

Magnus

> - Bernie
>
> ------------------------------------------------------------------------
> *From:* Bernard Arthur Hutchins, Jr
> *Sent:* Monday, January 7, 2019 7:51:53 PM
> *To:* synth-diy at synth-diy.org
> *Subject:* [sdiy] Long LFSRs (Was Psych Tone)
>
> Achim said:“An EXOR is simply multiplication (given the right encoding).”
>
> True and widely understood.
>
> 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.
>
> 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.”
>
> EXOR is still non-linear in the PRBS structure – the particular 
> application under discussion here. Compare, for example, the marvelous 
> Karplus-Strong “plucked string algorithm” which is a similar-looking 
> long shift register with two weighted feedback taps at the very end 
> back to the input (typically both being ½, and ADDED).This IS linear, 
> and K-S, generalized, IS a perfectly understood linear filter in a 
> feedback loop.
>
> Next, with regard to my suggesting using a shorter PRBS sequence to 
> correct for the “tricks” played by a longer ones (blundering into 
> audible special cases that linger), Achim said: “Yes.That works 
> because whatever the original distribution(s), mixing them will 
> (rather quickly under easily met conditions) converge towards a 
> Gaussian one (says the central limit theorem).”
>
> 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.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].
>
> One last thing:By chance today I same across another PRBS reference 
> that mentions several interesting things – like the “heartbeat” issue 
> just mentioned.
>
> http://electronotes.netfirms.com/Noise2.pdf
>
> -Bernie
>
>
>
> _______________________________________________
> Synth-diy mailing list
> Synth-diy at synth-diy.org
> http://synth-diy.org/mailman/listinfo/synth-diy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://synth-diy.org/pipermail/synth-diy/attachments/20190116/3b473dc7/attachment.htm>