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);

    }

}