/*
-------------------------------------------------------------------------------------------------
Assignment No:8
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)).
-------------------------------------------------------------------------------------------------
*/
#include<iostream.h>
#include<conio.h>
#include<math.h>
#define max 30
void main()
{
int n,a,b,j,bit[max][5]={0},bitcount=0,k,stages,l;
float Wr=0,Wi=0,temp1,temp2;
float xr[max]={0},xi[max]={0},Xr[max]={0},Xi[max]={0},temp;
clrscr();
cout<<"\\n How Many point dft?";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"\\n Enter x["<<i<<"](Real Imaginary):";
cin>>xr[i]>>xi[i];
}
// conversion of indices in binary
for(i=0;i<n;i++)
{
a=i;
j=0;
while(a!=0)
{
bit[i][j++]=a%2;
a=a/2;
if(i==n-1)
bitcount++;
}
}
cout<<"\\n\\n BIT COUNT:"<<bitcount;
bitcount--;
//Print bits of reverse indices from longest index to smallest
cout<<"\\n\\n Reverse bits are:";
for(i=0;i<n;i++)
{
cout<<endl;
for(j=0;j<=bitcount;j++)
cout<<" "<<bit[i][j];
}
cout<<"\\n\\n DECIMAL EQUIVALENT OF REVERSED BIT INDICES:";
for(i=0;i<n;i++)
{
a=0;
for(j=0,k=bitcount;k>=0;k--,j++)
{
a=a+(bit[i][j]*(pow(2,k)));
}
cout<<endl<<a;
Xr[i]=xr[a];
Xi[i]=xi[a];
}
cout<<"\\n \\n array after swapping:";
for(i=0;i<n;i++)
cout<<endl<<Xr[i]<<"+("<<Xi[i]<<")j";
//Calculation of no of stages
for(i=1;n!=pow(2,i);i++);
stages=i;
cout<<"\\n\\n NO OF STAGES:"<<stages<<endl;
//Stage calculation
for(k=1;k<=stages;k++) //loop for stages
for(l=0;l<n;l=l+pow(2,k)) //loop for butterfly
{
b=0;
for(i=l;i<(l+pow(2,k-1));i=i+1) //loop for each pt in butterfly
{
j=i+pow(2,k-1);
// calculating twiddle factor
Wr=cos(2*M_PI*b/n);
Wi=-sin(2*M_PI*b/n);
b++;
if(k==2 && stages>2)
b++;
//multiplying with twiddle factor
temp1=(Xr[j]*Wr)-(Xi[j]*Wi);
temp2=(Xr[j]*Wi)+(Xi[j]*Wr);
//calculating first element
xr[i]=Xr[i]+temp1;
xi[i]=Xi[i]+temp2;
//calculating second element
xr[j]=Xr[i]-temp1;
xi[j]=Xi[i]-temp2;
Xr[i]=xr[i];
Xi[i]=xi[i];
Xr[j]=xr[j];
Xi[j]=xi[j];
}
}
cout<<"\\N DFT OF GIVEN SEQUENCE IS:\\n";
for(i=0;i<n;i++)
cout<<endl<<Xr[i]<<"+("<<Xi[i]<<")j";
getch();
}