FFT2
void->void
pipeline FFT2() {
add FFTTestSource(64);
add
FFTKernel2(64);
add FloatPrinter();
}
float->float
filter CombineDFT(int n) {
float wn_r, wn_i;
init {
wn_r
= (float)cos(2 * 3.141592654
/ n);
wn_i
= (float)sin(-2 * 3.141592654 / n);
}
work
push 2*n pop 2*n {
int i;
float
w_r = 1;
float
w_i = 0;
float[2*n]
results;
for
(i = 0; i < n; i += 2)
{
// this is a
temporary work-around since there seems to be
// a bug in field
prop that does not propagate nWay into the
// array
references. --BFT
//int tempN = nWay;
//Fixed --jasperln
// removed nWay, just using n --sitij
float y0_r = peek(i);
float y0_i = peek(i+1);
float y1_r = peek(n + i);
float y1_i = peek(n + i + 1);
float y1w_r = y1_r * w_r - y1_i * w_i;
float y1w_i = y1_r * w_i + y1_i * w_r;
results[i] = y0_r + y1w_r;
results[i + 1] = y0_i + y1w_i;
results[n + i] = y0_r - y1w_r;
results[n + i + 1] = y0_i - y1w_i;
float w_r_next = w_r * wn_r - w_i
* wn_i;
float w_i_next = w_r * wn_i + w_i
* wn_r;
w_r = w_r_next;
w_i = w_i_next;
}
for
(i = 0; i < 2 * n; i++)
{
pop();
push(results[i]);
}
}
}
float->float
filter FFTReorderSimple(int
n) {
int totalData;
init {
totalData = 2*n;
}
work
push 2*n pop 2*n {
int i;
for
(i = 0; i < totalData; i+=4)
{
push(peek(i));
push(peek(i+1));
}
for
(i = 2; i < totalData; i+=4)
{
push(peek(i));
push(peek(i+1));
}
for
(i=0;i<n;i++)
{
pop();
pop();
}
}
}
float->float
pipeline FFTReorder(int n)
{
for(int i=1; i<(n/2);
i*= 2)
add FFTReorderSimple(n/i);
}
float->float
pipeline FFTKernel1(int n) {
if(n>2)
{
add splitjoin {
split roundrobin(2);
add FFTKernel1(n/2);
add FFTKernel1(n/2);
join roundrobin(n);
}
}
add CombineDFT(n);
}
float->float splitjoin FFTKernel2(int n) {
split roundrobin(2*n);
for(int i=0; i<2;
i++) {
add
pipeline {
add FFTReorder(n);
for(int j=2; j<=n; j*=2)
add
CombineDFT(j);
}
}
join roundrobin(2*n);
}
void->float
filter FFTTestSource(int N)
{
init {
}
work
push 2*N pop 0 {
int i;
push(0.0);
push(0.0);
push(1.0);
push(0.0);
for(i=0; i<2*(N-2); i++)
push(0.0);
}
}
float->void
filter FloatPrinter
{
init
{ }
work
push 0 pop 1 {
print(pop());
}
}