8-bit Pseudo-Random Number Generator

swToday we describe lightweight 8-bit pseudo-random number generator with an optional random seed initialization.

To generate 8-bit pseudo-random numbera Galois LFSR is used. The routine needs only 7 PIC instructions:


// Generates next 8-bit pseudo-random number
uns8 rand8();

// Generated 8-bit pseudo-random number (must not be equal to 0!) 
static uns8   RandomValue8;

uns8 rand8()
{
  RandomValue8 = lsr( RandomValue8 );
  // Optimization (avoid duplicate bank setting for RandomValue8 access)
  #pragma update_RP 0 /* OFF */	
  W = 0xB8;	// x^8 + x^6 + x^5 + x^4 + 1
  if ( Carry )
    RandomValue8 ^= W;

  return RandomValue8;
  #pragma update_RP 1 /* ON */
}

There are a few 8-bit polynomials that can be used instead of current 0xB8. All of them generate 8-bit pseudo-random sequence but with different characteristic. Give it a try!

0x8E, 0x95, 0x96, 0xA6, 0xAF, 0xB1, 0xB2, 0xB4, 0xB8, 0xC3, 0xC6, 0xD4, 0xE1, 0xE7, 0xF3, 0xFA

Variable RandomValue8 must be initialized to nonzero and preferably random value before generating next pseudo-random value. It is actually a generator initial seed. The easiest way is to use the lowest byte of TR unique Module ID. But this gives every time the same result thus the value is not actually random. To improve the randomness the value can be XORed with current temperature, current RSSI and other potentially “random” values. At the end never forget to make sure that the initial value is not equal to zero, otherwise LFSR will not work and will always return zero.

void APPLICATION()
{
  // Initialize RandomValue8
  moduleInfo();
  RandomValue8 = bufferINFO[0];
  RandomValue8 ^= getTemperature();
  RandomValue8 ^= getRSSI();

  // Make sure the seed is not 0
  if ( RandomValue8 == 0 )
    RandomValue8 = 0xAC;

  for ( ;; )
    // Generate next random numbers
    rand8();
}

The best results we got by combining RSSI measured at many RF channels. The resulting random seed distribution is almost ideal.

 rssicnt

void APPLICATION()
{
  // The way to switch RX chain on
  checkRF(0 );

  // Save current RF channel
  uns8 saveChannel = RFchannel;
  // Channel number
  uns8 channel = 64;
  do
    {
    setRFchannel( channel );
    RandomValue8 ^= getRSSI();
    // Resulting random number must not be 0
    if ( Zero_ )
      RandomValue8.4 = 1;
    // Rotate result
    W = rl( RandomValue8 );
    saveRandom = rl( RandomValue8 );
  } while( --channel != 0 );

  // Restore RFchannel
  setRFchannel(saveChannel );

  for ( ;; )
    // Generate next pseudo-random numbers
    rand8();
}

If 8-bit pseudo-random value is not enough you can easily upgrade to a 16-bit version. Only 8 PIC instructions are needed:

// Generates next 16-bit pseudo-random number
uns16 rand16();

// Generated 16-bit pseudo-random number (must not be equal to 0!) 
uns16 RandomValue16;

uns16 rand16()
{
  RandomValue16.high8 = lsr( RandomValue16.high8 );
  // Optimization (avoid duplicate bank setting for RandomValue16 access)
  #pragma update_RP 0 /* OFF */
  RandomValue16.low8 = rr( RandomValue16.low8 );
  W = 0b10110100;	// x^16 + x^14 + x^13 + x^11 + 1
  if ( Carry )
    RandomValue16.high8 ^= W;

  return RandomValue16;
  #pragma update_RP 1 /* ON */
}

Enjoy!

Post sent by Hynek Syrovátka.

Leave a Reply

Your email address will not be published. Required fields are marked *