Discrete Fourier Transform

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 N2 whereas its (N)log2N 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.

DFT of a cosine wave
DFT of a cosine wave

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: John (YA)

John has over 15 years of Research and Development experience in the field of Wireless Communications. He has worked for a number of companies around the world including Qualcomm Inc. USA. He has an MS in Electrical Engineering from Virginia Tech USA and has published his work in international journals and conferences.

0.00 avg. rating (0% score) - 0 votes

Leave a Reply

Your email address will not be published. Required fields are marked *