Random Number Generator

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.

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.

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 X^{16}+X^{14}+X^{13}+X^{11}+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 (2^{16}) 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

INIT_RANDOM_NUMBER_GENERATOR:

sts seed,r18

sts seed+1,r17

ret

;Returns the random number.The cycle of repetition is in (2

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 2^{16}. 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

;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