1 |
2 |
joachim |
#=======================================================================
|
2 |
|
|
#
|
3 |
|
|
# ca_prng_description.txt
|
4 |
|
|
# -----------------------
|
5 |
|
|
# README file for the ca_prng IP-core. The file
|
6 |
|
|
# contains a brief introduction to cellular automata based pattern
|
7 |
|
|
# generation, a description of the core and how to use the core.
|
8 |
|
|
#
|
9 |
|
|
#
|
10 |
|
|
# Author: Joachim Strömbergson
|
11 |
|
|
# Copyright (c) 2008, InformAsic AB
|
12 |
|
|
# All rights reserved.
|
13 |
|
|
#
|
14 |
|
|
# Redistribution and use in source and binary forms, with or without
|
15 |
|
|
# modification, are permitted provided that the following conditions
|
16 |
|
|
# are met:
|
17 |
|
|
# * Redistributions of source code must retain the above copyright
|
18 |
|
|
# notice, this list of conditions and the following disclaimer.
|
19 |
|
|
#
|
20 |
|
|
# * Redistributions in binary form must reproduce the above
|
21 |
|
|
# copyright notice, this list of conditions and the following
|
22 |
|
|
# disclaimer in the documentation and/or other materials
|
23 |
|
|
# provided with the distribution.
|
24 |
|
|
#
|
25 |
|
|
# THIS SOFTWARE IS PROVIDED BY InformAsic AB ''AS IS'' AND ANY EXPRESS
|
26 |
|
|
# OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
|
27 |
|
|
# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
|
28 |
|
|
# ARE DISCLAIMED. IN NO EVENT SHALL InformAsic AB BE LIABLE FOR ANY
|
29 |
|
|
# DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
|
30 |
|
|
# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
|
31 |
|
|
# GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
|
32 |
|
|
# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
|
33 |
|
|
# WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
|
34 |
|
|
# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
|
35 |
|
|
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
36 |
|
|
#
|
37 |
|
|
#=======================================================================
|
38 |
|
|
|
39 |
|
|
|
40 |
|
|
1: Introduction
|
41 |
|
|
---------------
|
42 |
|
|
A cellular automata CA) is a discrete model that consists of a grid (1D,
|
43 |
|
|
2D, 3D ) with objects called cells. Each cell can be in one of a given
|
44 |
|
|
set of states (on and off, different colours etc). Each cell has a set
|
45 |
|
|
of cells in close proximity. Given the current internal state of a cell,
|
46 |
|
|
the states of the cells in the close proximity and a given set of update
|
47 |
|
|
rules the next state of a cell can be determined. For more information
|
48 |
|
|
about cellular automata, se [1].
|
49 |
|
|
|
50 |
|
|
The ca_prng IP-core implements a 1D binary cellular automata with wrap
|
51 |
|
|
around at the edges (i.e. a ring). The update rules for a given
|
52 |
|
|
cell is based on the current state of the cell and the state of its
|
53 |
|
|
two nearest neighbours (left and right). The cell state for a given cell
|
54 |
|
|
(i), stored in the ca_state_reg register array can thus be given by
|
55 |
|
|
the state in cells (i-1), (i) and (i+1) as inputs to the update rule, se
|
56 |
|
|
figure 1.
|
57 |
|
|
|
58 |
|
|
---------------------
|
59 |
|
|
ca_state_reg: |...|i-1| i |i+1|...|
|
60 |
|
|
---------------------
|
61 |
|
|
\ | /
|
62 |
|
|
(update_rule)
|
63 |
|
|
|
|
64 |
|
|
---------------------
|
65 |
|
|
ca_state_new: |...|i-1| i |i+1|...|
|
66 |
|
|
---------------------
|
67 |
|
|
|
68 |
|
|
Figure 1: State update for a cell (i) based on neighbour cells
|
69 |
|
|
and the update rule.
|
70 |
|
|
|
71 |
|
|
With a three input, binary state the update rule set consists of eight
|
72 |
|
|
possible bit updates. In total the ca_prng supports 256 update
|
73 |
|
|
rules. For different rules and possible patterns, see [2].
|
74 |
|
|
|
75 |
|
|
The default update rule used in the ca_prng is rule30. Rule30 is an
|
76 |
|
|
uodate rule that when applied to the CA will produce a class III,
|
77 |
|
|
aperiodic, chaotic behaviour. The rule was discovered by Stephen Wolfram
|
78 |
|
|
[3].
|
79 |
|
|
|
80 |
|
|
|
81 |
|
|
2: IP-core description
|
82 |
|
|
----------------------
|
83 |
|
|
The ca_prng is a CA with 32 cells, implemented as a 32 bit wide
|
84 |
|
|
register. Each register has separate update logic that looks at the
|
85 |
|
|
current state of the register and its two nearest neighbours (with wrap
|
86 |
|
|
around). Register update latency is one cycle.
|
87 |
|
|
|
88 |
|
|
The actual update of the registers is controlled by external control
|
89 |
|
|
signals that allows a user to set the register initial pattern
|
90 |
|
|
(state) and request generation of new pattern.
|
91 |
|
|
|
92 |
|
|
Loading of initial pattern is is accomplished by setting the
|
93 |
|
|
input_patter_data port to the desired inital pattern and then
|
94 |
|
|
asserting the load_input_pattern port for one clock cycle.
|
95 |
|
|
|
96 |
|
|
Requesting a new pattern is accomplished by asserting the next_pattern
|
97 |
|
|
port.
|
98 |
|
|
|
99 |
|
|
After reset the ca_prng will use rule30 as the update rule. Changing the
|
100 |
|
|
rule is done by assigning the new rule to the update_rule port and then
|
101 |
|
|
asserting the load_update_rule for one clock cycle.
|
102 |
|
|
|
103 |
|
|
The generated pattern is available as a 32 bit value on the prng_data
|
104 |
|
|
port.
|
105 |
|
|
|
106 |
|
|
|
107 |
|
|
Figure 2 shows input and output ports of the ca_prng core.
|
108 |
|
|
|
109 |
|
|
|
110 |
|
|
––––––––––-
|
111 |
|
|
input_pattern_data | |
|
112 |
|
|
-------->| |
|
113 |
|
|
| |
|
114 |
|
|
load_init_pattern | |
|
115 |
|
|
------->| | prng_data
|
116 |
|
|
| |-------->
|
117 |
|
|
next_pattern | |
|
118 |
|
|
-------->| |
|
119 |
|
|
| |
|
120 |
|
|
update_rule | ca_prng |
|
121 |
|
|
-------->| |
|
122 |
|
|
| |
|
123 |
|
|
load_upate_rule | |
|
124 |
|
|
------->| |
|
125 |
|
|
| |
|
126 |
|
|
| |
|
127 |
|
|
| |
|
128 |
|
|
clk | |
|
129 |
|
|
-------->| |
|
130 |
|
|
| |
|
131 |
|
|
reset_n | |
|
132 |
|
|
-------->| |
|
133 |
|
|
|––––––––––-|
|
134 |
|
|
|
135 |
|
|
Figure 2: Input and output ports of the ca_prng core.
|
136 |
|
|
|
137 |
|
|
The ca_prng core is a positive edge triggered synchronous design. All
|
138 |
|
|
internal registers are equipped with a synhronous, active low reset.
|
139 |
|
|
|
140 |
|
|
|
141 |
|
|
3: IP-core delivery contents
|
142 |
|
|
----------------------------
|
143 |
|
|
The ca_prng is provided as RTL source code written in Verilog 2001
|
144 |
|
|
compliant code. The ca_prng delivery also contains a testbench that
|
145 |
|
|
verifies the functionality. Finally the core contains a functional model
|
146 |
|
|
written in Python as well as documentation (this file).
|
147 |
|
|
|
148 |
|
|
The provided testbench has been used to verify the core using the
|
149 |
|
|
ModelSim as well as the Icarus Verilog simulators.
|
150 |
|
|
|
151 |
|
|
The ca_prng core has been implemented in FPGA tools from Altera and
|
152 |
|
|
Xilinx. The following table lists the area and speed achieved.
|
153 |
|
|
|
154 |
|
|
Altera Devices (implemented using Quartus 9.0)
|
155 |
|
|
Stratix II
|
156 |
|
|
---------
|
157 |
|
|
Device: EP2S15
|
158 |
|
|
ALUT: 106
|
159 |
|
|
Reg: 40
|
160 |
|
|
Mem: 0
|
161 |
|
|
DSP: 0
|
162 |
|
|
fmax: 300 MHz
|
163 |
|
|
|
164 |
|
|
Cyclone III
|
165 |
|
|
-----------
|
166 |
|
|
Device: EP3C5
|
167 |
|
|
LE: 234
|
168 |
|
|
Reg: 40
|
169 |
|
|
Mem: 0
|
170 |
|
|
Mult: 0
|
171 |
|
|
fmax: 250 MHz
|
172 |
|
|
|
173 |
|
|
|
174 |
|
|
Xilinx Devices (implemented using ISE 11.0)
|
175 |
|
|
Spartan 3A
|
176 |
|
|
----------
|
177 |
|
|
Device: xc3s50a-5
|
178 |
|
|
Slices: 93
|
179 |
|
|
Reg: 48 (replicated update_rule_reg)
|
180 |
|
|
Mem: 0
|
181 |
|
|
Mult: 0
|
182 |
|
|
fmax: 250 MHz
|
183 |
|
|
|
184 |
|
|
Virtex-5
|
185 |
|
|
--------
|
186 |
|
|
Device: xc5vlx30-3
|
187 |
|
|
Slices: 42
|
188 |
|
|
Reg: 40
|
189 |
|
|
Mem: 0
|
190 |
|
|
Mult: 0
|
191 |
|
|
fmax: 400 MHz
|
192 |
|
|
|
193 |
|
|
|
194 |
|
|
4: References
|
195 |
|
|
-------------
|
196 |
|
|
[1] Wikipedia. Cellular Automaton. Web page. 2009.
|
197 |
|
|
http://en.wikipedia.org/wiki/Cellular_automaton
|
198 |
|
|
|
199 |
|
|
[2] Wolfram MathWorld. Elementary Cellular Automaton. Web
|
200 |
|
|
page. 2009.
|
201 |
|
|
http://mathworld.wolfram.com/ElementaryCellularAutomaton.html
|
202 |
|
|
|
203 |
|
|
[3] Wikipedia. Rule 30 description. Web page. 2009.
|
204 |
|
|
http://en.wikipedia.org/wiki/Rule_30
|
205 |
|
|
|
206 |
|
|
#=======================================================================
|
207 |
|
|
# EOF ca_prng_description.txt
|
208 |
|
|
#=======================================================================
|
209 |
|
|
|