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 pseudorandom number generators.
Embedded systems generally use some hardware based pseudorandom number generators to introduce nondeterministic behavior in their working. However, a particular type of pseudorandom 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 wellchosen 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 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.
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
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.
.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
