[sdiy] Long LFSRs (Was Psych Tone)
Bernard Arthur Hutchins, Jr
bah13 at cornell.edu
Sun Jan 13 20:45:08 CET 2019
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.
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:
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.
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.
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?
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.
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.
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.
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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Synth-diy