Saturday, November 26, 2011

Random number generator

Needed a way to make a microcontroller turn a load on at random. A little research and I found an algorithm that goes by the highfalutin name linear feedback shift register. Basically the bits in the register are shifted one bit either to the left or right and the result is then XORed with a constant. The content of the register changes in a pseudo random way. It isn't at all random because when we perform the shift and XOR the register goes through each possible value once and only once (each of 255 numbers for an 8-bit register) until we cycle back to the original seed value (initial value of the register). Thereafter, the exact same sequence gets repeated.

It's important to make sure the seed stored in the register is nonzero, else it will remain zero.

PIClist has a number of code snippets for implementing the LFSR in Microchip PICs. The following is for generating a 16-bit random number written in PIC18 assembly:

```  BCF     STATUS,C
RRCF    LFSRVALUEH,F
RRCF    LFSRVALUEL,F
BTFSS   STATUS,C
RETURN
MOVLW   0xA1
XORWF   LFSRVALUEH
XORWF   LFSRVALUEL
RETURN
```

Converting the above into mikroC PIC16 assembly with the 16-bit random number stored in variable N, we have:

```asm{bcf     STATUS,C
rrf     _N_L0+1,F
rrf     _N_L0+0,F
btfss   STATUS,C
goto    \$+4
movlw   0xA1
xorwf   _N_L0+1,F
xorwf   _N_L0+0,F}
```

And converting the same into mikroC we have:

```int8 RanNum()
{
static unsigned int RANDOM = 1;

RANDOM >>= 1;
if (STATUS.C)
RANDOM ^= 0xA1A1;
return RANDOM;
}
```

The above code translates into just 8 lines of mikroC assembly using the enhanced midrange instruction set.

For the circuit I'm using it in, I need a number from 0 to 99 to emulate a percentage value. So what I did was to simply take the last two digits (decimal) by dividing the 16-bit number by 100 and taking the remainder. I used a 16-bit generator instead of an 8-bit because the application requires that repetition of the sequence does not occur too quickly. I also wanted the seed number to be changed every time the circuit starts from a power-off condition so that the same sequence doesn't repeat every time the circuit powers up. To implement this the firmware loads RANDOM with the value stored in an EEPROM address. A crucial check is made to make sure RANDOM is not zero. If it is then it's incremented by one. RANDOM is then incremented and stored back in the same EEPROM location. Thus, every time the circuit boots up, RANDOM starts with a different seed.

```#define  addr_seed     0x1    // plug in your choice of eeprom address for the seed number
static unsigned int RANDOM;

void IniSeed()
{
// seed number for random number generator is obtained from an eeprom location
// the value of seed number is incremented and stored back in eeprom
// thus, a different seed number is used every time the MCU powers up.
if (!RANDOM)                           // seed number must not be zero!
RANDOM++;
}

int8 RanNum()
{
RANDOM >>= 1;
if (STATUS.C)
RANDOM ^= 0xA1A1;
return RANDOM % 100;     // a number from 0 to 99 is returned
}
```

Note that EEPROM_Read() and EEPROM_Write() are mikroC built-in functions. Admittedly the seed number in the above routine is only 8 bits long, but for my particular application this is sufficient. If you need a 16-bit seed then simply read the contents of two EEPROM addresses into RANDOM, increment RANDOM, and store the low and high bytes of RANDOM in the appropriate EEPROM addresses:

```void IniSeed()
{