Random Number Generator

Randomization.

Sometimes a need arises to have a function that generates random numbers much like C baseline

function “srand()/rand()” written in assembler.

Randomization however has always been one of the most confusing aspects of the implementation process. There has been endless talk about whether any number or noise generator can be truly random. The answer is simply “no.” This is because every “random” number generator repeats itself after some interval. If this periodicity is sufficiently large, the source, which is not really random,appears to be completely random. Hence, we call such sources pseudo-random number generators.
Embedded systems generally use some hardware based pseudo-random number generators to introduce nondeterministic behavior in their working. However, a particular type of pseudo-random generators known as linear feedback shift registers (LFSRs) can be integrated easily in software alone, without the requirement of additional hardware resources.

 

Linear feedback shift register (LFSR).

LFSR is a shift register whose input bit is a linear function of its previous state.
The initial value of the LFSR is called the seed, and because the operation of the register is deterministic, the stream of values produced by the register is completely determined by its current (or previous) state. Likewise, because the register has a finite number of possible states, it must eventually enter a repeating cycle. However, an LFSR with a well-chosen feedback function can produce a sequence of bits which appears random and which has a very long cycle.

 

Galois LFSR.

The bit positions that affect the next state are called the taps. In the Fig.1 the taps are [16,14,13,11]. The rightmost bit of the LFSR is called the output bit. The taps are XOR'd sequentially with the output bit and then fed back into the leftmost bit. The sequence of bits in the rightmost position is called the output stream.

 

 The arrangement of taps for feedback in an LFSR can be expressed in finite field arithmetic  as apolynomial mod 2. This means that the coefficients of the polynomial must be 1's or 0's. This is called the feedback polynomial or characteristic polynomial. For example, if the taps are at the 16th, 14th, 13th and 11th bits (as shown), the feedback polynomial

is X16+X14+X13+X11+1=(0xACE1)

The 'one' in the polynomial does not correspond to a tap — it corresponds to the input to the first bit (i.e. x0, which is equivalent to 1). The powers of the terms represent the tapped bits, counting from the left. The first and last bits are always connected as an input and output tap respectively.


Implementation.

A simple AVR assembler implementation of Galois LFSR for 16 bit random number generaton follows.

;Invoked only once to set the seed’s initial value.It must be other then 0!
INIT_RANDOM_NUMBER_GENERATOR:
 sts seed,r18
 sts seed+1,r17
ret

;Returns the random number.The cycle of repetition is in (216) numbers.
GET_RANDOM_NUMBER:  
 lds r18,seed
 lds r17,seed+1

 LSR16 r18,r17                          
 brcc skipxora
 EORI16 r18,r17,temp,0xB400
skipxora:  

 sts seed,r18
 sts seed+1,r17
ret

;@MACRO EORI16  MSB,LSB,temp,value  

.MACRO EORI16
 ldi @2,high(0xB400)
 eor @0,temp
 ldi @2,low(0xB400)
 eor @1,temp
.ENDMACRO

;@MACRO LSR16  MSB,LSB
.MACRO LSR16
 lsr @0
 ror @1   
.ENDMACRO

The random number generator needs to be initialized with initial seed value between 1 and 216. It needs to be kept in memory for later use by the actual generator. Production ready code may look like this.

.dseg
.seed: byte 2
.cseg
;INPUT:@0 - 2 bytes RAM seed label
;       @1 - seed MSB reg
;       @2 - seed LSB reg        
.MACRO INIT_SEED
 sts @0,@1
 sts @0+1,@2
.ENDMACRO



;INPUT:@0 - 2 bytes RAM seed label
;       @1 - seed MSB reg    
;       @2 - seed LSB reg
;       @3 - temp reg
;       @4 - taps        
;
;OUTPUT:@1 - random number MSB
;        @2 - random number LSB
.MACRO GET_RANDOM_NUMBER
 lds @1,@0
 lds @2,@0+1

 LSR16 @1,@2

 brcc skipxora                        

 EORI16 @1,@2,@3,@4

skipxora:  

 sts @0,@1
 sts @0+1,@2
.ENDMACRO

Comments

random gen       Reply

By jipm on Fri Mar 30 12:22:02 UTC 2012

good work again..



 Add Comment

  Comments 1 - 1 of 1  

Screen Name
Subject
Comment