K. J.
Somaiya College of Engineering, Mumbai-77
(Autonomous College Affiliated to University of Mumbai )
Batch: A3 Roll No.: 1811041
Experiment No. 4
Grade: AA / AB / BB / BC / CC / CD /DD
Signature of the Staff In-charge with date
Title: Compute DFT & IDFT of discrete time signals using Matlab.
Objective: To learn & understand the Fourier transform operations on discrete time
signals.
Expected Outcome of Experiment:
CO Outcome
CO3 Analyze signals in frequency domain through various image transforms
Books/ Journals/ Websites referred:
1. http://www.mathworks.com/support/
2. www.math.mtu.edu/~msgocken/intro/intro.html
3. www.mccormick.northwestern.edu/docs/efirst/matlab.pdf
4. A.Nagoor Kani “Digital Signal Processing”, 2nd Edition, TMH Education.
Pre Lab/ Prior Concepts:
Dept. of Computer Engg. DSIP Lab Sem VI Jan-Apr 2020 Page 1
K. J. Somaiya College of Engineering, Mumbai-77
(Autonomous College Affiliated to University of Mumbai )
Implementation details along with screenshots:
Given a sequence of N samples f(n), indexed by n = 0..N-1, the Discrete Fourier
Transform (DFT) is defined as F(k), where k=0..N-1:
F(k) are often called the 'Fourier Coefficients' or 'Harmonics'.
The sequence f(n) can be calculated from F(k) using the Inverse Discrete Fourier
Transform (IDFT):
In general, both f(n) and F(k) are complex.
Annex A shows that the IDFT defined above really is an inverse DFT.
Conventionally, the sequences f(n) and F(k) is referred to as 'time domain' data and
'frequency domain' data respectively. Of course there is no reason why the samples in
f(n) need be samples of a time dependent signal. For example, they could be spatial
image samples (though in such cases a 2 dimensional set would be more common).
Although we have stated that both n and k range over 0..N-1, the definitions above have
a periodicity of N:
So both f(n) and F(k) are defined for all (integral) n and k respectively, but we only need
to calculate values in the range 0..N-1. Any other points can be obtained using the above
periodicity property.
Dept. of Computer Engg. DSIP Lab Sem VI Jan-Apr 2020 Page 2
K. J. Somaiya College of Engineering, Mumbai-77
(Autonomous College Affiliated to University of Mumbai )
For the sake of simplicity, when considering various Fast Fourier Transform (FFT)
algorithms, we shall ignore the scaling factors and simply define the FFT and Inverse
FFT (IFFT) like this:
In fact, we shall only consider the FFT algorithms in detail. The inverse FFT (IFFT) is
easily obtained from the FFT.
Here are some simple DFT's expressed as matrix multiplications.
1 point DFT:
2 point DFT:
4 point DFT:
3 point DFT:
Dept. of Computer Engg. DSIP Lab Sem VI Jan-Apr 2020 Page 3
K. J. Somaiya College of Engineering, Mumbai-77
(Autonomous College Affiliated to University of Mumbai )
Note that each of the matrix multipliers can be inverted by conjugating the elements.
This what we would expect, given that the only difference between the DFT and IDFT
is the sign of the complex exponential argument.
Here's another couple of useful transforms:
If..
This is the 'Delta Function'. The usual implied periodicity has been made explicit by
using MOD N. The DFT is therefore:
This gives us the DFT of a unit impulse at n=n0. Less obvious is this DFT:
If..
Dept. of Computer Engg. DSIP Lab Sem VI Jan-Apr 2020 Page 4
K. J. Somaiya College of Engineering, Mumbai-77
(Autonomous College Affiliated to University of Mumbai )
Implementation steps with screenshots for DFT:
Code:
%DFT
y = input("Enter Sequence :");
N = length(y);
res = [];
for x=0:N-1
sum=0;
for a=1:N
sum=sum+y(a)*exp(-1j*2*pi*(a-1)*x/N);
end
res = [res, sum];
end
disp("DFT");
disp(res);
t=0:ln-1;
subplot(221);
stem(t,y);
title('Given Sequence');
ylabel ('Amplitude');
xlabel ('Time Index');
magnitude=abs(res);
disp("DFT Magnitude");
disp(magnitude);
t=0:ln-1;
subplot(222);
stem(t,magnitude);
title('Plotting magnitude response using DFT');
ylabel ('Amplitude');
Dept. of Computer Engg. DSIP Lab Sem VI Jan-Apr 2020 Page 5
K. J. Somaiya College of Engineering, Mumbai-77
(Autonomous College Affiliated to University of Mumbai )
xlabel ('X');
phase=angle(res);
disp("DFT Phase");
disp(phase);
t=0:ln-1;
subplot(223);
stem(t,phase);
title('Plotting magnitude sequence');
ylabel ('Phase');
xlabel ('X');
%IDFT
res1 =[];
for x=0:N-1
sum=0;
for a=1:N
sum=sum+res(a)*exp(1j*2*pi*(a-1)*x/N);
end
sum=sum/N;
res1 = [res1 sum];
end
disp("IDFT");
disp(res1);
t=0:ln-1;
subplot(224);
stem(t,res1);
title('IDFT Response');
ylabel ('Amplitude');
xlabel ('Time Index');
output :
Dept. of Computer Engg. DSIP Lab Sem VI Jan-Apr 2020 Page 6
K. J. Somaiya College of Engineering, Mumbai-77
(Autonomous College Affiliated to University of Mumbai )
Dept. of Computer Engg. DSIP Lab Sem VI Jan-Apr 2020 Page 7
K. J. Somaiya College of Engineering, Mumbai-77
(Autonomous College Affiliated to University of Mumbai )
Conclusion:- Hence we implemented DFT and IDFT for a given sequence.
Date: Signature of faculty in-charge
Post Lab Descriptive Questions
1. Compare and discuss the computational efficiency of DFT and
FFT
Ans. Discrete Fourier Transform (DFT) is the discrete version of the Fourier
Transform (FT) that transforms a signal (or discrete sequence) from the time
domain representation to its representation in the frequency domain. Whereas,
Fast Fourier Transform (FFT) is any efficient algorithm for calculating the DFT.
Computing a DFT of n points by using only its definition takes Θ(n^2) time,
whereas an FFT can compute the same result in only theta(nlogn)Θ(nlog n)
steps.
For large sequences, this constitutes quite a substantial gain.
2. Give the properties of DFT and IDFT.
Ans.
a. Periodicity
X (k + N) = X (k)
Circular b. shift
x ((n − m) modN ) ⇔ X (k) e−(i 2πkm )
b. Time reversal
x ((−n) modN ) = x ((N − n) modN ) ⇔ X ((N − k) modN ) = X ((−k) modN )
Dept. of Computer Engg. DSIP Lab Sem VI Jan-Apr 2020 Page 8
K. J. Somaiya College of Engineering, Mumbai-77
(Autonomous College Affiliated to University of Mumbai )
c. Complex conjugate
x’(n) ⇔ X’((−k)
modN)
d. Circular Convolution
Property x (n) ∗ h (n) ⇔ X
(k) H (k)
e. Multiplication property
x(n)h(n)⇔ (1/N)X(k)∗H(k)
f. Parseval’s Theorem
Symmetry
x (n) real ⇔ X (k) = X ‘((N − k) modN )
3. Discuss the impact on computation time & efficiency when the
number of samples N increases.
Ans.
Since, the complexity for computing dft of sample is Θ(n^2) is dependant on ‘n’
samples. Therefore, the computational time required increases exponentially
with sample size and efficiency decreases exponentially.
4. How to compute the maximum length N for a circular
convolution using DFT and IDFT?
Ans.
Let us take two finite duration sequences x1(n) and x2(n), having integer length
as N.
Their DFTs are X1(K) and X2(K) respectively, which is shown below −
X1(K)=∑n=0N−1x1(n)ej2ΠknN k=0,1,2...N−1X1(K)=∑n=0N−1
Dept. of Computer Engg. DSIP Lab Sem VI Jan-Apr 2020 Page 9
K. J. Somaiya College of Engineering, Mumbai-77
(Autonomous College Affiliated to University of Mumbai )
x1(n)ej2ΠknNk=0,1,2...N−1
X2(K)=∑n=0N−1x2(n)ej2ΠknNk=0,1,2...N−1
X2(K)=∑n=0N−1x2(n)ej2ΠknNk=0,1,2...N−1
Now, we will try to find the DFT of another sequence x3(n), which is given as
X3(K)
X3(K)=X1(K)×X2(K)X3(K)=X1(K)×X2(K)
By taking the IDFT of the above we get
x3(n)=1N∑n=0N−1X3(K)ej2ΠknNx3(n)=1N∑n=0N−1X3(K)ej2Πk
nN
After solving the above equation, finally, we get
x3(n)=∑m=0N−1x1(m)x2[((n−m))N] m=0,1,2...N−1
Dept. of Computer Engg. DSIP Lab Sem VI Jan-Apr 2020 Page 10
K. J. Somaiya College of Engineering, Mumbai-77
(Autonomous College Affiliated to University of Mumbai )
Dept. of Computer Engg. DSIP Lab Sem VI Jan-Apr 2020 Page 11
K. J. Somaiya College of Engineering, Mumbai-77
(Autonomous College Affiliated to University of Mumbai )
Page
Dept. of Computer Engg. DSIP Lab Sem VI Jan-Apr 2020 12
