Transcript Notes

Generating Random Numbers
in Hardware
Two types of random numbers used in computing:
--”true” random numbers:
++generated from a physical source
(e.g., clock)
++sequence cannot be “repeated”
++may not pass mathematical “randomness” tests
--pseudorandom numbers
++generated from a well-defined procedure
++repeatable (good for debugging, e.g.)
++initial value usually chosen by user (“seed”)
++may not give good random behavior
Projects: we want to use pseudorandom numbers
Two common methods used to generate
pseudorandom numbers in hardware:
--LFSR (linear feedback shift register)
--CA (Cellular automata)
LFSR (Linear feedback shift register):
Based on polynomials over a finite field
Simplest field: Z2
elements: 0, 1
addition:
0 + 0 = 0; 0 + 1 = 1 + 0 = 1; 1 + 1 = 0
multiplication:
0 * 0 = 0; 0 * 1 = 1 * 0 = 0; 1 * 1 = 1
(note: in Z4 with elements 0,1,2,3 we have 2 * 2 = 0—it’s NOT a field!!!)
• Linear Feedback Shift Register (LFSR):
- sequential shift register with combinational logic
- feedback provided by selection of points called
taps
5
Need to use specific LFSR configuration to get “full
cycle”:
Need to use a “primitive” polynomial to generate the
entire “multiplicative group” (i.e., all 2n – 1 nonzero
elements of the field of polynomials of degree n-1
with coefficients in Z2, whose elements can be
represented by n-bit numbers)
Example: suppose we have 3-bit numbers c3c2c1
representing
c 3x 2 + c 2x + c 1
Field elements:
000 , 001, 010, 011, 100, 101, 110, 111
Seed : 001
“taps” 3,2 (count bits as 3,2,1)
Shift left, low order bit is xor of “taps”
001, 010, 101, 011, 111, 110, 100, 001, …….
Example:
N = 32:
Taps 32, 22, 2, 1
For each n, there is at least one such primitive
polynomial (result from math)
8
Bit 8
Bit 1
Example: random number generator for n = 8:
8-bit shift register (shifts left)
Load with SEED which is any nonzero number
shift in XOR of the specified bits (8, 6, 5, 4 for n = 8)
Generate all 255 (28 – 1) nonzero numbers in “random” order, e.g.:
SEED=10101000 gives 10101000, 01010001, 10100011, 01000110, …
9
How good are the random numbers generated?
Reference: Shruthi Narayanan, M.S. 2005, ATI Technologies
Hardware implementation of genetic algorithm modules for intelligent
systems:
Random numbers generated by one
shift register
Random numbers generated by
multiple shift registers
Conclusion: use multiple shift registers
10
• Serial Test Results
32-bit LFSR implemented by [martin]
Martin, P., An Analysis of Random Number Generators for a Hardware Implementation of
Genetic Programming using FPGAs and Handel-C, Technical Report, University of Essex, 2002.
11
• Multiple Linear Feedback Shift Registers:
- n LFSRs of length m are implemented
- one-bit from each LFSR is taken to form
n-bit random number
Martin, P., An Analysis of Random Number Generators for a Hardware Implementation of
Genetic Programming using FPGAs and Handel-C, Technical Report, University of Essex, 2002.
12
Another method: use cellular automata to generate pseudorandom numbers
1-dimensional example: center cell changes according to the values in its
neighbors: “rule 30”, a Wolfram favorite:
current pattern
111
new state for center cell 0
110
0
101
0
100
1
Source: http://en.wikipedia.org/wiki/Rule_30
011
1
010
1
001
1
000
0
• Cellular Automata:
- groups of cells, each cell’s life depends
on its neighbors
- state of the cell in each cycle given by a
set of rules
Martin, P., An Analysis of Random Number Generators for a Hardware Implementation of
Genetic Programming using FPGAs and Handel-C, Technical Report, University of Essex, 2002
See also: . Harish Ramaswamy, An extended library of hardware modules for genetic
algorithms, with applications to DNA sequence matching, MS, Univ. of Cincinnati, 2008
14
• LFSR involves global signal routing and hence
causes longer delays
• Improvement: Cellular Automata require local
routing only
Cellular Automata
A 1D CA consists of a string of cells with 2 neighbors, left
(West) and right (East)
• At each time step, the value of a cell is given by a rule.
• A simple 1D CA based PRNG is obtained by applying
Rule 30, which is,
C(t+1) = (West(t) XOR (C(t) OR East(t)))
• A Multiple CA is obtained by combining several 1D CAs
in series
Random Number Generator Contd.
Results of Serial test on 1D CA* (Single and Multiple)
Hybrid CA
• CA which makes use of a combination of rules is known
as Hybrid CA
• Combination of Rule 90 and Rule 150 at appropriate
sites can yield maximum length cycles
Rule 90 : C(i)(t+1) = C(i-1)(t) XOR C(i+1)(t)
Rule 150: C(i)(t+1) = C(i-1)(t) XOR C(i)(t) XOR C(i+1)(t)
* Martin, P., An Analysis of Random Number Generators for a Hardware Implementation of Genetic
Programming using FPGAs and Handel-C, Technical Report, University of Essex, 2002.
Generating pseudorandom numbers on an altera chip:
a. Make your own generator, using “n” lfsr’s or ca’s, start
each with a different seed
b. Use code from the altera “cookbook”:
http://www.altera.com/literature/manual/stx_cookbook.pdf