S08 Random Number Generator

[Davo]

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.

[Davo]

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

[bigmac]

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

[Davo]

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?

[bigmac]

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

[Davo]

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.

[bigmac]

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

[JimDon]

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;
}

 

[Davo]

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

[bigmac]

---

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

[Davo]

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.

[CompilerGuru]

% 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

[bigmac]

Hello,

The P&E CASM08 assembler does support the % operator, however you will need to replace the surrounding parenthesis with curly braces.  This should be done for each of the two expressions.  This is one of differences between CW and P&E assemblers.  If you have not already done so, near the start of your ASM file, you will also need to include the directive to default to decimal numbers, rather than hexadecimal.

#BASE  10T

...

...

       EOR    #{POLYVAL/256}  ; High byte of polynomial

...

       EOR    #{POLYVAL%256}  ; Low byte of polynomial

As Daniel indicated, the purpose of these expressions is to select the high byte value and the low byte value for a 16-bit number.  There are also other alternative ways of doing this, but this method seems to be more clear (to me) as to the intent of the operation.  The P&E assembler does not have high byte and low byte directives, (well not the version that I use).

Regards,

Mac

Message Edited by bigmac on 2008-09-25 01:29 PM

[Davo]

Hi,

The P&E help file has no reference to modulo operators. The following seems to works OK to grab the lower 8 bits of a 16 bit value,

   EOR    #{POLYVAL&$00FF}

An alternate approach would be the longhand way:

POLYVAL_HI   equ   $A0

POLYVAL_LO   equ   $01

          ....

          EOR    #{POLYVAL_HI}
          STA    1,SP
          LDA    2,SP
          EOR    #{POLYVAL_LO} 

          ....

However the upper byte is interesting. Here is the listing outcome:

E05B [02] A844       526            EOR    #{POLYVAL/256}
 

I would have thought the listing should read:

E05B [02] A8A0       526            EOR    #{POLYVAL/256}

[bigmac]

Hello,

The % operator, and all the other operators should be listed within the "Operands" section.

Your problem is because the number 256 is being treated as a hexadecimal value, rather than decimal.  When the P&Eassembler is first started, the default number base is hexadecimal.  If you do not wish to change the default number base to decimal using the directive #BASE 10T, you can either use 100 as the hexadecimal equivalent of 256 decimal, or specifically define 256 as a decimal number.  the following instructions should produce the same result for a hexadecimal base.

     EOR    #{POLYVAL/256T}  ; Explicit decimal divisor
     EOR    #{POLYVAL/$100}  ; Explicit hexadecimal divisor
     EOR    #{POLYVAL/100}   ; Default hexadecimal divisor

For me, it is more intuitive to use the BASE directive so that decimal numbers are the default, and hexadecimal or binary numbers need to be explicitly defined as such.

Interestingly, the CW assembler defaults to a decimal number base.

Regards,

Mac

Message Edited by bigmac on 2008-09-25 04:17 PM

[peg]

Hello,

From the CASMHCS08 Pro Help file:

An operand may be an address, label, or a constant as defined by the opcode.  Arithmetic may be performed within parameters, at assembly time.  The allowed operators are:


*    multiplication
/    division
\    special division
+    addition
-    subtraction
<    left shift
>    right shift
%    remainder after division
&    bitwise and
|    bitwise or
^    bitwise xor


Special division is an operator that allows a divide by zero.  If there is a divide by zero anywhere in the expression, the entire expression equates to zero.

Operator precedence follows the rules of algebra and may be altered by the use of parentheses.

If more then one operator, parenthesis, or embedded spaces are used, the entire expression must be put inside curly brackets {}.

Examples:


jmp start    ; start is a previously defined label.
jmp start+3    ; jump to location start + 3
jmp {start > 2}    ; jump to location start divided by 4

[Davo]

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.

[bigmac]

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

[JimDon]

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

You will be much more productive using "C".

[Davo]

dah !

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

[JimB]

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