Transcript example - Robothon

Random Number Generator
(RNG) for Microcontrollers
Tom Dickens
The Boeing Company
[email protected]
Introduction
•
•
•
•
•
•
•
•
RNG Wisdom
Motivation for an RNG
Other RNG Methods
Requirements for a “Good” RNG
Approaches Taken
Testing
Implementation
Summary
Tom Dickens
RNG Wisdom…
“Anyone who considers arithmetical
methods of producing random digits is,
of course, in a state of sin.” John von
Neumann (1903-1957).
“The generation of random numbers is
too important to be left to chance.”
Robert R. Coveyou, Oak Ridge National
Laboratory in Tennessee.
Tom Dickens
Motivation For An RNG
For Microcontrollers
• More Interesting Robotic Behavior
• Avoid Stuck-In-A-Corner Logic
• Used In AI Techniques
– Genetic Algorithms
– Neural Networks
– Fuzzy Logic
Tom Dickens
Other RNG Methods
• Hardware-Based (true) RNGs
– White-Noise Source
– Transistor Circuits
Our desire is to have a pseudo random
number generator, as defined by…
Tom Dickens
Requirements - a “Good” RNG
• Key Requirements (detailed list in paper).
–
–
–
–
N = F(), where…
N is in the range 0 to 255
Large cycle of N’s before pattern repeats.
All values of N are generated the same number of
times in the cycle.
– Windows of consecutive N’s in cycle meet…
• Constraints for Average, Min, and Max values.
– Small Code Size
Tom Dickens
Approaches Taken
• Table-Based Method
– Define a table of 128 values.
– Use EXOR to generate 128 other values.
– Cycle through these 256 values 64
different ways.
– Cycle length of 16,384.
– Met the goodness criteria.
– 62 bytes of code + 128 bytes for table =
190 total bytes. 4 bytes of RAM.
Tom Dickens
Approaches Taken
• Equation-Based Method
– 2-byte seed value in RAM
– seed = 181 * seed + 359
– Return top 8 bits of seed.
– Cycle length of 65,536.
– Met the goodness criteria.
– 25 bytes of code, 4 bytes of RAM.
Tom Dickens
Approaches Taken
Notes:
181 and 359 determined by a program searching
for values to meet the goodness criteria.
Table method also used a program to find right
128 table values.
Tom Dickens
Generated Numbers
First 240 numbers:
1 255 117
4 73
35 65 133 50 218
226 208 81 76 71
60 170 216 82 145
50 209 28 68 182
196 68 28 34 183
243
2 216 237 149
189 13 80 163 78
35 99 131 69 227
38
6 115 211 85
196 244 31 77 162
254 47 135 179 203
213 181 171
5 209
71 136 138 67 178
85 167 38 109 111
222
156
229
187
28
10
132
137
27
56
226
23
217
39
0
125
132
135
134
128
119
106
89
68
43
13
236
199
158
113
232
185
182
223
52
181
98
59
64
113
206
87
12
237
250
15
223
203
211
248
56
148
13
161
81
30
6
10
43
103
167
239
4
228
145
9
78
94
59
228
88
153
165
126
34
Tom Dickens
21
99
237
179
181
242
108
34
20
66
171
81
51
81
171
110
114
226
190
6
186
218
102
94
194
146
206
118
138
11
230
197
1
152
139
219
134
141
241
176
203
66
22
69
208
252
223
207
202
210
229
5
48
104
172
251
87
190
50
177
49
22
119
84
172
129
210
159
232
172
237
170
227
152
201
27
226
85
116
63
182
217
168
35
74
29
156
199
158
33
Testing The Numbers
• Met The Defined Goodness Criteria
• Inspection
• Graphical Plots
– Plot number pairs on 256x256 grid.
Tom Dickens
Testing
1024 pairs
plotted
Tom Dickens
Testing
Half the
pairs plotted
Tom Dickens
Testing
All pairs
plotted
Tom Dickens
Testing
All pairs
with another
set of
constants
Tom Dickens
Implementation –
25 Bytes of 68HC11 Code
Random:
PSHB
; (1,3) Remember the current value of B
* scratch = seed * multiplier
LDAA #MULTIPLIER
; (2,2) A = #181
LDAB SEED_LOW
; (2,3) B = the low byte of the seed
MUL
; (1,10) D = A x B
STD RandomScratch
; (1,4) scratch = D
LDAA #MULTIPLIER
; (2,2) A = #181
LDAB SEED_HIGH
; (2,3) B = the high byte of the seed
MUL
; (1,10) D = A x B
* low byte of MUL result is added to the high byte of scratch
ADDB RandomScratch
; (2,3) B = B + scratch_high
STAB RandomScratch
; (2,3) scratch = seed * 181
*
LDD RandomScratch
; (2,4) D = scratch
ADDD #ADDER
; (3,4) D = D + 359
STD RandomSeed
; (2,4) remember new seed value
* (A = SEED_HIGH from ADDD instruction)
PULB
; (1,4) Restore the value of B
RTS
; (1,5) A holds the new 8-bit random number
Tom Dickens
Summary
•
•
•
•
•
RNG Studied
RNG Goodness Criteria Developed
Two RNG Methods Developed
Both Methods Were Critiqued
Equation-Based RNG Chosen For
Number Coverage and Code Size
• 68HC11 Code Implemented and
Tested
Tom Dickens