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 X¹⁶+X¹⁴+X¹³+X¹¹+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.

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