N-Point FFT Algorithm to find DFT or IDFT

N-Point FFT Algorithm to find DFT or IDFT

Problem Statement : Implement the N-point radix-2 DIT or DIF FFT algorithm to find DFT or IDFT of given sequence x (n). (Analyze the output for different N Program should work for any value of N (generalized)) .

1:  #include<conio.h>  
2:  #include<stdio.h>  
3:  #include<complex.h>  
4:  #include<stdlib.h>  
5:  complex data[64];  
6:  void main()  
7:  {  
8:     int ind(int n,int i);  
9:     void split(int N,int n);  
10:     double x,y;  
11:     int N,n,i,j,k,ch;  
12:     clrscr();  
13:     cout<<"    Radix-2 DIT FFT algorithm FOR DFT & IDFT\n\n";  
14:     cout<<"Enter the number of samples in the sequence x(n), N = ";  
15:     cin>>N;           // number of samples in x(n)  
16:     cout<<"\nEnter the samples of sequence x(n)";  
17:     for(n=0;n<N;n++)  
18:     {  
19:      cout<<"\nReal x("<<n<<") = ";    // enter values of samples of x(n)  
20:      cin>>x;  
21:      cout<<"Imag x("<<n<<") = ";    // enter values of samples of x(n)  
22:      cin>>y;  
23:      data[n]=complex(x,y);  
24:     }  
25:     cout<<"\n\t1.DFT\n\t2.IDFT\n\t3.EXIT\n\n\tEnter Ur Choice::";  
26:     cin>>ch;  
27:     switch(ch)  
28:     {  
29:     case 1:  
30:          n=log(N)/log(2);  
31:          split(N,n);  
32:          i=0;  
33:          while(i!=n)  
34:          {  
35:          int p1=pow(2,i),p2=pow(2,i+1),h=(N/p2);  
36:          for(j=0;j<h;j++)  
37:          {  
38:            for(k=0;k<p1;k++)  
39:            {  
40:             complex temp,temp1,temp2;  
41:             temp=complex(0.0,-(44.0*k)/(7.0*p2));  
42:             temp=exp(temp);  
43:             temp1=data[p2*j+k]+temp*data[p2*j+k+p1];  
44:             temp2=data[p2*j+k]-temp*data[p2*j+k+p1];  
45:             data[p2*j+k]=temp1;  
46:             data[p2*j+k+p1]=temp2;  
47:            }  
48:          }  
49:          i++;  
50:          }  
51:          break;  
52:     case 2:  
53:          n=log(N)/log(2);  
54:          i=n-1;  
55:          while(i>=0)  
56:          {  
57:          int p1=pow(2,i),p2=pow(2,i+1),h=(N/p2);  
58:          for(j=0;j<h;j++)  
59:          {  
60:            for(k=0;k<p1;k++)  
61:            {  
62:             complex temp,temp1,temp2;  
63:             temp=complex(0.0,(44.0*k)/(7.0*p2));  
64:             temp=exp(temp);  
65:             temp1=(data[p2*j+k]+data[p2*j+k+p1]);  
66:             temp2=((data[p2*j+k]-data[p2*j+k+p1])*temp);  
67:             if(i==n-1)  
68:             {  
69:             temp1=temp1/N;  
70:             temp2=temp2/N;  
71:             }  
72:             data[p2*j+k]=temp1;  
73:             data[p2*j+k+p1]=temp2;  
74:            }  
75:          }  
76:          i--;  
77:          }  
78:          split(N,n);  
79:          break;  
80:     case 3:  
81:         exit(0);  
82:     }  
83:     clrscr();  
84:     cout<<"\nReal(z)";  
85:     gotoxy(30,2);  
86:     cout<<"Imag(z)\n";  
87:     for(i=0;i<N;i++)  
88:     {  
89:     printf("%1.2lf",real(data[i]));  
90:     gotoxy(30,3+i);  
91:     printf("%1.2lf\n",imag(data[i]));  
92:     }  
93:     getch();  
94:  }  
95:  int ind(int i,int n)  
96:  {  
97:   int j,temp,num=0;  
98:   for(j=0;j<n;j++)  
99:   {  
100:   temp=i&(int)(pow(2,j));  
101:   if(temp!=0)  
102:    num+=pow(2,n-j-1);  
103:   }  
104:   return num;  
105:  }  
106:  void split(int N,int n)  
107:  {  
108:     int index,i;  
109:     complex temp;  
110:     for(i=0;i<N;i++)  
111:     {  
112:      index=ind(i,n);  
113:      if(index>i)  
114:      {  
115:       temp=data[i];  
116:       data[i]=data[index];  
117:       data[index]=temp;  
118:      }  
119:     }  
120:  }