FFT5

 

/////////////////////////////////

// An iterative implementation of the FFT Algorithm

// -Satish Ramaswamy

////////////////////////////////

 

void->complex filter source() {

  work push 8{     

    complex t;

    t.imag = 0;

    t.real = 0.9501; push(t);

    t.real = 0.2311; push(t);

    t.real = 0.6068; push(t);

    t.real = 0.4860; push(t);

    t.real = 0.8913; push(t);

    t.real = 0.7621; push(t);

    t.real = 0.4565; push(t);

    t.real = 0.0185; push(t);

 

  }

}

 

//////////////////////////////////

// The following recursive pipeline serves to bitreverse

// every N-inputs.

//////////////////////////////////

 

complex->complex pipeline bitreverse(int N) {

  if(N == 1) {

     add Identity<complex>;

  }

  else {

    add splitjoin {

      split roundrobin;

      add bitreverse(N/2);

      add bitreverse(N/2);

      join roundrobin(N/2);

    }

  }

}

 

float->void filter sink {

  work pop 1 {

    print(pop());

  }

}

 

///////////////////////////////////////

// Basic butterfly structure in FFT

///////////////////////////////////////

 

complex->complex filter butterfly(int r, int num) {

  work pop 2 peek 2 push 2 {

    //exponential weights for butterfly

    complex WN1; complex WN2;

    WN1.real = cos(-2*pi*r/num);

    WN1.imag = sin(-2*pi*r/num);

    WN2.real = cos(-2*pi*(r+num/2)/num);

    WN2.imag = sin(-2*pi*(r+num/2)/num);

    complex one = pop();

    complex two = pop();

 

    push(one+two*WN1);

    push(one+two*WN2);

  }

}

   

////////////////////////////////////////////////

// Creates the sth stage of the FFT's log(N) stages

////////////////////////////////////////////////

 

complex->complex pipeline FFTstage(int N, int s) {

  int num = 1;

  for(int i=0;i<s;i++) num*=2;

  if(num == N) {

    add splitFinal(N);

  }

  else {   

    add split1(N, num);

  }

}

 

 

////////////////////////////////////////

// The following 3 splitX splitjoins are helper functions

// for FFTstage

////////////////////////////////////////

 

complex->complex splitjoin split1(int N, int num) { 

  split roundrobin(num);

    for(int i=1; i<=N/num; i++) {

      add split2(i,num);

    }

    join roundrobin(num);

}

 

complex->complex splitjoin split2(int i, int num) {

  split roundrobin(1);

        for(int j=0;j<num/2;j++) {

          add butterfly(j , num);

        }

  join roundrobin(1);

}

 

complex->complex splitjoin splitFinal(int N) {

  split roundrobin(1);

  for(int i=0;i<N/2;i++) add butterfly(i,N);

  join roundrobin(1);

}

 

///////////////////////////////////

// Calculates magnitude of complex stream

///////////////////////////////////

 

complex->float filter magnitude() {

  work pop 1 peek 1 push 1 {

    complex c = pop();

    push(sqrt(c.real*c.real+c.imag*c.imag));

  }

}

 

complex->complex pipeline FFTKernel(int N) {

  add bitreverse(16);

  for(int i=1;i<4;i++) add FFTstage(16,i);

}  

void->void pipeline FFT5 {

  add source();

  add FFTKernel(16);

  add magnitude();

  add sink();

}