Discrete Fourier Transform or DFT is a mathematical operation that transforms a time domain signal to frequency domain. It is usually implemented using the Fast Fourier Transform (FFT). The computational complexity of the DFT is N² whereas its (N)log₂N for the FFT, where N is the number of samples of the the time domain signal. Mathematically, the DFT is written as

and this operation can be easily implemented in MATLAB as shown below.

clear all
close all

fm=100;
fs=1000;
Ts=1/fs;
N=1024;
t=0:Ts:(N-1)*Ts;

x=cos(2*pi*fm*t);
W=exp(-j*2*pi/N);

n=0:N-1;
for k=0:N-1
        X(k+1)=sum(x.*(W.^(k*n)));
end

plot((0:k)/N,abs(X))
xlabel ('Normalized Frequency')
ylabel ('X')

The DFT of the cosine function with frequency of 100Hz is shown below. It must be noted that the frequency in the figure below is normalized by the sampling frequency. So the peaks in the graph occur at 0.1*1000=100Hz and 0.9*1000=900Hz (image frequency). Actually if you zoom in you will see that the peaks are not exactly at 0.1 and 0.9 but  are slightly offset as the frequency bins are not located at exactly those frequencies.

In case of multiple sinusoids the resolution of the DFT becomes important. Higher the sample size (duration of the time domain signal) higher is the resolution of the DFT. As stated earlier the DFT is a computationally complex operation and usually the Fast Fourier Transform (FFT) is used to compute the frequency domain behavior. We will discuss this in the following posts.

A simple way to expedite the process of DFT calculation is to use matrix manipulation instead of a “for loop”.This is shown below.

clear all
close all

fm=100;
fs=1000;
Ts=1/fs;
N=128;
t=0:Ts:(N-1)*Ts;

x=cos(2*pi*fm*t);
W=exp(-j*2*pi/N);

n=0:N-1;
k=0:N-1;

X=x*(W.^(n'*k));

plot(k/N,abs(X))
xlabel ('Normalized Frequency')
ylabel ('X')

Although matrix manipulation makes for a nice and clean code, it was found that there was no improvement in the computation time. Both the “for loop” code and the “matrix multiplication” code took about 0.35 seconds to execute. However, increasing the sample size from 128 to 1024 results in significant better computation time for the latter scheme.

Author: Yasir Ahmed (aka John)

More than 20 years of experience in various organizations in Pakistan, the USA, and Europe. Worked as a Research Assistant within the Mobile and Portable Radio Group (MPRG) of Virginia Tech and was one of the first researchers to propose Space Time Block Codes for eight transmit antennas. The collaboration with MPRG continued even after graduating with an MSEE degree and has resulted in 12 research publications and a book on Wireless Communications. Worked for Qualcomm USA as an Engineer with the key role of performance and conformance testing of UMTS modems. Qualcomm is the inventor of CDMA technology and owns patents critical to the 4G and 5G standards.

Twitter Facebook Linkedin