A wide variety of applications, including data encryption and circuit testing, require random numbers. As the cost of the hardware become cheaper, it is feasible and frequently necessary to implement the random number generator directly in hardware itself. Ideally, the generated random number should be uncorrelated. A generator can be either “truly random” or “pseudo random.” The former exhibits true randomness and the value of next number is unpredictable. The later only appears to be random. The sequence is based on specific mathematical algorithms, and thus the pattern is repetitive and predictable. However, if the cycle period is very large, the sequence appears to be nonrepetitive and random. The focus of this paper is on pseudorandom number generators.
This paper provides an overview on the methods that are suitable for hardware implementation. The paper also describes singlebit and shows a leapforward LFSR implementation.
A single bit random number generator produces a value of 0 or 1. The most efficient implementation is to use a Linear Feedback Shift Register (LFSR) . It is based on the recurrence equation:
Here x_{i} is the i^{th} number generated, ai is a predetermined constant that can be either 0 or 1 and * and are And and Xor operator respectively. This equation implies that a new number (xn) can be obtained by utilizing m previous values (x_{n1} , x_{n2} ,…x_{nm} ) through a sequence of ANDXOR operations.
In pseudorandom number generator, the generated pattern will repeat after a certain number of cycles. It is know as the period of the generator. In an LFSR, the maximum achievable period, determined by m , is 2^{m1} . We use a special set of a_{i} s in order to achieve the maximum period. Despite their simplicity, the recurrence equations are different for different values of m . The table in Figure 1 lists the recurrence equation for m with values from 2 to 8.

For example, when m is 4, the equation becomes:
Assume the initial seed (i.e., s0, s1, s2, s3) is 1000. We can obtain the random number sequence by the equation: 100110101111000. This pattern repeats itself after 15 numbers. The new value, s_{n} , depends on the m previous values, s_{n1} , s_{n2} ,?s_{nm} . Therefore, m 1bit registers are required to store these values. After a new value is generated, the oldest stored value is no longer needed for future generation and can be done by an m slot shift register, which shifts out the oldest value and shifts in a new value in every clock cycle. In addition to registers, a few XOR gates are also required to perform exclusive operations. Let's use the previous example for m =4 again. We need four 1bit registers to store the required values. Let q3 , q2 , q1 , and q0 be the outputs of the registers and q3_next , q2_next , q1_next , and q0_next be their next values. The Boolean equation can be written as:

An LFSR random number generator is very efficiently implemented. It only needs an mbit shift register and 1 to 3 XOR gates, and thus the resulting circuit is very small and its operation is extremely simple and fast. Furthermore, since the period grows exponentially with the size of the register, we can easily generate a large nonrepetitive sequence. For example, with a 64bit generator running at 1GHz, the period is more than 500 years.
Some applications require more accuracy and need more that a single bit random number. Since the numbers produced by a single bit LFSR random number generator are correlated, one way to obtain a multi bit random number is to accumulate several single bit numbers.
The leapforward LFSR method utilizes only one LFSR and shifts out several bits. This method is based on the observation that LFSR is a linear system and the register state can be written in vector format:
In this equation, q(i + 1) and q(i) are the content of the shift register at (i+1)^{th} and i^{t} h steps and A is the transition matrix. After the LFSR advances k steps, the equation becomes:
We can calculate A^{k } and determine the Xor structure accordingly. The new circuit leaps k steps in one clock cycle. It still consists of the identical shifter register, although the feedback combinational circuitry becomes more complex. The implementation with 4 bit LFSR can be written as:
Assume that we need a fourbit random number generator and therefore have to advance four steps at a time. The new transition matrix becomes:
For the purpose of circuit implementation, the equation can be written as:
After performing the operations, we can derive the feedback equation for each signal as mentioned below:
Figure 3 shows the corresponding block diagram.

Figure 4 shows the fourbit output random sequence of the single LFSR and leapforward. The sequence generated is based on the seed value of 1000.

The simulation results are shown in Figure 5 . The first (top) figure shows the simulation results of Leap Forward LFSR techniques while the second (bottom) image is the LFSR result. It looks as though there is a high correlation between the two consecutive outputs of LFSR; while this is not the case, this is at the cost of extra hardware. The synthesis details are shown in Table 1 .
Synthesis Details  
Tool  Xilinx 
ISE Device family  Xilinx5x Spartan2 
Target device  2s30pq208 
Table 1: Synthesis details for simulation results
Several design techniques have been examined for hardware random number generators and this feasibility for FPGA devices. LFSR is the most effective method for single bit random number generator. When multiple bits are required, LFSR can be extended by utilizing extra circuitry. For a small number of bits, leapforward LFSR method is ideal because it balances the combinational circuitry and register, and balances the FPGA resource. We can extend this technique to a greater number of bits where one can get even better uncorrelated sequences for random number generation.
0 comments on “Random Number Generator Using LeapForward Techniques”