topic Re: S08 Random Number Generator in 8-bit Microcontrollers

S08 Random Number Generator

Davo — Tue, 16 Sep 2008 20:13:03 GMT

I am looking for a way of generatring an 8 bit random number using an S08. Preferably in assembly. I have searched the web endlessly but haven't found anything simple and usable. Any ideas appreciated.

Re: S08 Random Number Generator

JimDon — Thu, 29 Oct 2020 09:37:16 GMT

The first question is how "random" does it need to be?
What are you going to use it for?
"Good" random generators are just not as simple as you may like.

This is about as simple as it gets.

Read this to see if it it will do.
It this is good enough, then I am sure the asm guys will jump in to tell you the best way to do it.

Code:

unsigned long int lehmer(long int s)//  linear congruential pseudo based on D. Lehmer{  static unsigned long long a = 2007, b = 4194301, c = 2147483647, z = b;    if ( s < 0 ) {s = -s; a = s;}    z = (a + b * z) % c;    return z % s;}

Message Edited by JimDon on 2008-09-16 09:40 AM

Re: S08 Random Number Generator

Roach — Wed, 17 Sep 2008 00:50:27 GMT

If you have an AD input or time input, you may use them to generate your random number.

Re: S08 Random Number Generator

bigmac — Wed, 17 Sep 2008 13:06:46 GMT

Hello,

Use of the Lehmer algorithm, as suggested by JimD, may be somewhat overkill for an 8-bit result, since 32-bit quantities are used during the calculation.

You might also consider a pseudo-random sequence (PRS), similar to that used for CRC calculations. The suitability will depend on your application. For an 8-bit PRS, the pattern will repeat after 255 iterations, and for 16-bit, the sequence length would be 65535 iterations. Each of the possible (non-zero) values will occur once within each sequence.

The starting point for the sequence will be determined by initialisation of a "seed" value. If the starting point should be different for each equipment, the seed must be related to an external event. Perhaps read the TPM counter when this randomly timed event occurs, and use the LS byte as the seed.

The following 8-bit PRS is based on a CRC function coded in C, and then converted to ASM. The ASM code is untested. The 8-bit polynomial used is X^8 + X^5 + X^4 + 1. The subroutine assumes that you have allocate a byte variable RAND, preferably within zero page RAM, and that this has been initialised to the required non-zero seed value.

POLYVAL EQU $8C ; Polynomial value

; PRS sub-routine:

; On exit, ACC = next value of sequence

NEXTVAL:

LDX #8

LDA RAND

NV1: LSRA

BCC NV2

EOR #POLYVAL

NV2: DBNZX NV1 ; Loop for next bit

STA RAND

RTS

This process could be easily extended to a 16 bit PRS, obviously using a suitable 16-bit polynomial.

Regards,

Mac

Re: S08 Random Number Generator

Davo — Thu, 18 Sep 2008 04:16:01 GMT

Thanks bigmac. I tested this generator and it works well. There are a few more things I would like to achieve:

I would like to range the number within 0-47 or 1-48. I tried simply rejecting every value over 48 but that didn't seem to give me well distributed results.

The "randomness" is not overly important, however I do want every number in the range to appear at least occaisonally.

