1 <?xml version="1.0" encoding="UTF-8"?>
2 <processnetwork xmlns="http://www.tik.ee.ethz.ch/~shapes/schema/PROCESSNETWORK" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.tik.ee.ethz.ch/~shapes/schema/PROCESSNETWORK
3 http://www.tik.ee.ethz.ch/~shapes/schema/processnetwork.xsd" name="FFT">
6 N is the number of FFT points
7 number_of_layers = ld(N)
8 processes_per_layer = N/2
12 <variable value="4" name="N"/>
13 <variable value="2" name="NUMBER_OF_LAYERS"/>
14 <variable value="2" name="PROCESSES_PER_LAYER"/>
18 <variable value="8" name="N"/>
19 <variable value="3" name="NUMBER_OF_LAYERS"/>
20 <variable value="4" name="PROCESSES_PER_LAYER"/>
23 <variable value="16" name="N"/>
24 <variable value="4" name="NUMBER_OF_LAYERS"/>
25 <variable value="8" name="PROCESSES_PER_LAYER"/>
28 <variable value="32" name="N"/>
29 <variable value="5" name="NUMBER_OF_LAYERS"/>
30 <variable value="16" name="PROCESSES_PER_LAYER"/>
34 <variable value="64" name="N"/>
35 <variable value="6" name="NUMBER_OF_LAYERS"/>
36 <variable value="32" name="PROCESSES_PER_LAYER"/>
40 <variable value="128" name="N"/>
41 <variable value="7" name="NUMBER_OF_LAYERS"/>
42 <variable value="64" name="PROCESSES_PER_LAYER"/>
46 <variable value="256" name="N"/>
47 <variable value="8" name="NUMBER_OF_LAYERS"/>
48 <variable value="128" name="PROCESSES_PER_LAYER"/>
53 public static int bitreverse(int n, int N)
55 String numberString = Integer.toString(n, 2); //binary representation of n
57 //prepend zeros until string is N characters long
58 while (numberString.length() < N)
60 numberString = "0" + numberString;
64 char[] numberCharArray = numberString.toCharArray();
65 for (int count = 0; count < numberCharArray.length / 2; count++)
67 char help = numberCharArray[count];
68 numberCharArray[count] = numberCharArray[N - 1 - count];
69 numberCharArray[N - 1 - count] = help;
72 //convert back to integer
73 return Integer.valueOf(String.valueOf(numberCharArray), 2);
80 public static int butterfly(int layer, int p, int addOffset)
82 int index = 2 * (p % (1 << (layer - 1))) +
83 p / (1 << (layer - 1)) +
84 (p / (1 << layer)) * ((1 << (layer + 1)) - 2);
87 return index + (1 << layer);
94 <!-- instantiate processes -->
95 <process name="generator">
96 <iterator variable="i" range="N">
97 <port type="output" name="input_coefficients">
98 <append function="i"/>
101 <source type="c" location="generator.c"/>
104 <process name="consumer">
105 <iterator variable="i" range="N">
106 <port type="input" name="output_coefficients">
107 <append function="i"/>
110 <source type="c" location="consumer.c"/>
113 <iterator variable="i" range="NUMBER_OF_LAYERS">
114 <iterator variable="j" range="PROCESSES_PER_LAYER">
115 <process name="fft2">
116 <append function="i"/>
117 <append function="j"/>
118 <port type="input" name="inA"/>
119 <port type="input" name="inB"/>
120 <port type="output" name="outA"/>
121 <port type="output" name="outB"/>
122 <source type="c" location="fft2.c"/>
127 <!-- instantiate channels -->
128 <!-- channels for input and output coefficients -->
129 <iterator variable="i" range="N">
130 <sw_channel type="fifo" size="16" name="inputchannel">
131 <append function="i"/>
132 <port type="input" name="in"/>
133 <port type="output" name="out"/>
135 <sw_channel type="fifo" size="16" name="outputchannel">
136 <append function="i"/>
137 <port type="input" name="in"/>
138 <port type="output" name="out"/>
142 <!-- channels for butterfly network -->
143 <iterator variable="layer" range="NUMBER_OF_LAYERS - 1">
144 <iterator variable="i" range="N">
145 <sw_channel type="fifo" size="16" name="butterflychannel">
146 <append function="layer"/>
147 <append function="i"/>
148 <port type="input" name="in"/>
149 <port type="output" name="out"/>
154 <!-- instantiate connections -->
155 <!-- connections from input generator to input channel and from output channel to output consumer -->
156 <iterator variable="i" range="N">
157 <connection name="input_connection">
158 <append function="i"/>
159 <origin name="generator">
160 <port name="input_coefficients">
161 <append function="i"/>
164 <target name="inputchannel">
165 <append function="i"/>
169 <connection name="output_connection">
170 <append function="i"/>
171 <origin name="outputchannel">
172 <append function="i"/>
175 <target name="consumer">
176 <port name="output_coefficients">
177 <append function="i"/>
183 <!-- connections from FFT2 to channels -->
184 <iterator variable="layer" range="NUMBER_OF_LAYERS - 1">
185 <iterator variable="i" range="PROCESSES_PER_LAYER">
186 <connection name="layerkconnection_A">
187 <append function="layer + 1"/>
188 <append function="i"/>
190 <append function="layer"/>
191 <append function="i"/>
194 <target name="butterflychannel">
195 <append function="layer"/>
196 <append function="2 * i"/>
200 <connection name="layerkconnection_B">
201 <append function="layer + 1"/>
202 <append function="i"/>
204 <append function="layer"/>
205 <append function="i"/>
208 <target name="butterflychannel">
209 <append function="layer"/>
210 <append function="2 * i + 1"/>
217 <!-- connections from channels to FFT2 -->
218 <!-- connections from input channels to first FFT layer -->
219 <iterator variable="i" range="PROCESSES_PER_LAYER">
220 <connection name="layer1connection_A">
221 <append function="i"/>
222 <origin name="inputchannel">
223 <append function="bitreverse(2 * i, NUMBER_OF_LAYERS)"/>
226 <target name="fft2_0">
227 <append function="i"/>
231 <connection name="layer1connection_B">
232 <append function="i"/>
233 <origin name="inputchannel">
234 <append function="bitreverse(2 * i + 1, NUMBER_OF_LAYERS)"/>
237 <target name="fft2_0">
238 <append function="i"/>
244 <!-- connections from last FFT layer to output channels -->
245 <iterator variable="i" range="PROCESSES_PER_LAYER">
246 <connection name="lastlayerconnection_A">
247 <append function="i"/>
249 <append function="NUMBER_OF_LAYERS - 1"/>
250 <append function="i"/>
253 <target name="outputchannel">
254 <append function="i"/>
258 <connection name="lastlayerconnection_B">
259 <append function="i"/>
261 <append function="NUMBER_OF_LAYERS - 1"/>
262 <append function="i"/>
265 <target name="outputchannel">
266 <append function="i + PROCESSES_PER_LAYER"/>
272 <!-- other connections -->
273 <iterator variable="layer" range="NUMBER_OF_LAYERS - 1">
274 <iterator variable="i" range="PROCESSES_PER_LAYER">
275 <connection name="FFTconnection_A">
276 <append function="layer"/>
277 <append function="i"/>
278 <origin name="butterflychannel">
279 <append function="layer"/>
280 <append function="butterfly(layer + 1, i, 0)"/>
284 <append function="layer + 1"/>
285 <append function="i"/>
289 <connection name="FFTconnection_B">
290 <append function="layer"/>
291 <append function="i"/>
292 <origin name="butterflychannel">
293 <append function="layer"/>
294 <append function="butterfly(layer + 1, i, 1)"/>
298 <append function="layer + 1"/>
299 <append function="i"/>