document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. /*
  2. -------------------------------------------------------------------------------------------------
  3.  Assignment No:8
  4.  Title: 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)).
  5. -------------------------------------------------------------------------------------------------
  6. */
  7.  
  8. #include<iostream.h>
  9. #include<conio.h>
  10. #include<math.h>
  11.  
  12. #define max 30
  13.  
  14. void main()
  15. {
  16.     int n,a,b,j,bit[max][5]={0},bitcount=0,k,stages,l;
  17.     float Wr=0,Wi=0,temp1,temp2;
  18.     float xr[max]={0},xi[max]={0},Xr[max]={0},Xi[max]={0},temp;
  19.     clrscr();
  20.     cout<<"\\n How Many point dft?";
  21.     cin>>n;
  22.     for(int i=0;i<n;i++)
  23.     {
  24.         cout<<"\\n Enter x["<<i<<"](Real Imaginary):";
  25.         cin>>xr[i]>>xi[i];
  26.     }
  27.     // conversion of indices in binary
  28.     for(i=0;i<n;i++)
  29.     {
  30.         a=i;
  31.         j=0;
  32.         while(a!=0)
  33.         {
  34.                 bit[i][j++]=a%2;
  35.                 a=a/2;
  36.             if(i==n-1)
  37.                 bitcount++;
  38.             }
  39.     }
  40.     cout<<"\\n\\n BIT COUNT:"<<bitcount;
  41.     bitcount--;
  42.     //Print bits of reverse indices from longest index to smallest
  43.     cout<<"\\n\\n Reverse bits are:";
  44.     for(i=0;i<n;i++)
  45.     {
  46.         cout<<endl;
  47.         for(j=0;j<=bitcount;j++)
  48.         cout<<" "<<bit[i][j];
  49.     }
  50.         cout<<"\\n\\n DECIMAL EQUIVALENT OF REVERSED BIT INDICES:";
  51.     for(i=0;i<n;i++)
  52.     {
  53.             a=0;
  54.             for(j=0,k=bitcount;k>=0;k--,j++)
  55.             {
  56.                 a=a+(bit[i][j]*(pow(2,k)));
  57.             }
  58.             cout<<endl<<a;
  59.             Xr[i]=xr[a];
  60.             Xi[i]=xi[a];
  61.         }
  62.     cout<<"\\n \\n array after swapping:";
  63.         for(i=0;i<n;i++)
  64.             cout<<endl<<Xr[i]<<"+("<<Xi[i]<<")j";
  65.         //Calculation of no of stages
  66.         for(i=1;n!=pow(2,i);i++);
  67.             stages=i;
  68.         cout<<"\\n\\n  NO OF STAGES:"<<stages<<endl;
  69.     //Stage calculation
  70.         for(k=1;k<=stages;k++) //loop for stages
  71.         for(l=0;l<n;l=l+pow(2,k)) //loop for butterfly
  72.         {
  73.             b=0;
  74.             for(i=l;i<(l+pow(2,k-1));i=i+1)  //loop for each pt in butterfly
  75.             {
  76.                 j=i+pow(2,k-1);
  77.                 // calculating twiddle factor
  78.                 Wr=cos(2*M_PI*b/n);
  79.                 Wi=-sin(2*M_PI*b/n);
  80.                 b++;
  81.                 if(k==2 && stages>2)
  82.                     b++;
  83.                 //multiplying with twiddle factor
  84.                 temp1=(Xr[j]*Wr)-(Xi[j]*Wi);
  85.                 temp2=(Xr[j]*Wi)+(Xi[j]*Wr);
  86.                 //calculating first element
  87.                 xr[i]=Xr[i]+temp1;
  88.                 xi[i]=Xi[i]+temp2;
  89.                 //calculating second element
  90.                 xr[j]=Xr[i]-temp1;
  91.                 xi[j]=Xi[i]-temp2;
  92.                 Xr[i]=xr[i];
  93.                 Xi[i]=xi[i];
  94.                 Xr[j]=xr[j];
  95.                 Xi[j]=xi[j];
  96.             }
  97.             }
  98.         cout<<"\\N DFT OF GIVEN SEQUENCE IS:\\n";
  99.         for(i=0;i<n;i++)
  100.             cout<<endl<<Xr[i]<<"+("<<Xi[i]<<")j";
  101.         getch();
  102.  }
');