SURE -- Summer Undergraduate Research Experience
 |
|
Generating Pseudo Random Numbers With Hardware |
|
by Tom
Rogers |
|
Research
Question:
Can a linear feedback shift register (LFSR) type pseudo random
number generator (PRNG) be configured in FPGA
hardware so that it can match or exceed the
statistical performance of the standard Java PRNG algorithm?
Background: PRNG are used in large
scale Monte Carlo simulations, such as, simulating the
random motion of oxygen molecules diffusing through plastic food
packaging. Tracking particle behavior on a molecular level can
require supercomputers to generate billions of random numbers.
Patterns in a PRNG can cause significant errors. A typical
PRNG repeats itself on a cycle. Care has to be taken to be sure
that the cycle is longer than the random number requirements.
Finally, merely calculating PRNGs can consume significant
amounts of
computer time.
LFSR PRNGs have been used in cell phone wireless
communication systems to help prevent eavesdropping and noise
interference. They are relatively simple devices which consist
of simple logic gates.
Low cost FPGA systems can configure numerous logic gates into
complex devices. They're ideal for implementing LFSR PRNGs. Such a device can generate a random number
in a single clock cycle as compared to numerous clock cycles
required in a computer. This could reduce the computer time required to obtain random numbers.
The repeat cycle of LFSR systems i= (2^r) – 1 where r = the
number of shift registers (SR’s). If a longer cycle is needed
it’s only necessary to add more SR’s.
|
The Goal
Behind This Project
|
|
This project 's
hidden goal was to move cutting edge concepts from University to
high school classrooms. Elements were chosen at least
partly for their relevance to AP and IB Computer Science, AP
Statistics, and to a lesser extent AP Physics. The use of FPGA
should be a source of ideas for science fair projects.
This project
spawned three different applets including the one described
which can be used for exploring various concepts in statistics,
computer science, and physics. These are
available over the internet along with related materials for use
by teachers and students. Check the links at left or
intuitor.com.
The author, with help from Clemson
University, is continuing work on using FPGAs in the high school
classroom. These are relatively easy-to-use low cost systems
which can illuminate many different concepts in the subjects
named above. He will post information as it becomes available.
|
 |
| Fig. 1. Screen Shot of Software |
|
Procedure: Both standard and experimental PRNGs were characterized using
specially written software (see figure 1).
The software used three different hypothesis tests:
-
chi squared test on the shape of the distribution.
-
z-test on the mean of the distribution
-
f-test on the standard deviation of the distribution
All tests used alpha = .05 and n = 10,000. Numbers
were floating point. Significant digits varied depending on
PRNG configuration. Null hypothesis was that the distribution
of PRNs matched a
theoretical uniform distribution. Rejecting the null was
defined as failure and was expected 5 % of the time.
The program displayed a time plot and histogram. It also
showed a plot of repeat rates for various first digits.
An LFSR system was implemented on an
Xess
XSA-50
FPGA system. Output was a
single decimal digit with values of 1 – 9 shown on an LED
digit. This used four bits from a system with 10 shift
registers. The system
generated a pseudo random number each time a button was pushed
and automatically
recalculated a new number whenever it generated a value which
was not 1-9.
Data: The z-test, time plot and plot of the distribution of first
digit repeats were the most useful data. They're summarized below.
In the plots showing the distribution of consecutive first digit
repeats the blue bars represent runs of 3, the violet runs of 4 and
the red runs of
5 or more for a sample size of 10,000. The time plots display 100
consecutive data points
|
Standard Java PRNG
Z-test failure rate = 8.7 %
The Java PRNG is not considered an excellent PRNG but was
used as a useful starting point.
|
Basic 64 SR LFSR
Z-test failure rate = 36 %
A 64 SR system generated 64 bit PRNs. Bits were
used in consecutive order. Note excessive runs of 0s and 9s
with no runs in other digits. Also note the patterns in the
time plot.
|
Improved 64 SR LFSR
Z-test failure rate = 34 %
This system generated 64 bit PRNs with bits
selected randomly from among the 64 SRs. Note the improved
first digit repeat pattern and the lack of
pattern in time plot.
|
 |
 |
 |
|
- Dual 64 SR LFSR
-
Z-test failure rate = 14.2 %
Tests of
improved LFSR systems with 16 and 10 SR’s gave z-test failure
rates of 26.7 and zero % respectively. The 10 SR system
repeats every 1023 PRNs and so a sample of 10,000 will contain
nearly 10 complete PRN sets. By contrast the 16 SR system
repeats every 65,535 and the 64 SR system roughly every 1.8
E19 PRNs . A sample of 10,000 will only
contain a fraction of the 16 and 64 SR cycle. This implied
that LFSR systems have subtle cycles which tend to average out
over their entire repeat cycle.
The dual
system had two 64 SR LFSRs set at different initial values.
PRNs were selected alternately from the two systems. Initial
values were adjusted so that high areas in one system’s would
coincide with low areas in the other and average out their
effects
With an
overall cycle of over 1.8 E19, setting up the dual system in
out-of-phase mode was easier said than done. After numerous
trials it was demonstrated that the z-test failure rate could
be significantly reduced but it’s doubtful that the optimum
point was reached.
|
LFSR Implemented by an
FPGA
A limited
number of trials were performed with the hardware due to the
manual nature of the system’s I/O (a button and a single LED
digit output). However, the system did output all nine of the
digits 1-9 in a seemingly random fashion.
|
|
Conclusions: According
to software simulations, the best LFSR system matched the Java
PRNG in all the tests except the z-test comparing the mean random
numbers samples (n = 10,000) to a theoretical mean. The LFSR
system failed this test about 14.2 % of the time as compared to a
failure rate of 8.7 % for the Java PRNG. Theoretically the failure
rate should have been 5 %. However, the simulations also implied
that the LFSR system could be improved with further research.
An LFSR system was implemented on an FPGA but was not fully
tested due to its manual I/O system. However, it did demonstrate
the feasibility.
Future Work: Additional work needs to be done to determine
the optimum settings of the dual LFSR system and further
characterize its behavior. Future implementations of LFSR systems
on an FPGA need to be interfaced with a computer so that its
characteristics can be determined in an automated manner.
Acknowledgments: This project was made possible thanks to the mentoring of
Dr.
Daniel
Noneaker and
the assistance of
Peter
Rickenbach
who was invaluable as a resource in configuring the FPGA device.
|
|