The end goal is that I have 48 outputs that I need to randomly turn-on and turn-off every few seconds - and every bit should over a period of time (minutes to 10's of minutes) have a turn at being in either state.

thanks again

Re: S08 Random Number Generator

bigmac — Thu, 18 Sep 2008 11:49:51 GMT

Hello,

If you are simply toggling the respective LED when each value between 1 and 48 is output, this will not produce random on and off intervals since the sequence repeats every 255 iterations. If you do require "randomness" for the intervals, one way would be to use a 48-bit PRS generator, with each bit representing a LED state. However, this might be more complex than the task warrants.

A possible alternative might be to divide the LEDs into three groups of 16. Now divide the 8-bit result so that the low nybble addresses the LED position in each group, and the MS bit determines whether the addressed LED should be currently on or off. The remaining three bits would be used to select the LED group - so the 8 states would need to be mapped to the three groups.

One possibility might me to ignore two of the states (representing no change to LED status), and map the remaining 6 states, with two states per group. Alternatively, if the groups are physically interspersed, it may be acceptable to favour two of the groups over the third, i.e. 3 + 3 + 2 = 8.

The following code represents a slightly more complex arrangement that achieves 24 states using an auxiliary COUNT variable. However, I don't know how "random" the group selection will actually be.

JSR NEXTVAL ; Get next PRS value

PSHA

AND #$0F ; Low nybble

STA ADDRESS ; LED address within group

LDX COUNT ; Auxiliary counter

AIX #8

CPX #24

BLO *+3 ; Skip next if no overflow

CLRX

STX COUNT

PULA ; PRS value

PSHX

NSA

AND #$07 ; Range 0-7

ORA 1,SP ; Combine with count value (0-23)

AIS #1 ; Adjust stack pointer

LDX #3

DIV

PSHH ; Remainder (0-2)

PULA

NSA

ORA ADDRESS ; Combine with low nybble

STA ADDRESS ; Range 0-47

BRSET 7,RAND,BR1 ; Branch if LED on state

JSR LED_OFF ; Addressed LED off

BRA BR2 ; Branch always

BR1:

JSR LED_ON ; Addressed LED on

BR2:

Regards,

Mac

Message Edited by bigmac on 2008-09-18 03:12 PM

Re: S08 Random Number Generator

Davo — Thu, 18 Sep 2008 12:23:41 GMT

Thanks again Mac for your reply.

I do need to work from a number that is 0-47 or 1-48. The reason being that I don't want a situation where many outputs can change at one time. There needs to be a gradual changing of states. So I basically feed the number into a routine that sets/clears the corresponding bit. A separate random number generator makes the set/clear decision (simply use one bit of the 8 bit result to make the set/clear decision).

The compactness of the code is not important, as the processor is pretty idle and the app only takes a few k. It's running in an SH8.

Perhaps I could take the 8 bit result and divide it by 48 and use the remainder.

One other point - I need a seed that has some rendomness about it. I was thinking of using the lower bits of the internal temperature sensor read by the ADC. There should be sufficient noise and variability. Your thoughts?

Re: S08 Random Number Generator

Davo — Thu, 18 Sep 2008 12:58:27 GMT

dah !

of course I can't use the reminder because 48 doesn't evenly divide into 256

Re: S08 Random Number Generator

bigmac — Thu, 18 Sep 2008 14:04:25 GMT

Hello,

If I correctly understand your requirements, the code sample that I gave would seem to meet most of them. For each sample, a maximum of one LED would change state. Of course there will be many samples where no change occurs because the new state for a particular LED is identical to its previous state. But I don't think this would detract from the randomness of the process.

The sample code attempts to provide equal weighting to all LEDs. Simply dividing by 48 may also be adequate, but some LEDs will have more weighting. LEDs 1-15 would be addressed six times during each PRS cycle, whereas the other LEDs would be addressed five times.

With this in mind, there is possibly some advantage in using an 8-bit value from a 16-bit PRS, so that each LED is addressed many more times during the full PRS cycle.

I would suggest running the LED control code from within the ISR associated with a TPM overflow interrupt. With the use of an additional counter variable, the update could occur once every N overflows.

I assume that the seed would only need to be initialised after each POR. The only reason I can think of for having this randomised would be for the case of multiple units, operating side by side, to have different display patterns. The temperature sensor measurement may possibly work, however if multiple units are subject to the same temperature environment, the range of different values may be quite limited. I would suggest using the low byte of a 10-bit measurement, and swap the nybbles.

An alternative possibility that comes to mind is to use an external R and C, connected to a comparator input. Then read the low byte of the TPM counter value when the capacitor (or resistor) voltage reaches the internal reference level and the comparator changes state. The time constant should correspond to many TPM increments, and the capacitor should be a loose tolerance type (-20, +80 percent) used typically for bypassing applications. Finally, don't trim the internal clock until this process is completed. Again, I would swap the nybbles of the counter value.

Regards,

Mac

Re: S08 Random Number Generator

Davo — Thu, 18 Sep 2008 20:19:02 GMT

Getting Interesting. The first routine (NEXTVAL) works OK, however about 30% of the numbers never get generated (meaning some LEDs don't ever get turned on).

The second routine crashes - not had time yet to debug it, but the COP times out when the routine is called.

Re: S08 Random Number Generator

JimDon — Thu, 29 Oct 2020 09:37:18 GMT

i is 150 for all 48 values. This varies with the initial value of z.

You could probably tweak the values and get it better than that. Read the wiki I linked to for advise.

Code:

#include "stdafx.h"



unsigned char lehmer(unsigned char  s)
{  static unsigned short a = 2007,
   b = 7,
   m = 32768,
   z=0;
   
    z = (b + a * z) % m;
    return (z >> 6) % s;
}
int main(int argc, char* argv[])
{
 int i = 0;
        unsigned char data[48];
        int j = 0;

 while( j < 48)
 {
  unsigned char c = lehmer(48);
  if( data[c] == 0)
  {
   ++j;
   printf("%d\n",  c );
   data[c] = 1;
  }
  if( j == 48 )
   break;
  ++i;

 }
 printf("\n%d i=%d\n",  j,i );
 return 0;
}

Re: S08 Random Number Generator

JimB — Fri, 19 Sep 2008 04:08:25 GMT

Might not be following this correctly, but think you can scale your random number by treating the 0-255 (for 8 bits) as 0-1 (by considering the "binary point" at the left), and just multiply it by 49 to get 0-48 out.

Jim

Re: S08 Random Number Generator

bigmac — Sat, 20 Sep 2008 21:21:57 GMT

Hello,

Davo wrote:
Getting Interesting. The first routine (NEXTVAL) works OK, however about 30% of the numbers never get generated (meaning some LEDs don't ever get turned on).

The second routine crashes - not had time yet to debug it, but the COP times out when the routine is called.

Yes, there is a problem with the manner in which I attempted to convert the original CRC routine to a PRS in assembler - the sequence was not maximal length, and only 50 percent of the possible codes were generated. However, using the CRC method, I now feel that you will need a 16-bit generator to obtain a much longer sequence length. Apparently successful tests were conducted with the following C code, under simulation.

#include <hidef.h> /* EnableInterrupts macro */
#include "derivative.h" /* Include peripheral declarations */

typedef union {
word wval;
byte bval[2];
} DBYTE;

// Global variables:
DBYTE CRC16;

// Function prototypes:
void update_crc16( word new, word *crc);
void LED_control( byte address);
void LED_on( byte addr);
void LED_off( byte addr);

/**********************************************************************/
void main(void)
{
static byte a;
static word i;

   EnableInterrupts;

   for( ; ; ) {

      update_crc16( 1, &CRC16.wval);
      a = CRC16.bval[0] ^ CRC16.bval[1]; // Combine the two bytes
      if ((a & 0x3F) < 48) {
         a &= 0xBF;           // MS bit represents LED state
         LED_control( a);
      }
      __RESET_WATCHDOG();
   }
}

/**********************************************************************/
/* Update 16-bit CRC value
* Polynomial: x^16 + x^15 + x^2 + 1 */
#define POLYVAL16 0xA001

void update_crc16( word new, word *crc)
{
word c;
byte i;

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

/**********************************************************************/
/* Control of addressed LED */

void LED_control( byte address)
{
   if (address & 0x80)
      LED_on( address & 0x3F);
   else
      LED_off( address & 0x3F);
}

With this code the two bytes of the CRC value are XORed (modulo 2 addition). Bit-7 of the result then indicates the next state for the addressed LED, bit-6 is ignored, and the remaining six bits indicate the address of the LED, with values 48-63 as a do nothing condition.

My tests over about one half the sequence length of 65535, showed that each LED is addressed a similar number of times, although not quite equal, for both LED on and LED off conditions. About one half the LEDs will be active at any time.

For the purpose of testing the code, I put no delay in the loop between each call of the CRC function, but in practice this would be necessary for your application.

Regards,

Mac

Re: S08 Random Number Generator

Davo — Mon, 22 Sep 2008 05:31:17 GMT

Hi Mac, Do you have an assembly version of the code ?

Re: S08 Random Number Generator

bigmac — Mon, 22 Sep 2008 18:48:48 GMT

Hello,

No, I did not convert the 16-bit CRC algorithm, as I previously did for the 8-bit CRC. It was quicker to do the simulation tests using C. Is there any particular reason that you need to use assembler?

Regards,

Mac

Re: S08 Random Number Generator

JimDon — Mon, 22 Sep 2008 19:13:53 GMT

You can use C and assembler, but mac does have a point.

You will be much more productive using "C".

Re: S08 Random Number Generator

Davo — Tue, 23 Sep 2008 06:48:01 GMT

Mac, I do appreciate all of your help with this. I am converting some legacy code to include some new features. The main body is all in assembly. I'm not a C programmer and haven't had the time to learn given the small amounts of code I cut these days.

Re: S08 Random Number Generator

bigmac — Wed, 24 Sep 2008 12:09:04 GMT

Davo wrote:
Hi Mac, Do you have an assembly version of the code ?

; variable/data section

ORG     Z_RAMStart
RAND:     DS.W   1
ADDRESS: DS.B   1

;*******************************************************************
; Set next LED state change

NEXT_STATE:
          JSR    NEXTVAL        ; Get next PRS value
          PSHA
          AND    #$3F           ; Mask first 6 bits
          STA    ADDRESS
          CMP    #48            ; Test for within range 0-47
          PULA
          BHS    NS2            ; Exit if out of range (no change)
          AND    #$80           ; Test bit-7
          BNE    NS1            ; Branch if bit is set
          LDA    ADDRESS
          JSR    LED_OFF        ; Addressed LED turn-off
          RTS

NS1:      LDA    ADDRESS
          JSR    LED_ON         ; Addressed LED turn-on
NS2:      RTS

;*******************************************************************
; PRS sub-routine:
; On exit, ACC = next value of sequence

POLYVAL EQU $A001 ; Polynomial value

NEXTVAL: LDX    #16            ; Bit count
          LDA    RAND+1         ; Low byte
          EOR    #1
          PSHA                  ; 2,SP
          LDA    RAND           ; High byte
          PSHA                  ; 1,SP
NV1:      LSR    1,SP
          ROR    2,SP
          BCC    NV2
          LDA    1,SP
          EOR    #(POLYVAL/256)
          STA    1,SP
          LDA    2,SP
          EOR    #(POLYVAL%256)
          STA    2,SP
NV2:      DBNZX NV1            ; Loop for next bit
          PULA                  ; High byte
          STA    RAND
          PULA                  ; Low byte
          STA    RAND+1
          EOR    RAND           ; Combine byte values
          RTS

Message Edited by bigmac on 2008-09-24 03:13 PM

Re: S08 Random Number Generator

Davo — Thu, 25 Sep 2008 06:25:35 GMT

Mac, again - thanks for the reply.

My P&E assembler didn't accept the % operator. #(POLYVAL%256)

I assume this is an Intel operator. I replaced it with #{POLYVAL&256} assuming it was a bitwise AND of POLYVAL. This worked a treat and I am getting a pretty good distribution of random numbers.

Re: S08 Random Number Generator

CompilerGuru — Thu, 25 Sep 2008 08:34:18 GMT

% means modulo, not and, and therefore
using "& 256" will just load 0....
I would try just no operator first "#POLYVAL", or if that gives a warning, try "&255"
(or check the P&E Manual how to get the lower 8 bits of a label).

Daniel