Advertisement

Article

Random Number Generator Using Leap-Forward Techniques

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 non-repetitive and random. The focus of this paper is on pseudo-random number generators.

This paper provides an overview on the methods that are suitable for hardware implementation. The paper also describes single-bit and shows a leap-forward LFSR implementation.

Single Bit Random Number Generator Using LFSR

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:

  (1)

Here xi is the ith number generated, ai is a pre-determined 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 (xn-1 , xn-2 ,…xn-m ) through a sequence of AND-XOR operations.

In pseudo-random 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 2m-1 . We use a special set of ai 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.


Figure 1:  Sample Recurrence Equations

For example, when m is 4, the equation becomes:

  (2)

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, sn , depends on the m previous values, sn-1 , sn-2 ,?sn-m . Therefore, m 1-bit 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 1-bit 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:


Figure 2

An LFSR random number generator is very efficiently implemented. It only needs an m-bit 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 non-repetitive sequence. For example, with a 64-bit generator running at 1GHz, the period is more than 500 years.

Multiple-Bit Leap Forward LFSR

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 leap-forward 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:

  (3)

In this equation, q(i + 1) and q(i) are the content of the shift register at (i+1)th and it h steps and A is the transition matrix. After the LFSR advances k steps, the equation becomes:

  (4)

We can calculate Ak 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:

  (5)

Assume that we need a four-bit random number generator and therefore have to advance four steps at a time. The new transition matrix becomes:

  (6)

For the purpose of circuit implementation, the equation can be written as:

  (7)

After performing the operations, we can derive the feedback equation for each signal as mentioned below:

  (8)

Figure 3 shows the corresponding block diagram.


Figure 3:  Block diagram

Figure 4 shows the four-bit output random sequence of the single LFSR and leap-forward. The sequence generated is based on the seed value of 1000.


Figure 4:  Four-bit output random sequence of a single LFSR and leap-forward

Results

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

Conclusion

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, leap-forward 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.

About the Author
Narendra S. Bolabattin received a B.E. in Computer Science and Engineering from Shivaji University in 1999 and M.Tech in VLSI-System Design from the National Institute of Technology-Warangal in 2003. He worked for more than a year as a Research Associate in N.I.T Warangal. Bolabattin is currently a lecturer in the Department of Microelectronics and VLSI at the International Institute of Information Technology—Pune. His research interests include analog/mixed signal/low power RF IC Design, MEMS, and cyrptography. His email address is .

0 comments on “Random Number Generator Using Leap-Forward Techniques

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.