dsp..C program to compute N-point Radix-2 DIT FFT algorithm.

/*  C program to compute N-point Radix-2 DIT FFT algorithm.

 Inputs: 1.Number of samples of x(n)
2.Values of samples of x(n)

 Output: Real and imaginary part of DFT X(k).
==================================================================*/

#include<stdio.h>
#include<conio.h>
#include<math.h>
#define SWAP(a,b)var=(a);(a)=(b);(b)=var;

void main()
{
 int N,n,m,j,k,i,p;
 float data[200],real1,imag1,real2,imag2,var;
 float costheta,sintheta,t,Theta;

 clrscr();
 printf("\n\t\t Readix-2 DIT FFT algorithm\n\n");

 printf("\n\n Enter the number of samples in the sequence x(n),N=");
 scanf("%d",&N);

 printf("\n\n Enter the Samples of the Sequence x(n):\n");
 printf("\n Real part  Imaginary part");

 for(n=1;n<=N;n++)
 {
   printf("\n x(%d)=",n-1);
   scanf("%f%f",&data[2*n-1],&data[2*n]);
 }
 n=N<<1;
 j=1;

 for(i=1;i<n;i=i+2)
 {
  if(j>i)
  {
   SWAP(data[j],data[i]);
   SWAP(data[j+1],data[i+1]);
  }
  m=n>>1;
  while(m>=2 && j>m)
  {
   j-=m;
   m>>=1;
  }
  j+=m;
 }

 k=1;m=1;t=0.0;
 while((N/(2*k))>=1)
 {
  p=pow(2,m);
  n=1;
  Theta=((2*M_PI)/(float)p)*t;
  costheta=cos(Theta);
  sintheta=sin(Theta);

  for(i=1;i<=2*N;)
  {
   real1=data[i]+costheta*data[i+p]+sintheta*data[i+1+p];
   imag1=data[i+1]+costheta*data[i+1+p]-sintheta*data[i+p];
   real2=data[i]-costheta*data[i+p]-sintheta*data[i+1+p];
   imag2=data[i+1]-costheta*data[i+1+p]+sintheta*data[i+p];

   data[i]=real1;
   data[i+1]=imag1;
   data[i+p]=real2;
   data[i+p+1]=imag2;

   if(n<k)
   {
    t=t+1;
    Theta=((2*M_PI)/(float)p)*t;
    costheta=cos(Theta);
    sintheta=sin(Theta);
   }
   else
   {
    i=i+p+2;
    n=1;
    t=0;
    Theta=((2*M_PI)/(float)p)*t;
    costheta=cos(Theta);
    sintheta=sin(Theta);
   }
  }
  k=k<<1;
  m++;
 }

 printf("\n\n Output of DIT FFt is as follows:\n");
 printf("\n\n Real part of X[k]       Imaginary part of X[k]");
 for(n=1;n<=N;n++)
 {
  printf("\n%f\t\t %f ",data[2*n-1],data[2*n]);
 }
 getch();
}

op*********

                 Readix-2 DIT FFT algorithm

 Enter the number of samples in the sequence x(n),N=8

 Enter the samples of the sequence x(n):

       Real Part   Imaginary Part

 x(0)=   0.5           0

 x(1)=   0.5           0

 x(2)=   0.5           0

 x(3)=   0.5           0

 x(4)=    0            0   

 x(5)=    0            0   

 x(6)=    0            0   

 x(7)=    0            0   

 Output of DIT FFT is as follows

       Real part of X(k)   Imaginary part of X(k)

         2.000000             0.000000

         0.500000             -1.207107  

         0.000000             0.000000

         0.500000             -0.207107

         0.000000             0.000000

         0.500000             0.207107

         0.000000             0.000000

 

         0.500000             1.207107