Generating random bits with PIC hardware

[ElectricDruid]

Does anyone have any experience generating a random bitstream with hardware on a PIC?

I think it's supposed to be possible using the CRC^* module, which includes a hardware LFSR^*, but I don't know anything about it and the datasheet doesn't include a handy diagram.

What I'm trying to do is to dither the output from the NCO^*. The idea being that dithering by XOR'ing the NCO output with a random bitstream wouldn't change the ratio of high pulses to low pulses, but would break up the repeating cyclic patterns you get with an NCO.
There's a configurable logic cell (CLC^*!) that would do the XOR for me, but I need a source of random bits that I can route to it.

Thanks!

* - initialism bingo!

[cordobes]

Hi Tom, externally with a 2n2222 injecting avalanche noise, or internally taking as seed the values of some ram sector at initialization. I have not tried more specific solutions, for cost/benefit reasons (ADC implementations). My 2c.

[Digital Larry]

I wrote a pseudo random number generator which was just of the form:

x(n + 1) = y * x(n) + z

which just truncated naturally to 16 bits in the 8031 I was using.  Then I experimented with y and z until I got a fairly long sequence.  Not sure if that would work.

[Rob Strand]

I wrote a pseudo random number generator which was just of the form:

x(n + 1) = y * x(n) + z

Those work totally fine for non-critical stuff.  Especially for 32 bits or more.

The trick is finding good y values.     For natural wrapping mod 2^n arithmetic on a microprocessor you get the longest sequences when y is of the form y= 8 * m  + 5 or y= 8 * m + 3;  where you plug in some integer value for m to get a y value.    That just guarantees a long sequence.  It's not enough for a good random sequence.

z is considered non-critical but needs to be odd. You can use z=1.

Lot's of info available on these:
https://en.wikipedia.org/wiki/Linear_congruential_generator

The other common type uses shift registers.   Normally the shift registers create random bits but  RG has posted a few times on the forum about turning those into random numbers.
EDIT: typo fixed ; y= 8 * m + 3 not y= 5 * m + 3

[ElectricDruid]

I can generate random numbers in software perfectly well, that's fine. I've done that a lot using LFSRs mostly, but also with LCGs. The trouble is that (a) that's not fast enough and (b) the processor is busy doing other stuff.
I need a source of noise internally that I can route to the CLC module and that (ideally) updates at the uP instruction rate or better (so 8MHz).
There's a ton of chips with a ton of peripherals, and I'm *sure* it's got to be possible to get one of them to generate a psuedorandom string of bits, but I can't find anything anywhere about it. The CRC module is the most likely candidate from what I can see, but it might not be the only one.

[Rob Strand]

I can generate random numbers in software perfectly well, that's fine. I've done that a lot using LFSRs mostly, but also with LCGs. The trouble is that (a) that's not fast enough and (b) the processor is busy doing other stuff.
I need a source of noise internally that I can route to the CLC module and that (ideally) updates at the uP instruction rate or better (so 8MHz).
There's a ton of chips with a ton of peripherals, and I'm *sure* it's got to be possible to get one of them to generate a psuedorandom string of bits, but I can't find anything anywhere about it. The CRC module is the most likely candidate from what I can see, but it might not be the only one.

It seems a fairly specific problem.

It's possible to do the multiplications for the LCG generator with a few shifts and adds.  That's an old trick used by assembler programmers to have fast multiplications by a constant.  You can even choose the multiplier (A or Y) with a common bit pattern that appears more than once in A.   I made fast random number generators like that when I was a kid on the old TRS-80 computer (1.774MHz clock!!!). Only you know if even that isn't going to work.

A small pic processor could be used to generate the random numbers.  It's only offloading that part of the processing.  You can still run into trouble if the random numbers cannot be generated fast enough.  You don't want the main processor to read two of the same number, although you could check for that an re-read, with an obvious delay penalty (the assumption being the raw generator output is a unique sequence).

The old school hardware solution was a zener or reversed biased junction turned into a bit stream.   In reality there is an analog limit on the bit rate.   They generated bits so you need to read in a word at a slow enough rate.  The act of forming a word from bits might not be much quicker than a fast LCG.

There are chips but they could be more complicated than you own project!   Often these specific chips can be expensive and annoying to replace if you fry one,
https://www.fdk.com/cyber-e/pdf/HM-RAE001.pdf

[marcelomd]

I need a source of noise internally that I can route to the CLC module and that (ideally) updates at the uP instruction rate or better (so 8MHz).

What are you doing that needs random numbers at 8MHz?

Also, 8M bits per second or 8M words per second?

[cordobes]

One idea that might work would be to use the spi shift register.
Routing the output of sys_clk (depending on the PIC you are using) to the spi_clk line, and input noise on the spi_dat line with a bjt or zener, as Rob mentioned (clamped with shottky).
Configure spi, disable all the interrupts it generates.
This way you would have a random data ready in the spi buffer, or directly perform the XOR between that buffer and the data you want to modify.
It is worth the try.

[Digital Larry]

Lot's of info available on these:
https://en.wikipedia.org/wiki/Linear_congruential_generator

And all this time I thought I'd invented it!   

[Rob Strand]

And all this time I thought I'd invented it!

  It's kind of evolved but arcane knowledge.

A good run down is in one of the volumes of Donald Knuth's series of books (The Art of Computer Programming, 1968).   He has an algorithm for the "spectral test" which tests for good and bad multipliers.   It took about 5 days to run it on my TRS-80 and that was only for 16 bit numbers  .   (The algorithm needs to be run using integer calculations with word lengths somewhat longer than the multiplier word size.  If the calculations overflow it screws up the results.)

The later papers on lcg's give up on the natural mod 2^n version and use mod prime numbers.  Obviously these take more computation and then people come up with ways of speeding it up.

The downside of the lcg's is the lower bit aren't as random has the upper bits.   If you AND-off the upper bits an use that as a smaller random number it's not a great random number.   What you need to do is shift down the word and use the upper bits.

The random number generators now are much more evolved.   There's plenty about them on Wikipedia.

[ElectricDruid]

What are you doing that needs random numbers at 8MHz?

Also, 8M bits per second or 8M words per second?

8M *bits*. I only need one bit, not a full byte.

I'm trying to dither the output of the NCO. You can use it to generate a PDM output and make a DAC out of it. If you do that, the output is regular and repeating. I was hoping that by XOR'ing the output with a random bitstream, I could break up the regularity and improve the noise performance of the DAC (by spreading the noise out as white noise instead of it having noticeable frequency components).

[Rob Strand]

8M *bits*. I only need one bit, not a full byte.

I'm trying to dither the output of the NCO. You can use it to generate a PDM output and make a DAC out of it. If you do that, the output is regular and repeating. I was hoping that by XOR'ing the output with a random bitstream, I could break up the regularity and improve the noise performance of the DAC (by spreading the noise out as white noise instead of it having noticeable frequency components).

An LFSR running at clock speed would seem like the thing for the job.  You will need a long sequence to avoid hearing cyclic patterns.

[Christoper]

An LCG seeded with the given clock value is a textbook pseudorandom number generator.

[amz-fx]

At one time I did a lot of random generator code but it was for the AVR chips and not PIC.

One of the systems that I liked for very long pseudo-random sequences is the Alternating Stop-and-Go Generator. It uses one LFSR to drive two other LFSR generators that alternate output depending on the state of LFSR1. This requires 3 separate software LFSR routines but that is trivial with today's micros.

Best regards, Jack

ps: I also coded the LFSR for the FV1 that is in SpinCad.