8-bit MicrocontrollersのトピックRandom number generation

Random number generation

KRichard — Thu, 01 Mar 2007 00:37:17 GMT

Hello! I would like to have some examples of random number generation on HCS08 with CodeWarrior, would you please share some ideas? Thanks in advance, Richard

Re: Random number generation

bigmac — Thu, 01 Mar 2007 01:24:15 GMT

Hello,

What size number do you require?

If the random number is required in response to an external event (that may occur at a "random" time), and the events are not closely spaced, it may be possible to utilize the TIM or TPM counter value. For this simple method, the number should probably not exceed byte size, and I would probably use the LS byte of the timer, and swap the high and low nybbles to further "randomize" the value.

However, if you need a true "quasi-random" value, you might be able to easily adapt an existing function that calculates CRC values of the size you need. I recall that there are some recent threads on this subject in these forums, so use the search engine.

You could use the timer value as the initial "seed", and calculate the first CRC value based on this. The next CRC calculation would then use the previous CRC value, and so on. The CRC polynomial used would not matter for this application.

Regards,

Mac

Re: Random number generation

bigmac — Thu, 01 Mar 2007 10:46:54 GMT

Hello,

To further clarify the possible use of a CRC algorithm to generate a quasi-random value, I found the following code to generate an 8-bit CRC value.

/* Update 8-bit CRC value
using polynomial X^8 + X^5 + X^4 + 1 */

#define POLYVAL 0x8C

void update_crc(unsigned char new, unsigned char *crc)
{
unsigned char c, i;

  c = *crc;
  for (i = 0; i < 8; i++) {
     if ((c ^ new) & 1) c = (c >> 1 ) ^ POLYVAL;
     else c >>= 1;
     new >>= 1;
  }
  *crc = c;
}

To use this function to generate a quasi-random value, I think the following would work -

Firstlly, define and initialise a global variable to contain the random value

unsigned char rndval = SEED; // Must be non-zero value

Then when the next random value is required, and rndval is to be updated, use the following code -

update_crc(0xFF, &rndval);

My understanding is that the first parameter could actually be any non-zero constant.

Regards,

Mac

Message Edited by bigmac on 2007-03-0112:49 PM

Re: Random number generation

mke_et — Thu, 01 Mar 2007 22:23:27 GMT

Whatever method you use to generate the number, I would reseed it every time it's needed, and use a seed tied to a non-synchronous event to the code.

Obviously it's impossible to truely random numbers, but if the call to generate a number does the seed based on when it's called in the program against say a shuffle of a timer counter or something, then you at least won't get the same number after a reboot and executing the exact same sequence every time.

Re: Random number generation

dwhite — Sat, 03 Mar 2007 06:30:55 GMT

I try to stay away from values based only on timers and functions (CRC) because they tend to give the same result each time unless the request is generated by a human.

If you have a fairly noisy A/D input you could also XOR that in with your timer based value to help randomize it. I've even heard of people leaving unused A/D inputs floating to pick up radio noise for random number generation.

In one system, I took the results from all 8 A/D inputs and XOR'd them together as a seed value then I XOR'd that with a timer and the previous random value and put it through a scrambling function like the CRC. Pretty random!

Re: Random number generation - generating the seeds

rocco — Sat, 03 Mar 2007 09:44:12 GMT

In years past, I have used two methods to generate seeds for pseudo-random number generators.

In one, I had a very fast free-running counter that I would read and reset every time a button was pressed on the user interface, generating a fresh seed every button-press. When I needed a random number, I would generate it from the new seed if it was available. Otherwise, I would generate it from the previous random number if a fresh seed was not available yet.

In a similar vane to what dwhite mentioned, I once needed a 16-bit analog-to-digital converter tied to the AC line for calculating power. When I needed a new seed, I grabbed the most recent value returned by the AtoD. But in that case, the need for a random number was rare, and completely asynchronous with regard to the AC line.

Re: Random number generation

billw — Sat, 03 Mar 2007 10:04:58 GMT

First you need to decide whether "unpredictability" is important or not, especially compared to the sorts of statistical properties that random numbers are supposed to generate for simulations and such. Unpredictability is extremely important for cryptographic sorts of applications, but not so much for anything else (and of course it makes debugging harder.) The pseudo-random-number generators based on CRC-like calculations are adequate for many applications (though I'd beware of doing common
operations like "modulo" to get smaller random numbers if statistical properties are
important; you might interfere with the "randomness"...)

Getting "real", unpredictable random numbers in a deterministic system like a microcontroller is pretty tough. You can pick up a couple bits worth of randomness by timing external events like keypresses with a high-speed timer, but...

I keep expecting the next generation of micros to have built-in hardware support for generating random numbers (multiple noisy semiconductor junctions driving multiple counters, or something.) But I don't know if the people who want such things would consider them 'trustworthy' or not...