I need a pseudo random number generator for the ATTiny 13

Go To Last Post
15 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I'm doing a project where I need a really simple random number generator for the ATTiny 13. I would like to generate numbers between 0 to 255 and the sequence can repeat after generating 256 numbers.

As for the seed, I will store that in EEPROM and change it every time I apply power.... I know that limits me to 100,000 power cycles, but that should still work.

If the EEPROM exceeds it's lifespan, will it error on me or just return the same number every time? At that point, for this application it won't matter, as long as I don't hang the processor.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I found that walking a pointer thru the program code and fetching bytes from it gives great looking random numbers. Someone suggested that here a while back.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I need to guarentee that I hit all the values 0 - 255 before I repeat is the problem.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

so make a table and seed it by jumping into it in a random spot. OR: If you start with a byte, xor the 2 lsbs, then xor that with the next to most (7th), then put this in the msb and right shift. This will give 128 values before repeating. I dont think you can get a 'maximal length sequence' with an even number of bits. Proof is left to a mathematician.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If space is available, you could do a circular buffer to greatly increase the number of power cycles

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I don't have sufficient flash memory or eeprom left to make a table... So, I tried the routine you suggested. Just a test

mov r17, r16 ; copy the seed

andi r17, 0x43 ; mask out all but bits 6, 1, and 0
clr r18 ; count the number of 1's
clr r19 ; need a zero to add to

lsr r17
adc r18, r19
lsr r17
adc r18, r19
lsr r17
lsr r17
lsr r17
lsr r17
lsr r17
adc r18, r19
bst r18, 0 ; copy the least significant bit to T
bld r16, 7 ; and store it to the most significant bit of my original number
lsr r16 ; right shift the original number

I started with a seed of 0x43 and within 6 iterations I got back to my original number...
What am I doing wrong?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
within 6 iterations I got back to my original number

Isn't a random number...random? Or do you want predictable random numbers? If you have some form of user input then you could just read the value of a free running timer.

John Samperi

Ampertronics Pty. Ltd.

https://www.ampertronics.com.au

* Electronic Design * Custom Products * Contract Assembly

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I have some little programs to do the 'binary maximal length sequences'... need to look for em.... they generate all the 2^n-1 combinations for any number of bits, but I think its the number of xor taps from the shift reg that have to be an odd number... like in the ccitt polynomial that gets xored with the data to give a crc... the bit positions are the taps in the shift register. Is only a couple of instructions and generates all the 8 bit numbers.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Try my A/D converter :D

Wiseguy

Who let that guy in here?

If you don't know my whole story, keep your mouth shut.

If you know my whole story, you're an accomplice. Keep your mouth shut. 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Sorry guys, I don't have any user input, so I can't tie this to the clock. And all of my inputs are tied to digital values. I don't think I would have much randomness there. I did find a routine that seems to work. which is and the seed with 10111000 binary and XOR all of the bits together. put that xor in the carry bit and do a LSL. It seems to generate numbers between 1-255 as long as the initial seed is not 0.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Is there a more efficient method of XOR the bits in a byte together than what I posted above? My routine used up 4 registers. I really wanted it to work with 2 registers, that would save me some pushs and pops.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I believe you stumbled onto a simple linear congruential algorithm .Works okay, but as you've noticed, no zero condition.

random:     ldi      temp,0x1d		 
            	clc
            	rol     random
            	brcc	pc + 2
            	eor   	random,temp
            	ret		

-carl

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

This generates all numbers from 1 to 127

//file bgbmls.c
//generate 8 bit bmls
//Sept 16 05 Bob G initial edit

#include 
#include 

unsigned char c,i,n,b0,b1,b7;

int main(void){
  printf("bgbmls Sept 16 05\n");
  n=1; //seed sr
  i=0; //clear counter
  while(1){
    b0=(n & 0x01)!=0; //extract lsb
    b1=(n & 0x02)!=0;
    if(b0 != b1) b7=0x40; else b7=0; //calc msb
    n >>=1;
    if(b7) n |= b7;
    i++;     
    printf("%02x %02x\n",i,n);
    if(n==1) break;
    if(i==0) break;
    if((i % 20)==1) c=getch();
    if(c=='q') break;
  }
}
//------------eof--------------

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thank you! thank you! thank you!

That's the algorithm I need..... :D

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

No psuedo-random number generator, either shift register or congruential, will ever generate more than (2^n - 1) different numbers. Usually the number 0 is omitted, but if 0 occurs, then some other number will be missing. This is a problem if you want exactly 256 values with equal weighting. One way round it is to add a cycling offset to the random number, modulo 256. Start the offset at 0 and increment by 1 every cycle (255 states) of the RNG - you can detect when it cycles by looking for a particular value, eg 001. This will give you 255 sets of 256 random numbers (0..255) one after another. Each of these 255 sets will have a single repeated number and a single omitted number, different each time, but over the full sequence of (256*255) states, each number will appear exactly 255 times.

Example, take the trivial case of a 2-bit RNG, length 2^2 -1, producing the sequence 1-3-2 repeatedly. Add a cycling offset modulo 2^2 (range 0..3) -

1 3 2 1 3 2 1 3 2 1 3 2 - 1 3 2 1... << rng
0 0 0 1 1 1 2 2 2 3 3 3 - 0 0 0 1... << offset
1 3 2 2 0 3 3 1 0 0 2 1 - 1 3 2 2... << final sum

When applying this in a practical situation, make quite sure that the RNG period and the offset period have no common factors, otherwise the sequence will short-circuit and repeat too often.