Has anybody used the ADC LSB to generate random bit sequences?

Go To Last Post
24 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I might have an application where such random bit sequences are useful.  I had the idea of connecting an output pin (which is doing its own thing driving some hardware) through an RC network to the ADC input, and using the ADC LSB as a random bit.  Any thoughts or experiences?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Do you need actual random data, or is random-looking

data OK?  If it just needs to appear random, then I'd

suggest using a linear-feedback shift register (LFSR).

 

The attempt to use ADC output might produce less-

random-looking data.  The downside of LFSR's is they

repeat, but you can make the period as large as you like.

 

I've used a three-byte LFSR to generate realistic explosion

sounds using a mega 328P, for example.  Probably only

needs 2.

 

--Mike

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

dfgy

Doing magic with a USD 7 Logic Analyser: https://www.avrfreaks.net/comment/2421756#comment-2421756

Bunch of old projects with AVR's: http://www.hoevendesign.com

Last Edited: Mon. Jun 24, 2019 - 08:39 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

It seems doubtful that the ADC LSB would give true randomness, since there would no doubt be various biases (though I believe there are way to correct them if known).  What may look "random" for 1000 samples, might look much different after 10 billion samples  (then you can see with 1 million choices, the average of getting a 7440 after getting a 223154 is not 1 in a million (as it should), but 1 in 5000).  So how "good"/unpredictable do you want your random values to be?

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I don't need great randomness, but I do want to occasionally seed an LFSR in a system that has no user inputs (so no waiting to see how long before a user presses a button, etc).  I know there are other ways to generate a seed, I was just wondering about the ADC in particular.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Paulvdh wrote:
Quite a lot of years ago I read some thesis about using available hardware inside an AVR for generating randomness. One of the methods was by using the RC opscillator of the watchdog.

 

Yes, if you have 2 oscillators that are not synchronized, this should work.

You would set the WDT to generate interrupts, and timer 0, for example, to generate a square wave synchronous to the main oscillator, at a much higher frequency.

