FFT6
void->void
pipeline FFT6() {
int N = 64;
add FFTTestSource(N);
add
FFTKernel2(N);
add
IFFTKernel2(N);
add CPrinter();
}
complex->complex
filter CombineDFT(int n) {
complex
wn;
init {
wn.real
= cos(2
* pi / n);
wn.imag
= -sin(2 * pi / n);
}
work
push n pop n {
int i;
complex
w, y0, y1, y1w, w_next;
w.real
= 1.0;
w.imag
= 0.0;
complex[n]
results;
for
(i = 0; i < n/2; i++)
{
y0 = peek(i);
y1 = peek(n/2 + i);
y1w = y1 * w;
results[i] = y0 + y1w;
results[n/2
+ i] = y0 - y1w;
w_next
= w * wn;
w = w_next;
}
for
(i = 0; i < n; i++)
{
pop();
push(results[i]);
}
}
}
complex->complex
filter CombineIDFT(int n, int maxN) {
complex
wn;
float invN;
init {
wn.real
= cos(2
* pi / n);
wn.imag
= sin(2 * pi / n);
}
work
push n pop n {
int i;
complex
w, y0, y1, y1w, w_next;
w.real
= 1.0;
w.imag
= 0.0;
complex[n]
results;
for
(i = 0; i < n/2; i++)
{
y0 = peek(i);
y1 = peek(n/2 + i);
y1w = y1 * w;
results[i] = y0 + y1w;
results[n/2
+ i] = y0 - y1w;
w_next
= w * wn;
w = w_next;
}
for
(i = 0; i < n; i++)
{
pop();
push(results[i]);
}
}
}
complex->complex
filter CombineIDFTFinal(int
n, int maxN) {
complex
wn;
float invN;
init {
invN = 1.0 / ((float)maxN);
wn.real
= cos(2
* pi / n);
wn.imag
= sin(2 * pi / n);
}
work
push n pop n {
int i;
complex
w, y0, y1, y1w, w_next;
w.real
= invN;
w.imag
= 0.0;
complex[n]
results;
for
(i = 0; i < n/2; i++)
{
y0 = invN * peek(i);
y1 = peek(n/2 + i);
y1w = y1 * w;
results[i] = y0 + y1w;
results[n/2
+ i] = y0 - y1w;
w_next
= w * wn;
w = w_next;
}
for
(i = 0; i < n; i++)
{
pop();
push(results[i]);
}
}
}
complex->complex
filter FFTReorderSimple(int
n) {
work
push n pop n {
int i;
for
(i = 0; i < n; i+=2)
{
push(peek(i));
}
for
(i = 1; i < n; i+=2)
{
push(peek(i));
}
for
(i=0;i<n;i++)
{
pop();
}
}
}
complex->complex
pipeline FFTReorder(int n)
{
for(int i=1; i<(n/2);
i*= 2)
add FFTReorderSimple(n/i);
}
complex->complex
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);
}
complex->complex
pipeline FFTKernel2(int n) {
add FFTReorder(n);
for(int j=2; j<=n; j*=2)
add CombineDFT(j);
}
complex->complex
pipeline IFFTKernel2(int n) {
add FFTReorder(n);
for(int j=2; j<n; j*=2)
add CombineIDFT(j, n);
add CombineIDFTFinal(n, n);
}
void->complex
filter FFTTestSource(int N)
{
work
push N pop 0 {
int i; complex c1, zero;
c1 = 1.0 + 0.0i;
zero
= 0.0;
push(zero);
push(c1);
for(i=0; i<N-2; i++)
push(zero);
}
}
complex->void
filter CPrinter()
{
work
push 0 pop 1 {
complex
c = pop();
print(c.real);
print(c.imag);
}
}
complex->complex
filter PassThroughPrinter()
{
work
push 1 pop 1 {
complex
c = pop();
print(c.real);
print(c.imag);
push
(c);
}
}