Discrete Fourier Transform

Miguel De Jesus Rosario December 14, 20103 comments Coded in C++

This is an implementation of a Discrete Fourier Transform, also known as DFT.  This code is ideal for DSP beginners and students.  This implementation is based on the assumption that the input signal is a sequence of real numbers.  The result is a sequence of complex numbers containing the DFT frequency samples. 

using namespace std;

#define pi 3.14159265

// class complex
class complex
	//This class member function set the values of the class members real and imag
	void setvals(double r, double i) 

	//This function get the values (by reference) of the class members real and imag
	void getvals(double &r, double &i) 

	/* The class members real and imag represents the real and imaginary parts 
       of a complex number, respectively.*/
	double real;
	double imag;

}; // end of class complex

/* function dft receives two parameters x and N. x is the input sequence containing 
the discrete-time samples and N is the number of DFT points.  The complex type paramater
xk receives a sequence of N-points frequency samples (this is the DFT of the input sequence*/

void dft(double x[], int N, complex xk[])
	double r,i;
	for(int k=0;k<N;k++) //k is the index of the N-point frequency sequence
		xk[k].setvals(0,0); //initialize the values of the counters to zero  
		for(int n=0;n<N;n++) //n is the index of the discrete-time sequence
			xk[k].getvals(r,i); // get the values of real and imag

			/*This is the computation of the real and imaginary parts of the DFT.
			The class member function setvals is used to update the value of the accumulators
			contaning the real and imaginary parts of the DFT samples*/

			xk[k].setvals(r + x[n]*cos(2*pi*k/N*n),i + x[n]*sin(2*pi*k/N*n));	
		} //end inner for-loop

	} //end outer for-loop

}//end dft function

//Declaration of the main() function
int main()
	int size; // The number of DFT samples 
	double r,i; // r = real part of the DFT; i = imaginary part of the DFT 

cout<<"Enter the desired number of DFT samples: ";

double *x = new double[size];  //dynamic array x represent the discrete-time samples
complex *xk = new complex[size]; // dynamic array xk represent the DFT samples

cout<<"\nEnter the sequence x[n]: ";
for(int h=0;h<size;h++)

//Computation of the DFT of x
dft(x, size, xk);

system("CLS"); //clear screen

cout<<"Discrete Fourier Transform: "<<endl<<endl;

for(int h=0;h<size;h++)
	cout.precision(3); // display three (3) decimal places
	xk[h].getvals(r,i); //get the DFT samples values
	cout<<"xk["<<h<<"] = "<<fixed<< r <<" + "<<fixed<< i <<"j"<<endl;  // print the DFT samples


return 0;
}// end main function