I need a pseudo random number generator for the ATTiny 13

Log in or register to post comments
Go To Last Post
15 posts / 0 new
Author
Message
BarryKirk
BarryKirk's picture
Level: New Member
Joined: Mon. May 2, 2005
Posts: 19 View posts
#1
Posted by BarryKirk: Fri. Sep 16, 2005 - 07:45 PM
  • 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.

Tags:

AVR Microcontrollers, megaAVR and tinyAVR
Top
Bronze Markbobgardner
bobgardner's picture
Level: 10k+ Postman
Joined: Wed. Sep 4, 2002
Posts: 26609 View posts
Location: Orlando Florida
Posted by bobgardner: Fri. Sep 16, 2005 - 07:50 PM
  • 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

Top
BarryKirk
BarryKirk's picture
Level: New Member
Joined: Mon. May 2, 2005
Posts: 19 View posts
Posted by BarryKirk: Fri. Sep 16, 2005 - 08:12 PM
  • 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.

Top
Bronze Markbobgardner
bobgardner's picture
Level: 10k+ Postman
Joined: Wed. Sep 4, 2002
Posts: 26609 View posts
Location: Orlando Florida
Posted by bobgardner: Fri. Sep 16, 2005 - 08:17 PM
  • 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

Top
NogginGTS
NogginGTS's picture
Level: Hangaround
Joined: Mon. Mar 17, 2003
Posts: 274 View posts
Posted by NogginGTS: Fri. Sep 16, 2005 - 08:56 PM
  • 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

Top
BarryKirk
BarryKirk's picture
Level: New Member
Joined: Mon. May 2, 2005
Posts: 19 View posts
Posted by BarryKirk: Fri. Sep 16, 2005 - 10:14 PM
  • 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?

Top
Bronze Markjs
js's picture
Level: Moderator
Joined: Wed. Mar 28, 2001
Posts: 30156 View posts
Location: Sydney, Australia (Gum trees, Koalas and Kangaroos, No Edelweis, but plenty of Corona beer)
Posted by js: Fri. Sep 16, 2005 - 10:22 PM
  • 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

Top
Bronze Markbobgardner
bobgardner's picture
Level: 10k+ Postman
Joined: Wed. Sep 4, 2002
Posts: 26609 View posts
Location: Orlando Florida
Posted by bobgardner: Fri. Sep 16, 2005 - 10:27 PM
  • 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

Top
Torby
Torby's picture
Level: 10k+ Postman
Joined: Tue. Nov 11, 2003
Posts: 10380 View posts
Location: Bartlesville Oklahoma USA
Posted by Torby: Fri. Sep 16, 2005 - 10:38 PM
  • 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. 

Top
BarryKirk
BarryKirk's picture
Level: New Member
Joined: Mon. May 2, 2005
Posts: 19 View posts
Posted by BarryKirk: Fri. Sep 16, 2005 - 10:48 PM
  • 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.

Top
BarryKirk
BarryKirk's picture
Level: New Member
Joined: Mon. May 2, 2005
Posts: 19 View posts
Posted by BarryKirk: Fri. Sep 16, 2005 - 10:50 PM
  • 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.

Top
H. Carl Ott
H. Carl Ott's picture
Level: Hangaround
Joined: Wed. Oct 3, 2001
Posts: 293 View posts
Location: NYC, USA
Posted by H. Carl Ott: Fri. Sep 16, 2005 - 10:56 PM
  • 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

Top
Bronze Markbobgardner
bobgardner's picture
Level: 10k+ Postman
Joined: Wed. Sep 4, 2002
Posts: 26609 View posts
Location: Orlando Florida
Posted by bobgardner: Fri. Sep 16, 2005 - 11:14 PM
  • 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

Top
BarryKirk
BarryKirk's picture
Level: New Member
Joined: Mon. May 2, 2005
Posts: 19 View posts
Posted by BarryKirk: Fri. Sep 16, 2005 - 11:35 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thank you! thank you! thank you!

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

Top
peret
peret's picture
Level: Raving Lunatic
Joined: Wed. May 26, 2004
Posts: 2482 View posts
Location: Las Vegas, Nevada
Posted by peret: Sat. Sep 17, 2005 - 12:27 AM
  • 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.

Top