wrong with my FFT program

This is a discussion on wrong with my FFT program within the C Programming forums, part of the General Programming Boards category; hi,all.I wrote this program to implement the FFT algorithm.Running with wrong answer.can anybody tell me what mistake i made?thanks! Code: ...

  1. #1
    Registered User rpbear's Avatar
    Join Date
    Nov 2009
    Posts
    18

    Smile wrong with my FFT program

    hi,all.I wrote this program to implement the FFT algorithm.Running with wrong answer.can anybody tell me what mistake i made?thanks!
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    
    #define PI 3.1415926
    #define N 16 //the length
    #define W_RE (cos(-2.0*PI/N))
    #define W_IM (sin(-2.0*PI/N))
    
    void recursive_fft(double [],int,double [],double []);
    
    int main(){
    
    	double x[N] = {0.5751,0.4514,0.0439,0.0272,
                          	    0.3127,0.0129,0.3840,0.6831,
                                0.0928,0.0353,0.6124,0.6085,
                                0.0158,0.0164,0.1901,0.5869};
    	double y_re[N],y_im[N];
    
    	recursive_fft(x,N,y_re,y_im);
    
    	/*output*/
    	for(int i = 0;i<N;i++){
    		printf("%lf",y_re[i]);
    		if(y_im[i])
    			printf(" + %lfi",y_im[i]);
            printf("\n");
    	}
    	return 0;
    }
    
    /*x is the input DFT,len_x is the length
     *y_re and y_im ===> real part and image part of the result
     * */
    void recursive_fft(double x[],int len_x,\
    						double y_re[],double y_im[]){
    
    	double re_w = 1.0,im_w = 0;
    	double x_even[len_x/2],x_odd[len_x/2];
    	double y1_re[len_x/2] ,y1_im[len_x/2] ;
    	double y2_re[len_x/2] ,y2_im[len_x/2] ;
    	int index_even = 0,index_odd = 0;
    
    	for(int i=0;i<len_x/2;i++){
                y1_re[i] = y1_im[i] = y2_re[i] = y2_im[i] = 0;
        }
    	if(1 == len_x){
    		y_re[0] = x[0];y_im[0] = 0;
    		return ;
    	}
    
    	
    	for(int i = 0;i<len_x;i++){
    		if(i % 2 == 0){/*even */
    			x_even[index_even++] = x[i];
    		}else{
    			x_odd[index_odd++] = x[i];
    		}
    	}
    
    	recursive_fft(x_odd,index_odd,y1_re,y1_im);
    	recursive_fft(x_even,index_even,y2_re,y2_im);
    
    	for(int k = 0;k<len_x/2;k++){
    		y_re[k] = y1_re[k]*re_w - im_w*y1_im[k] + y2_re[k];
    		y_im[k] = y1_im[k]*re_w + y1_re[k]*im_w + y2_im[k];
    		y_re[k+len_x/2] = im_w*y1_im[k] - y1_re[k]*re_w + y2_re[k];
    		y_im[k+len_x/2] = -1*y1_im[k]*re_w - y1_re[k]*im_w + y2_im[k];
    		re_w = re_w*W_RE - im_w*W_IM;
    		im_w = im_w*W_RE + re_w*W_IM;
    	}
    }

  2. #2
    Registered User rpbear's Avatar
    Join Date
    Nov 2009
    Posts
    18
    any hint?

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Assuming you're using Cooley-Tukey DIT (which is the best fit I could find on Wiki), it would seem that you're always using exp(-2πi/N), when that N should be changing with the recursion to be exp(-2πi/len_x).

  4. #4
    Registered User rpbear's Avatar
    Join Date
    Nov 2009
    Posts
    18
    Quote Originally Posted by tabstop View Post
    Assuming you're using Cooley-Tukey DIT (which is the best fit I could find on Wiki), it would seem that you're always using exp(-2πi/N), when that N should be changing with the recursion to be exp(-2πi/len_x).
    thanks,I do use the Cooley-Tukey algorithm.I modified my code as you said,and the answer's still wrong,did u find any logical mistake in my code?

  5. #5
    Registered User rpbear's Avatar
    Join Date
    Nov 2009
    Posts
    18

    find the bug

    replace the code
    Code:
     re_w = re_w*W_RE - im_w*W_IM;
            im_w = im_w*W_RE + re_w*W_IM;
    with
    Code:
    save_re = re_w;save_im = im_w;
    		re_w = save_re*W_RE(len_x) - save_im*W_IM(len_x);
    		im_w = save_im*W_RE(len_x) + save_re*W_IM(len_x);

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Client-server system with input from separate program
    By robot-ic in forum Networking/Device Communication
    Replies: 3
    Last Post: 01-16-2009, 02:30 PM
  2. Using variables in system()
    By Afro in forum C Programming
    Replies: 8
    Last Post: 07-03-2007, 12:27 PM
  3. Replies: 5
    Last Post: 01-13-2007, 01:14 AM
  4. BOOKKEEPING PROGRAM, need help!
    By yabud in forum C Programming
    Replies: 3
    Last Post: 11-16-2006, 10:17 PM
  5. What is wrong with my code? My first program......
    By coreyt1111 in forum C++ Programming
    Replies: 11
    Last Post: 11-14-2006, 01:03 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21