The WDT ISR will sample the timer square wave (i.e. check if it's high or low), to get random bits.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

For seeding an LFSR you could sample all of the PIN

registers, TCNTs, SPH and SPL, SREG, OSCCAL, (and

any others that won't interfere with normal operation),

and mix them all together somehow (XOR).

 

--Mike

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I seem to recall that there is at least one article about random generation in the tutorial forum - I think one of the areas examined may have been ADC noise.

 

EDIT: OK so i can't find what I thought I remembered - must have been something else. However, in the process of searching I was reminded of this: https://www.avrfreaks.net/forum/... which is always good for a giggle - wonder what David is up to these days?

 

Last Edited: Wed. Jun 19, 2019 - 02:00 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You also have a bunch of ram that on power up is in a 'random' state. May not actually be that random, but there should be enough 'random' bits in there to get something useful. On power up before the c runtime sets up the ram, do something with the ram (xor/sum/whatever) to get a 'random' seed.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

curtvm wrote:
May not actually be that random, but there should be enough 'random' bits in there to get something useful.
Interesting idea for an experiment - I have a pretty strong feeling that it may all start up with 0x00 but I guess one could put in a simple test of this?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

> I have a pretty strong feeling that it may all start up with 0x00

 

Not a chance in 2^(ram bytes*8). You know that already, you just need some coffee or something.

:)

Last Edited: Wed. Jun 19, 2019 - 03:50 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Why do you say not a chance? This is SRAM not DRAM. They are flip flops. I imagine they either default to all 0's or all 1's

 

Now I'm gonna have to dig out a board and debugger to try something I guess...

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

>They are flip flops

So they start with a flip or a flop?

 

Quick tests on a 4809- the ram is 'random' values, but it appears to be almost the same 'random' every time its powered up (I let sit for about 30 sec between test, with power shorted to gnd).

 

Out of 6K, only about 70 bytes change each time, and many of those are single bit differences (this did include the data/bss, but was not a lot). I would assume these bits/bytes have a natural inclination one way or the other on the molecular level, but a few handful of bits are on the 'edge'.

 

I think I checked this out a long time ago on a tiny2313 and kind of remember the same thing- random, but mostly the same random.

 

May end up that this is not a great idea, but could still end up with a few dozen bits of 'random'. I imagine using the ram for re-seeding while running could also be useful.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

hjk

Doing magic with a USD 7 Logic Analyser: https://www.avrfreaks.net/comment/2421756#comment-2421756

Bunch of old projects with AVR's: http://www.hoevendesign.com

Last Edited: Mon. Jun 24, 2019 - 08:40 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0


I think incompressibility is a reasonable test of randomness. I just powered up a mega4809 and dumped the sram (attached file), it's incompressible, at least with the tools I tried, so it must be pretty random.

 

edit: this is what it looks like visually (converted using the ImageMagick tool)

 

 

Attachment(s): 

Last Edited: Wed. Jun 19, 2019 - 08:12 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

curtvm wrote:

You also have a bunch of ram that on power up is in a 'random' state. May not actually be that random, but there should be enough 'random' bits in there to get something useful. On power up before the c runtime sets up the ram, do something with the ram (xor/sum/whatever) to get a 'random' seed.

 

In ancient history, Intel's 2Kx8 static ram chips had a strong tendency to start up with the value they had a power down.

The largest known prime number: 282589933-1

It's easy to stop breaking the 10th commandment! Break the 8th instead. 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I think incompressibility is a reasonable test of randomness. I just powered up a mega4809 and dumped the sram (attached file), it's incompressible, at least with the tools I tried, so it must be pretty random.

Well it could be random, but is it repeatable??? --you don't want that

 

22  54 11 7 29  3 88 is random, but if it is the same each time, maybe that is not  "random" enough  

 

this is what it looks like visually (converted using the ImageMagick tool)

 If you look closely you can see bigfoot

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

curtvm wrote:

Out of 6K, only about 70 bytes change each time, and many of those are single bit differences (this did include the data/bss, but was not a lot). I would assume these bits/bytes have a natural inclination one way or the other on the molecular level, but a few handful of bits are on the 'edge'.

 

I've seen this on UC3 micros.  I had an app with a non-initialized local bug that would run fine on some boards but always hang on (identical) others.  Finally tracked down the bug and fixed it.  I did some tests on a handful of boards (dumped the SRAM after powerup with JTAG) and found exactly what you describe.  Even if the boards were without power for weeks they would power up with nearly the same SRAM contents as before.  Note that the SRAM contents was vastly different from chip to chip but each chip seemed like it would power up with near identical SRAM contents regardless of how long it was without power.

Letting the smoke out since 1978

 

 

 

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Interesting. I will do a new SRAM dump in a few days and XOR the 2 samples together, if most bits are the same it will be easily noticeable.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The old trick of a zener diode and resistor to your ADC should give enough randomness methinks. A 3V3 zener should be especially noisy.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The old trick of a zener diode and resistor to your ADC should give enough randomness methinks

Probably good for general-purpose use.  What if the adc step size isn't exactly uniform....then some numbers have a very very slightly larger change of being generated (assuming a 100% perfectly linear ramp was applied).   Many other biases to consider as well.  If you were generating lottery winners of 1 in 300 million, even a few ppm skew could give you the "edge" & maybe "greatly" improve your odds to 1 in 80 million!  

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

#1 This forum helps those that help themselves

#2 All grounds are not created equal

#3 How have you proved that your chip is running at xxMHz?

#4 "If you think you need floating point to solve the problem then you don't understand the problem. If you really do need floating point then you have a problem you do not understand." - Heater's ex-boss

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I've tried both the watchdog method and the ADC method.  The ADC as I recall with a gain like 200X or something.  The watchdog is slower, I think 1 bit every 16ms or so, and the ADC worked pretty well, but then changed depending on physical conditions (I had it on a breadboard and the pin was left open).  I would have felt more comfortable with the pin connected to some sort of hardware noise like the zener mentioned above.  No matter what method you use, the results may need to be balanced or whitened.  My approach when trying to do this was using an algorithm that produces a whitened type of output, but I was constantly feeding more seed into it to alter it in real time.  I'm not sure if that was a good idea or bad idea...

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

avrcandies wrote:
Well it could be random, but is it repeatable??? --you don't want that

digitalDan wrote:
I did some tests on a handful of boards (dumped the SRAM after powerup with JTAG) and found exactly what you describe.

 

Well, I have confirmed this too. After discharging the SRAM from a mega4809 overnight, when powering up I observed that only 4% of bits have changed.

Also, I measured on this particular MCU, a bias toward "1" bits over "0" bits of about 1-2 standard deviations. This is not large, so it doesn't disprove randomness.

 

So basically, the contents of a freshly powered SRAM is a pseudo-random sequence particular for that specific chip. I guess this might be used for code protection schemes (?).

 

I was not aware of this property of SRAM, so thanks for the infoyes Always learning...