Pseudorandom Noise Generators

[R.G.]

This has been a longstanding interest of mine, from the 1980s on. I was a fan of the MM5837 (did I get that number right?) noise generator, even with its two-second repeat.

I ran into a need for one recently, and got out my old, dusty code. I found I didn't actually have the chip that I had programmed that on, so I got sucked into a code rewrite, got interested, looked up some references, including the very useful info on Electric Druid's page.

I like L O O O O N G sequences, so I got into looking at how one might pick a good primitive polynomial that was easy to implement, gave a long sequence, and adapted well to the simpler and cheaper PICs. E.D.'s page reminded me of Scott Dattallo's "vertical arithmetic approach"  - I've used this before to debounce eight input lines for a PIC simultaneously.

E.D., I did try to follow your vertical approach to shift registers, got distracted and lost my concentration, and just dove back into my coding. I came up with something I think is different, and that you may like as well or better.

First, pick a good polynomial for a maximum length sequence. The Xilinx  LFSR page (https://www.xilinx.com/support/documentation/application_notes/xapp052.pdf) is a kind of a bible for this kind of thing. Being a lazy coder, I looked for sequences which could be both maximum length and needed only two feedback bits, not four. I noticed that these tend to appear at lengths where N is either one less or one more than two to the N power. Again being lazy, I picked some likely sequences where N was 15 (i.e. one less than two to the fourth), 23 ( one less than 3*2³), 31, 47, 63, and 71; all one less bit than an even number of eight bit register bits.

I also picked polynomials where the second feedback bit was in the highest order byte. This let all the mat work be done with only a reference to the highest order byte in the shift register string, without multiple loads.

The simple implementation using ROLF FILE, bit instructions, which rotates through the carry bit, let you do the simple shift register by simple sequential ROLF SR_0 through ROLD SR_N/8, which is very efficient of instructions.

So far, so good. A bit of optimizing and tinkering got the feedback bit computation down to four or five instructions, and after that you only need one instruction per byte. On a PIC with a 16MHz internal clock, this lets you put out random bits at over 200kHz, giving a good range for flattening and pinking filters with a range all the way to the top of audio.

But back at that vertical arithmetic stuff. I tried rearranging the code for eight LFSRs in parallel, and got lost in the weeds. It's tough to do this in low-end PIC assembly. I realized that what I needed was a vertical array of N bytes for the registers, and pointers.

Doing pointers in the 12 bit or 14 bit instruction set and doing them fast and efficiently was beyond me. But there are 8 pin PICs with the "enhanced to support the C language" instruction set, and that difference seems to be native instructions for pointers with auto increment, decrement, offset and so on.  Once I started hacking on the enhanced set, I had my LFSRs done in short order. With pointers, there are no actual movement of the bits in the registers - you just point to the "active" place in the LFSR, moving the pointer, not the shift register bits. No shifts or roll instructions.

Originally I did only one vertical bit slice; when that worked, the only difference in bit slices is where the contents of the bit slice happens to be in the maximum-length sequence.

So finally, it looks like this:
- for an N-bit LFSR, use N+1 contiguous RAM byted.
- use a start pointer and an end pointer, the end pointer being the (N-1)th bit of the register at the moment.
- the start pointer and end pointer are separated by one unused bit, which called the "hold bit".
- having previously picked N and the polynomial correctly per above, you only need to work with the bit at the end pointer and the feedback bit which will be guaranteed to be an offset of less than seven away from it. These two bits give you the feedback bit.
- generate the feedback bit by loading W from the end pointer, XORing the offset feedback bit into W, and then storing W in the hold bit location.
- since the number of bytes is N+1, the start pointer is always one less than the hold bits location, and the tail pointer is always one more than the hold location.
- if you set it up this way, the hold location is the correct position to be the new start bit when you increment the pointer.
- so by working with only ONE pointer and always using offsets of less than seven one pointer lets you do all the math without changing the pointer
- you can pick any of the bytes as the output word; the hold bits location is handy as it's already in W for transfer to the output latch, saving another load and save.
- If you seed the eight parallel LFSRs "well", the values they contain in the maximum length sequence are far away from each other, and are effectively uncorrelated, although strictly speaking they are 100% autocorrelated at some shift; but for noise generation,  you're good. The ear can't "autocorrelate" for that long.
- I spent some time thinking about how to do the pointer rollover. It would be ideal if you could simply have the pointer register roll over at any value. Sadly, it does not. But picking a length N = 2^N-1 guarantees that you can do the pointer rollover with only and AND mask on the high order pointer register bits. This point would be obvious to someone who's really good with code, but I had to struggle to get here.
- this approach leaves you free to pick N as large as you like, subject only to needing for it to be efficient enough to compute the feedback bits easily. A baby PIC like the 16F15313 is an eight pin device with the C-language enhanced instructions that let you do pointers efficiently.

And it wasn't until I realized that last that I really grinned. The number of instructions to generate a vertical LFSR with a length of 63 is identical to the number of instructions needed for a vertical LFSR of 31, and also for 15. The number of instructions is irrelevant; it's the same every time. So you're free to pick N any size where N+1 is an even power of 2.

That gets profound when you do the timing math.

A PIC executes an instruction every four clocks. So a 16MHz PIC ticks off instructions every 250nS. The instruction loop for the byte-wide vertical LFSR is 18 instructions IIRC, including outputting the result. So the loop time is 18* 250nS = 4.5uS, 222,222hz.

How long the sequence is before it repeats is 2^N-1 for a maximal length. If I did the math right, using
N = 31 ==> 214,748,3647 states. You're executing one of these every 4.5uS, so one "repeat" takes 9663.676... seconds,
161 minutes, 2.68 hours. Not bad. I won't remember the slight "repeat" two and a half hours later.

But the baby PIC has more RAM bytes. If I make N be 63, that's 9.22E18 states. Dividing by 3600 gives hours: 2.562E15 hours; 1.07E14 days; 2.922E11 years; that's over 292 million years. By that time, the batteries will have run down.    
By picking seeds that are separated in the maximum length sequence by a million years or so, we can be pretty sure the auto correlation won't be noticed.

[EBK]

If you want a really good pseudorandom noise generator, start a thread here about Mammoth Electronics and stand back.   

[PRR]

> both maximum length and needed only two feedback bits, not four. I noticed that these tend to appear at lengths where

Lancaster's CMOS Cookbook has a passage on this theme. Probably looks antiquated now. The Xilinx table goes much further. Everybody should have CMOS Cookbook on the shelf, but here's the key table.


As long as your PIC is hot, the next pages of CMOS CB cover sine generation with shift-register and a fistful of resistors.

[R.G.]

Yep, Lancaster's book was one of the early inspirations for this. My copy of the CMOS Cookbook has an honestly-gotten break in the spine on that page.

I've done several variants before. What got me on this one was the ability to make enormously long sequences with the literally same code that does shorter ones.

In fact, given enough RAM bytes and a big enough pointer register, the thing that actually sets the LFSR length is the code that forces the pointer register to roll over at some point. The pointer register simply increments, and each loop has references to pointer plus or minus some offset. What really sets the length of the LFSR is the truncation operations on the pointer register. There's no other reference in the code, no counters for where the pointer is, nothing. The limit on the LFSR size is simply the masking off of high bits on the pointer register whenever the pointer is updated. Nothing changes in the code except the truncation of the pointer register, so no timing changes, nothing else changes. It takes no longer to shift any length of "shift" register, because the bits never move. All that changes is that there is a localized frenzy of bit manipulation relative to a pointer that trundles endlessly around the length of the storage RAM.

I don't think I'd have ever gone down this path without previously noting that good-ish LFSR lengths were often a power of two, minus one. I suspect there is some profound math underlying this, at some depth, but it's beyond me. For me, it was a just a nugget I stumbled onto.

[highwater]

Dang, y'all are reminding me of what I used to like about programming back when straight C with inline assembly code poking at VGA registers wasn't considered a security risk. Makes me want to buy an Atmega board with an LCD and see what kind of retro-demoscene-madness I can come-up with. Or a PIC, just because bitwise pointers(!?!) sounds like just my kind of crazy.

--

I suspect there is some profound math underlying this, at some depth, but it's beyond me. For me, it was a just a nugget I stumbled onto.

IIRC, it's basically that an LFSR will always have at-least one state (canonically, all zeros) that it freezes on. A less-well-designed one can freeze in more than one state. A really bad one can freeze in more states than it will cycle in.

The brain-twistingly-complex mathematics are (I assume... I don't understand them) more a matter of how to arrange the feedback so you can be absolutely sure it won't get stuck.

[R.G.]

You're correct - the classical description is that LFSRs will hang at all 0s. Actually, it depends on the feedback logic and the style and the format, whether Fibonacci or Galois. An LFSR with XOR feedback locks up at all 0s, one with XNOR feedback locks at all 1s. You can implement equivalent-function LFSRs with an overall external feedback (the F-form) or feed just the output bit back into several stages with XOR/XNORs in front of each stage that gets a feedback bit (the G form). Turns out that The F and G formats can be transformed into the other.

What was nagging/amazing me was that I was looking for "primitive polynomial" impmenentations ("primitive polynomial" = "gives a maximum length sequence") that could be done with only one XOR, two feedback bits. Not all lengths N have a two-term feedback to give a primitive polynomial. Of the ones that do, there always seems to be one at even powers of two plus or minus one; moreover, the exact powers of two never seem to have a two-term polynomial. For instance, sixteen is 2⁴ and only has a four-term primitive polynomial. But 15 and 17 both have two-term feedback primitive polynomials.

From just staring at the tables of LFSR polynomials, this is true around 16, 32, 64, etc.; however, these are not the only lengths that have two-term feedback. Notice that 23 and 25 do as well, as do 47 and 49 and 71/73. These three occur at multiples of eight bits, so my brain highlighted them for me when I was first looking for lazy-coder implementations for byte-long variations. But the required work for making them work with the vertical bit-slice simultaneous LFSRs was complicated, as it required actual arithmetic to make the pointers roll over/back when doing pointer math. It could be done, but ate a lot more instructions (equals slower output speeds and a lower "flat spectrum" frequency limit" to do. Doing a simple mask of pointer high bits was easy and fast. To me, it seemed that it would be easier (and more lazy  ) to pad the LFSR length up a bit to and even power of two to make pointer computation simple - especially since there was no particular cost to just using more RAM as long as it was available.

But my simple wonderment was - WHY does there seem to be a two-term primitive polynomial at one more and one less than a power-of-two length? And what about those one more and one less than even bytes? Bytes are arbitrary, how could nature know bytes are "special". Is this related to the spacing of primes? My simple mathematical background got lost somewhere on the next step with the conjecture that it's related to prime-ness of 2^N +/- 1, which is often, but not always prime.

I never was much good at math.

[ElectricDruid]

Very interesting stuff, RG! Thanks for sharing your thought on it.

I'd never thought of doing the vertical LFSRs on a "bit-sliced" basis. Instead, I was looking at what happened when you did eight operations together on a standard byte-by-byte representation of the shift register. Turns out that (if you have the taps in the right places) you can do whole-byte operations to effectively do eight sets of XORs in one go. This gives you a *whole byte* of new data each time instead of a just a single new bit. It's a way of rolling eight sets of shift operations up into a single big operation instead. Turns out it uses significantly less instructions that way.

Since I'd never considered doing a LFSR with a bit-per-byte (or eight in parallel...), I'd also never considered using pointers to move the bits around. As soon as you adopt that representation, it obviously makes a lot of sense to do. As you say, the "enhanced" PICs with the extra instructions are a massive step forward, and I use them almost exclusively these days. The two different pointers make a lot of stuff much easier, and they finally have a proper Add-with-carry instruction (it's taken a while...) and other improvements.

I've recently been working on doing pink noise generation, using the Voss-McCartney algorithm, and while I thought I'd made the code pretty efficient, I'm now going to go back and revisit it to see if I can't use any of your ideas to shave a bit more out of it!

Finally, one word of warning, although you're not likely to hit this on the PIC: there was a discussion recently on the SynthDIY mailing list about using very long LFSRs for the generation of audio noise, and several people suggested that very long bit lengths aren't a great idea, the reason being that they are statistically certain to have long periods of repeated bit sequences that we hear as tones, as well as periods of "silence" where we get a long section of all ones or all zeros. Obviously with 16-bit, 32-bit, 64-bit registers, these periods aren't going to be very long at audio sample rates, but if you start pushing thing up to lengths that are easy to do on a modern PC you can cause yourself more trouble than you thought.
Since I'd always done this sort of stuff on lower-spec processors, this had never occurred to me, but it makes sense as soon as you consider what a very-long-LFSRs output sequence looks like.

Tom

[R.G.]

Good - I was hoping it might spark some ideas.

I was (dimly) aware of the periods-of-silence thing, but in a slightly different way. I have always been as interested in very low frequency randomness as much as higher frequency hiss and such. In my mind, repeating LFOs are OK, but modulation with a mildly irregular LFO is much more ear-catching. So one of my objectives was to generate sequences with outputs low enough to be an interesting replacement for an oscillator LFO.

This can be done two ways, of course. Simply slowing down the output sample rate and running things slower in general gives you "randomness" to a lower real-time clock rate, and the slower clock also means that the ear-memory for repeats gets bypassed, being much less noticeable. The other is to make the LFSR longer, since the longest all-0s or all-1s sequence is either N or N-1. So in my mind, extending to higher N gives a lower frequency limit at the same time as preserving more nuances of wandering on top of the lowest "wander" frequency out of the LFSR.

As a practical matter, it probably makes no difference, as wind and surf synthesizers work fine with a few non-harmonically related oscillators doing the modulation. And, as you note, I'll probably never go for really long LFSRs. Maybe if I was interested more in crypto, or some such, but for simply noise/random generators, something under N = 100 is more than I'll ever need.

It reminds me of the Space Child's Mother Goose - Little Jack Horner sat in a corner, extracting cube roots to infinity...

[Rob Strand]

I like the idea of not shifting the bits.

As a practical matter, it probably makes no difference, as wind and surf synthesizers work fine with a few non-harmonically related oscillators doing the modulation. And, as you note, I'll probably never go for really long LFSRs. Maybe if I was interested more in crypto, or some such, but for simply noise/random generators, something under N = 100 is more than I'll ever need.

That's the problem with this stuff.   If the requirements are low you can use a single LFSR but if the requirements are high you need a state of the art generator.   The real world is somewhere between those extremes, which is somewhere between the Sun and Alpha Centauri.   Soon as you make a compromise there's always room for improvement, the improvements are usually known, so where do you stop!

One of the "better wheel" LFSR's is the twisters (fairly popular these days),
https://en.wikipedia.org/wiki/Mersenne_Twister

[ElectricDruid]

so where do you stop!

Actually, it turns out deciding where to stop is one of the easy bits! For the Pink noise generation, I had a PIC running at 32MHz max clock speed, which represents a 8MHz instruction cycle. If you want a 100KHz output rate, you've only got 80 instructions per-sample. 100KHz *sounds* pretty high, right?, since 96KHz is top quality audio, but in reality for noise generation, you can expect some drop-off in the frequency response well before you hit the half-sample-rate point  (AKA Nyquist frequency) so if you want a nice flat response for your white noise or a nice even response for your pink noise, it's a good idea to keep the sample rate as high as you can. So I've got basically 80 instructions to do all the calculation required to generate the next sample. That provides a *very hard limit* on what can be done. Furthermore (just to add to the fun) if you want the sample rate to be consistent (You do. You really do...) then you need to make sure that every possible path through the code comes out at the same number of instruction cycles.
This kind of craziness is what we do and what we love. That's the way it goes...

T.

[Rob Strand]

I was actually thinking about the quality of the generator (in terms of randomness) than the cycle length and bandwidth.

If you want a 100KHz output rate, you've only got 80 instructions per-sample. 100KHz *sounds* pretty high, right?, since 96KHz is top quality audio, but in reality for noise generation, you can expect some drop-off in the frequency response well before you hit the half-sample-rate point  (AKA Nyquist frequency)

That's a valid way to get flatness.

Another way to approach the sinc roll-off is to use a sinc compensation filter.  That lets you get a flat response without needing a high clock rate.   Some of the modern function generator use sinc compensation since they don't have the luxury to up the sample rate to 100MHz+.  They use 40MHz or so clock then use sinc compensation filter to bump the highs back up to flat.

There's no right way.  If you have the bandwidth free there's no need to stuff around with sinc compensation filters.

[R.G.]

My reading on making Gaussian and sinc-i-fying the noise suggested both. In a real DSP, the internal sinc computation is sensible, as the hardware exists in the processor to do the filtering. In a PIC - well, it's good that we can do XORs. 

The PIC minimal approach has to be limited to computing things FAST and then using a simple RC filter to flatten the noise by attenuating the stuff above some freuqency that you think is going to be flat-to.

I was looking at only 16MHz, as the 10F2320s I had were limited to that. This consideration was what was behind those number-of-instructions and output frequency things I mentioned. Looks like with the six pin SOT-23 (!) baby PICs, you can get to 200k - 250k output sameples per second, and then one-pole RC limit back down to the audio band pretty simply. I still have a kind of childish wonder at parts today, having spent decades being limited in designs by parts - not being able to get parts that were fast enough or big enough. Being able to make a years-long sequency generator in a package smaller than a TO-92 makes me grin.

Sadly, the SOT-23 PICs don't (...yet) have native pointer instructions, so I can't go implement 200KHz+ samples with three uncorrelated outputs in that same $0.50 SOT-23-6. The limits imposed by simple RC filtering to flatness mean you have to output samples at about 10x the highest flat spectrum frequency, and the limit of 16Mzha clocks (and 4MHz instruction rate) mean you have a budget of aobut 20 instructions for the sample generation loop.

@E.D. - I don't have the math background to quickly estimate the effect of slightly varying loop lengths and the resulting sample time jitter on the output spectrum. I suspect that it shows up as phase jitter in the output spectrum, but that is just a guess. I got around it in this instance by forcing the code to not have any conditional branches, which forces all loops to have the same number of clock cycles. I got to that in the vertical blt-slice version by not doing arithmetic on the pointer register, limiting myself to a simple masking operation on every mask change. That forced the execution times to bv the same (I think...). This is all highly PIC specific, of course. I started looking at the eight pin AVR parts a little, and it seems like they might have a more-native instruction set that handles the pointer case better.

@PRR: yep, sine generation from the CMOS Cookbook is another love of mine. I had that in mind for octave generation with PLLs in the octave-up-and-down scheme in a post here. It was some time ago.  The scheme was to PLL to a note using a divider inside the PLL feedback to multiply in octaves, then use the divider outputs to sum to triangles or sawtooths for more audio friendly outputs. Of course, sawtooths are not sines, but I also had in mind using Johnson counters as feedback dividers for the PLLs. That would give sine-ish outputs directly. The logic part gets complicated pretty fast though any you're fighting PLL acquisition and tracking for wide range locks with higher dividers.

Sigh - so many designs, so little time.

[ElectricDruid]

I have always been as interested in very low frequency randomness as much as higher frequency hiss and such. In my mind, repeating LFOs are OK, but modulation with a mildly irregular LFO is much more ear-catching. So one of my objectives was to generate sequences with outputs low enough to be an interesting replacement for an oscillator LFO.

One way to do this would be to use the LFSR to modulate an LFO's frequency. The basic plan would be "if it's a one, go up in frequency a little bit, if it's a zero, go down in frequency a little bit". This is essentially setting up an integrator for the LFSR values, and then using the integrator output to frequency-modulate the LFO. E.g. we have filtered noise for the LFO FM. Add "leaky integration" for bonus points and to stop the output drifting off too far (statistically unlikely, but you never know). The "leakiness" would give a measure of the "mildly irregular" over the "highly irregular".
This idea turns up in Thomas Henry's book about noise generators, although he was thinking of analog circuits, not firmware.

I suppose another way would be just to use the integrator output ("random walk"?) output directly, but the advantage of the modulated LFO is that you know what modulation depth you're going to get. Some random techniques produce very variable levels with the modulation sometimes very shallow and sometimes very deep.

I've done a lot of experiments in this area, since (like you) I prefer modulations that aren't entirely predictable. Random frequency modulation of an otherwise pretty normal LFO is one way to go, but you can also generate random waveforms a lot of other ways. Here's a link to some earlier ideas I worked on, a combined LFO/random generator.

https://www.electricdruid.com/AdvancedModulationGenerator.pdf

Hope it sparks a few ideas in return!
Tom

[DIY Bass]

I must admit I don't fully understand it, but some of the hardware random number generators based on reverse biased transistors look pretty cool.

[anotherjim]

Random is such a fuzzy concept, that my brain rebels at the idea that it can be formularized. Especially if it requires terms I don't recognise.

Yes, I would reverse zener a transistor too, even if it means adding a boost converter to get enough voltage to make it happen.
I'm also kind of baffled by the CD4006. It's been obsolete a while but continues to be required in all kinds of clones. It's a shift register, so is there no replacement logic device? Even if it means extra chips to equal the 4006's stage length.

[ElectricDruid]

Random is such a fuzzy concept, that my brain rebels at the idea that it can be formularized. Especially if it requires terms I don't recognise.

Ok, fair enough. It's a fair cop. We're really discussing "pseudo random number generators", not *genuine* random sources like the transistor. Random can't be formularised, but you can generate something that is statistically indistinguishable for a specific purpose.
So in the case of LFSRs, they actually generate a fixed pattern of bits as an output, but the pattern is so long and complicated that it looks and acts like it's random. But it's not: if you go back to the start state and run it again, you get the same sequence.

Yes, I would reverse zener a transistor too, even if it means adding a boost converter to get enough voltage to make it happen.

The trouble with transistor noise sources is that not every transistor is good for it, and the levels are usually very low, so then you need high gain to boost it, and that can introduce other problems or amplify mains hum or whatever else.
The great thing about LFSRs is that they're reliable and they produce a decent output level. And with tiny processors like the 6-pin thing RG's been using, they can take up less space than a reverse-biased transistor and its amplifier.

I'm also kind of baffled by the CD4006. It's been obsolete a while but continues to be required in all kinds of clones. It's a shift register, so is there no replacement logic device? Even if it means extra chips to equal the 4006's stage length.

There are plenty of shift register chips out in the world, but I don't know if they're pin-compatible. Sounds to me like people are still building circuits that have been kicking around for 25 years (who'd have thought it?! ).
Still, I wouldn't build a LFSR using hardware. For me, it's a bit pointless. You can do the exact same thing on a single chip processor, so why use a handful of hard-to-find obsolete discrete logic to do it?

Tom

[R.G.]

I loved this one:
https://assets.amuniversal.com/321a39e06d6401301d80001dd8b71c47

A sequence of a thousand zeroe - or more! - can and in fact must be part of a truly random sequence. But no human would think that was actually random.  Real randomness is HARD.

As E.D. referred to, the cd4006 is an 18 stage shift register in a 14 pin DIP. It requires at least one external XOR package, that being a 14 pin DIP if you want to do through-hole. It could produce a pseudorandom sequence at best twice as long as the MM5837. It also needs a clock oscillator, perhaps a CMOS 555 for another 8-pin DIP, perhaps part of the XOR package if you do simple polynomials with only one XOR needed.

Compared to that setup, an 8-pin DIP PIC can produce a pseudorandom sequence that is effectively unlimited in length - to unaided humans at least. There are computer-based encryption cracking attacks that can deduce the generating polynomial from a long enough sample of the sequence, but for audio noise purposes, the ear can't tell the noise from random.

The CD4000 family can run faster, a few MHz at least, but that runs you through the sequence faster too, so the ear-memory beat is closer together. PIC based ones will top out at about half a MHz, but again with an unlimited sequence. PICs can't run from 9V or 12V like CD4000 stuff can, so the PICs in a 9V environment will need at least a 3V to 5V zener to produce their power supply. So the baby-PIC can be one 8-piun DIP plus a zener or transistor base-emitter used as a zener. PICs also come in SOT-23-6 packages, like the 10F320 I was using. This is smaller than a TO-92, and feasible to build into a fake TO-92-sized blob.

Compared to reverse-transistor zeners, the PIC approach gets you a TO-92 equivalent package for the noise generator, but needs a diode or another TO-92 to do its power supply, and produces a 5V (i.e. power supply) sized string of random bits that can be turned into half to one volt of analog noise with one resistor and one cap. The reverse transistor approach produces millivolts of noise that needs an opamp plus ancillary parts to amplify it up to size to get usable noise levels.

[Child's Garden Of Wonder Alert]
It struck me in writing this up that a million-bit long - shoot, a zillion-bit long - sequence of bits is just a symbol. "Zero" is a symbol, as is "one". We know that o and 1 repeating some number of times is a feature of pseudorandom sequence generators, and in fact must be part of truly random sequences.

Given that, how  could you ever distinguish a series of exact repeats of a million-bit-long sequence from a truly random sequence? A truly random sequence must contain strings of repeats of million-bit-long sequences as part of its truly random pattern at some point in the sequence.

Sure, this is just a rehashing of the Dilbert "nine, nine, nine, nine, nine, nine....", but it's a variation I hadn't thought of til now. Those "nines" could be gigantic strings of apparently-random bits.

Randomness is HARD.

[PRR]

> hardware random number generators based on reverse biased transistors look pretty cool.

They work, usually. They always have 1/f bass-rise; this may be good for the Druid who likes long-term extra randomness.

It occurred to me a while back that in today's world, a TL072 rigged as two high-gain amplifiers would boost its own hiss to line-level, for 19 cents and one chip. The hiss of TL072 is not tightly specified, and will vary between production runs. But it can't be "low" (basic physics) and if it is high the wafer would normally be rejected (or sold to back-alley fake-parts merchants). And if you buy a baggie all at the same time they may be very consistent down to the last crumb.

This will also have resistor hiss. You can design for more R-hiss, lessening the contribution of the Silicon, but the high impedance invites ambient crap (hum/buzz, signal, radio).

All analog parts show 1/f noise. The TL072 is OK but not great. There are $$$ parts with specified low 1/f corner. The resistors also have 1/f, and low-% resistors won't be specified.

For jiggling a Synth, I would think a shielded breadboard and an hour of part-rolling would give a fine result.

[R.G.]

In this one case, new old stock parts might be a good idea. If you can actually find 741 opamps made in the 1970s, they will be as noisy as you're likely to get an opamp being. A dual "741" would even give you another opamp to amplify the noise.

On the other hand, a current-production PIC 10F320 costs $0.51 as of a few seconds ago, and Mouser has 13,573 in stock.

I think the real issue with going discrete versus using a controller is the same old one - there is a hump to get over in programming the part, plus changing to something different.

As an aid to those struggling with coding (that's not a dig; PIC code isn't always easy!) here's the code for the N=63 case. It's by no means optimized, so no guarantees.
Code copyright 2019 R.G. Keen. Permission given for personal use in making up to 20 units.

Inner loop is 17/18 instructions depending on whether the BTFSC instruction doing the effective XOR takes a skip or not. On average, it will be 17.5 instructions as about half the time the test bit will be 1, but this is highly position dependent in the bit stream.

Short version, mostly comment stripped:

Code Select Expand


;===============================================================================
; PIC Noisemaker
; generates a maximal length pseudorandom sequence of 2^63 -1 states
;===============================================================================
; copyright 2019 R.G. Keen permission given for personal use for less than 20 units
list      p=10f320            ; list directive to define processor
#include <p10f320.inc>        ; processor specific variable definitions
__CONFIG _FOSC_INTOSC & _BOREN_OFF & _WDTE_OFF & _MCLRE_OFF & _CP_OFF & _LVP_OFF & _LPBOR_OFF & _WRT_ALL
ANSELA equ 0x08
ADCON equ 0x1F
ADRES equ 0x1E
SR63_0 equ 0x60
SR63_1 equ 0x61
SR63_2 equ 0x62
SR63_3 equ 0x63
SR63_4 equ 0x64
SR63_5 equ 0x65
SR63_6 equ 0x66
SR63_7 equ 0x67
HOLD equ 0x40
OUTPUTBYTE equ 0x41
TEMPREAD equ 0x42
;**********************************************************************
ORG     0x1FF             ; processor reset vector
        ORG     0x000             ; coding begins here
MOVLW 0xBC ; seed byte in W
MOVWF SR63_0 ; seed byte in shift reg 0
MOVLW 0x35 ; seed byte in W
MOVWF SR63_1 ; seed byte in shift reg 1
MOVLW 0x5F ; seed byte in W
MOVWF SR63_2 ; seed byte in shift reg 2
MOVLW 0x3D ; seed byte in W
MOVWF SR63_3 ; seed byte in shift reg 3
MOVLW 0x9A ; seed byte in W
MOVWF SR63_4 ; seed byte in shift reg 4
MOVLW 0x42 ; seed byte in W
MOVWF SR63_5 ; seed byte in shift reg 5
MOVLW 0xF2 ; seed byte in W
MOVWF SR63_6 ; seed byte in shift reg 6
MOVLW 0x72 ; seed byte in W
MOVWF SR63_7 ; seed byte in shift reg 7
CLRF ANSELA ; clear ansela, all pins are NOT analog inputs
MOVLW 0xF0 ; load W with TRIS data for the I/O port
; only bit ra2 is output
MOVWF TRISA ; and W into TRIS reg - bit GPIO.0 is now output
; previous is setup, only the following loop repeats
Carry_Calc:
RLF SR63_7, W ; put high byte in W, rotated 1 bit left
MOVWF HOLD ; store in hold byte
BTFSC HOLD, 6 ; test bit 62 for clear
COMF HOLD, F ; complement W bits if SR_63 bit 6 = 1
; does XOR with W high bit
RLF HOLD, F ; rotate feedback Bit into carry
RLF SR63_0, 1
RLF SR63_1, 1
RLF SR63_2, 1
RLF SR63_3, 1
RLF SR63_4, 1
RLF SR63_5, 1
RLF SR63_6, 1
RLF SR63_7, 1 ; eight bytes done
MOVFW SR63_0 ; get output byte into W
MOVWF LATA ; and put all the bits into the output latches
; only bit 0 comes out to the pin due to tris setting
GOTO Carry_Calc
        end
; ====
Long version, more comments.

Code Select Expand

;===============================================================================
; PIC Noisemaker
; generates a maximal length pseudorandom sequence of 2^63 -1 states
; as a feedback shift register
;===============================================================================
; copyright 2019 R.G. Keen
; permission given for personal use for less than 20 units
;-------------------------------------------------------------------------------
; Notes:
; Uses 4 memory bytes as one 32 bit shift register.
; the top byte is used for feedback bits; use lfsr-2 feedback for simpler/faster
; calc of feedback.
; For N up to 64, the longest prime primitive lfsr-2 is 63 bits feedback from
; 63 and 62.
; Output of one of the bits is on GP.2
; language is Microchip's free assembler in the free MPLAB coding suite.
;===============================================================================
; Fuse Configuration
list      p=10f320            ; list directive to define processor
#include <p10f320.inc>        ; processor specific variable definitions

__CONFIG _FOSC_INTOSC & _BOREN_OFF & _WDTE_OFF & _MCLRE_OFF & _CP_OFF & _LVP_OFF & _LPBOR_OFF & _WRT_ALL
;===============================================================================
; Hardware Configuration
;-------------------------------------------------------------------------------
; auxillary register defns
ANSELA equ 0x08
ADCON equ 0x1F
ADRES equ 0x1E
; Variable Declarations
; need definition for SR63_0 through SR63_7
SR63_0 equ 0x60
SR63_1 equ 0x61
SR63_2 equ 0x62
SR63_3 equ 0x63
SR63_4 equ 0x64
SR63_5 equ 0x65
SR63_6 equ 0x66
SR63_7 equ 0x67
;
HOLD equ 0x40
OUTPUTBYTE equ 0x41
TEMPREAD equ 0x42
;**********************************************************************
ORG     0x1FF             ; processor reset vector
; Internal RC calibration value is placed at location 0x1FF by Microchip
; as a movlw k, where the k is a literal value.
        ORG     0x000             ; coding begins here
;================================================================
;Initialization
;================================================================
; Set up oscillator. Use fastest possible for fastest output samples
MOVLW B'01110000' ; load literal for OSCCON running at 16MHz
MOVWF OSCCON ; set up oscillator
; Seeding
; make up a seed from prime numbers and such.
; following is 256 bit from a password generator
; 9e 70 bc 35 5f 3d 9a 42 f2 72 fe bd 71 95 87 69
; c3 20 43 8a 82 fa a5 f6 58 fb 23 5c 39 e1 a9 2e
MOVLW 0xBC ; seed byte in W
MOVWF SR63_0 ; seed byte in shift reg 0
MOVLW 0x35 ; seed byte in W
MOVWF SR63_1 ; seed byte in shift reg 1
MOVLW 0x5F ; seed byte in W
MOVWF SR63_2 ; seed byte in shift reg 2
MOVLW 0x3D ; seed byte in W
MOVWF SR63_3 ; seed byte in shift reg 3
MOVLW 0x9A ; seed byte in W
MOVWF SR63_4 ; seed byte in shift reg 4
MOVLW 0x42 ; seed byte in W
MOVWF SR63_5 ; seed byte in shift reg 5
MOVLW 0xF2 ; seed byte in W
MOVWF SR63_6 ; seed byte in shift reg 6
MOVLW 0x72 ; seed byte in W
MOVWF SR63_7 ; seed byte in shift reg 7
;=================================================================
; initialize A-D
CLRF ANSELA ; clear ansela, all pins are NOT analog inputs
; initialize output ports.
MOVLW 0xF0 ; load W with TRIS data for the I/O port
; only bit ra2 is output
MOVWF TRISA ; and W into TRIS reg - bit GPIO.0 is now output
;------------------------------------------------------------------------------
; Main Task: everything down to here is setup; following code repeats forever
;-------------------------------------------------------------------------------
Carry_Calc:
; Do another shift operation, and then output the bit value.
; carry calc for 63 bit

RLF SR63_7, W ; put high byte in W, rotated 1 bit left
MOVWF HOLD ; store in hold byte
BTFSC HOLD, 6 ; test bit 62 for clear
COMF HOLD, F ; complement W bits if SR_63 bit 6 = 1
; does XOR with W high bit
RLF HOLD, F ; rotate feedback Bit into carry
RLF SR63_0, 1
RLF SR63_1, 1
RLF SR63_2, 1
RLF SR63_3, 1
RLF SR63_4, 1
RLF SR63_5, 1
RLF SR63_6, 1
RLF SR63_7, 1 ; eight bytes done
MOVFW SR63_0 ; get output byte into W
MOVWF LATA ; and put all the bits into the output latches
; only bit 0 comes out to the pin due to tris setting
GOTO Carry_Calc

; ====

                end


[ElectricDruid]

It looks to me like it'll be a constant 18 instructions, R.G.

Those BTFSC/BTFSS instructions are very cleverly arranged so that if they skip over the next instruction, they take two instructions, but if they don't, they only take one. The net result is that the branch+the next instruction always takes two. The only difference is whether the next one is the following instruction (COMF in your case) or just a NOP ("no operation" for the non-assembler speakers amongst you).

At 18 instructions with a 16MHz clock, that's running at over 220KHz. Won't repeat for, what, 2.6 million years?...Nice work, RG