Circular Convolution of two sequences using DFT and IDFT

Circular Convolution of  two sequences using DFT and IDFT

Compute the circular convolution of given two sequences using DFT and IDFT.

1:  #include<graphics.h>  
2:  #include<iostream.h>  
3:  #include<conio.h>  
4:  #include<stdlib.h>  
5:  void main(void)  
6:  {  
7:   int sample,impulse,sam[10],imp[10],out[10][10],outp[10]={0},i;  
8:   int gd=DETECT,gm,maxx,maxy,j,k;  
9:   char str[5];  
10:   initgraph(&gd,&gm,"c:\\tc\\bgi");  
11:   maxx=getmaxx();   // Returns maximum x or y screen coordinate  
12:   maxy=getmaxy();  
13:   cout<<"\n\tEnter the number of element in sample sequence::";  
14:   cin>>sample;  
15:   cout<<"\n\tEnter the number of element in impulse sequence::";  
16:   cin>>impulse;           //input impulse & sample sequence  
17:   cout<<"\n\tEnter the sample sequence";  
18:   for(i=0;i<sample;i++)  
19:   cin>>sam[i];  
20:   cout<<"\n\tEnter the impusle sequence";  
21:   for(i=0;i<impulse;i++)  
22:   cin>>imp[i];  
23:   if(sample<impulse)  
24:   for(i=sample;i<impulse;i++)  
25:    sam[i]=0;  
26:   else  
27:   for(i=impulse;i<sample;i++)  
28:    imp[i]=0;  
29:   if(sample<impulse)  
30:        sample=impulse;  
31:   int temp;  
32:   for(i=0;i<sample;i++)  
33:       for(j=0;j<sample;j++)  
34:       {  
35:            out[(j+i)%sample][i]=sam[j];  
36:       }  
37:   for(j=0;j<sample;j++)  
38:    for(k=0;k<sample;k++)  
39:     outp[j]=outp[j]+out[j][k]*imp[k];  
40:   int samp=sample;  
41:   setcolor(RED);  
42:   line(0,maxy/2,maxx,maxy/2);  
43:   line(maxx/2,0,maxx/2,maxy);  
44:   setcolor(GREEN);  
45:   for(i=0;i<samp;i++)  
46:   {  
47:    line(maxx/2+i*30,maxy/2,maxx/2+i*30,maxy/2-outp[i]*5);  
48:    moveto(maxx/2+i*30,maxy/2-outp[i]*5-10);  
49:    itoa(outp[i],str,10);        //converts integer to string  
50:    outtext(str);  
51:   }  
52:   getch();  
53:  }  

More about → Circular Convolution of two sequences using DFT and IDFT

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:  }  

More about → N-Point FFT Algorithm to find DFT or IDFT