Discrete Fourier Transform and Fast Fourier Transform | MATLAB Tutorial

Discrete Fourier Transform (DFT)

Fourier transform means a signal sampled in time and space to the same signal sampled with frequency. Discrete Fourier Transform (DFT) is a finite duration discrete frequency sequence which is obtained by sampling one period of Fourier transform. Sampling is done at ‘N’ equally spaces points, over the period extending from ω= 0 to ω= 2π. The DFT of discrete sequence x(n) is denoted by X(k) and is mathematically given by,

Since the summation is taken for ‘N’ points, it is called as N-point DFT. It is necessary to have this N ≥ L, where L: Length of the signal x(n).

Inverse Discrete Fourier Transform (IDFT)

We can obtain discrete sequence x(n) back from its DFT, which is called as inverse discrete fourier transform (IDFT) and is mathematically given by,

This is called ‘N’ Point IDFT.

Example:

• Derive the DFT of the sample data sequence x(n)= {1, 2, 3, 4, 5, 6, 7, 8} and compute the corresponding amplitude and phase spectrum.
Solution :
Given sequence is x(n)= {1, 2, 3, 4, 5, 6, 7, 8} and we know DFT X(k) is given by,

Here, N= 8       N-1= 7 and      k = 0, 1, 2, 3, 4, 5, 6, 7.

Now we compute the value of X(k) in a tabular manner by substituting k = 0, 1, 2, 3, 4, 5, 6, 7 in the above equation.

 k 0 1 2 3 4 5 6 7 X(k) 36 -4+9.66i -4+4i -4+1.66i -4 -4-1.66i -4-4i -4-9.66i X(k) in polar form 36 ∠ 0 10.45 ∠1.96 5.65 ∠2.35 4.32 ∠2.75 4 ∠-3.14 4.32 ∠-2.74 5.65 ∠-2.35 10.45 ∠-1.96

Thus, X(k)= {36, -4+9.66i, -4+4i, -4+1.66i, -4, -4-1.66i, -4-4i, -4-9.66i }

Using the above data of X(k) in polar form we can easily plot magnitude and phase spectrum.

• Now find the sequence x(n) for which IDFT X(k) if given by

X(k)= {36, -4+9.66i, -4+4i, -4+1.66i, -4, -4-1.66i, -4-4i, -4-9.66i }

Solution:

Given DFT is X(k)= {36, -4+9.66i, -4+4i, -4+1.66i, -4, -4-1.66i, -4-4i, -4-9.66i } and we know that sequence x(n) is given by IDFT,

Here, N= 8       N-1=7  and      n = 0, 1, 2, 3, 4, 5, 6, 7.

 n 0 1 2 3 4 5 6 7 x(n) 0 1 2 3 4 5 6 7

Hence the result, x(n)= {0, 1, 2, 3, 4, 5, 6, 7} which is our original Sequence.

MATLAB CODE

```clear all
clc
% Number of Samples;N=8 for 8-point DFT
N=8;
%Defining the value of 'j' for imaginary terms
j=sqrt(-1);xn=[1 2 3 4 5 6 7 8];
xk=zeros(1,N);
%Computation of DFT using its definition
for k=0:1:N-1
for n=0:1:N-1
xk(k+1)=xk(k+1)+xn(n+1)*exp(-j*2*pi*n*k/N);
end
end
disp('The DFT Sequence of Magnitude spectrum is')
magxk=abs(xk)
disp('Phase sequence is')
phasxk=angle(xk)
wk=0:1:N-1;
%Magnitude Plot
subplot(2,1,1)
stem(wk,magxk);
title('Magnitude Spectrum')
xlabel('k')
ylabel('magxk')
%Phase Plot
subplot(2,1,2)
stem(wk,phasxk);
title('Phase Spectrum')
xlabel('k')
ylabel('phasxk')
%Computution of IDFT of the calulated DFT in the above code,
%should give the same input sequence.
for n=0:N-1
for k=0:N-1
xn(n+1)=xn(n+1)+(xk(k+1)*exp(j*2*pi*k*n/N));
end
end
%Plot the Sequence
xn=xn./N;
t=0:N-1;
figure;
stem(t,xn);
ylabel ('Amplitude');
xlabel ('Time Index');
```

Figure 1

Figure 2

Fast Fourier Transform (FFT)

While computing N-Point DFT, N2 complex multiplications and N2-N complex additions are required. Thus if N is large then the number of computations goes very high and to avoid this a new algorithm was developed called as Fast Fourier Transform Algorithm (FFT). Radix-2 FFT algorithm is the most important algorithm out of all other FFT algorithms. Based on the division there are two algorithms as follows:

1. Radix-2 Decimation in Time (DIT) algorithm.

Consider an N-point signal x[n] of even length. The derivation of the DIT radix-2 FFT begins by splitting the sum into two parts — one part for the even-indexed values x[2n] and one part for the odd-indexed values x[2n + 1].

Let us consider N = 8, then
X[0] = X0[0] + 1 · X1[0]

X[1] = X0[1] + W8-1 · X1[1]

X[2] = X0[2] + W8-2 · X1 [2]

X[3] = X0[3] + W8-3  · X1 [3]

X[4] = X0[0] + W8-4 · X1 [0]

X[5] = X0[1] + W8-5 · X1 [1]

X[6] = X0[2] + W8-6 · X1 [2]

X[7] = X0[3] + W8-7 · X1 [3]

1. Radix-2 Decimation in Frequency (DIF) algorithm.

Consider an N-point signal x[n] of even length. The derivation of the DIF radix-2 FFT begins by splitting the DFT coefficients X[k] in to even- and odd- indexed values.

The DIT and DIF radix-2 FFT algorithms are very similar.

1. The DIT and DIF radix-2 FFT algorithms have the same complexity.
2. Both can be implemented in-place.
3. For the DIT FFT, x[n] is in bit-reversed order, X[k] is in normal order.

For the DIF FFT, X[k] is in bit-reversed order, x[n] is in normal order. In DIT-FFT algorithm requires a bit-reversal prior to the in-place flow graph, while the DIF FFT algorithm requires a bit-reversal after the in-place flow graph.

Inverse Fast Fourier Transform (IFFT)

Computation of IFFT can be obtained by using the radix-2 DFT FFT algorithm with the definition of IDFT,

Thus IDFT differs from DFT by a Multiplication factor of  and a negative sign of imaginary part of (Wn).

MATLAB CODE

```clear all;
clc;
N=4;
xn=[1 1 2 3];
disp ('DFT of Sequence x[n]');
xk=fft(xn,N)
disp ('The Magnitude response is');
Magxk=abs(xk)
disp ('The phase response is');
phasexk= angle(xk)
disp ('Inverse DFT of Sequence is');
Xn= ifft(xk)
n=0:1:N-1
wk=0:1:N-1
subplot(2,2,1)
stem(n,xn);
title ('Input Sequence');
xlabel('n')
ylabel('x[n]');
subplot(2,2,2)
stem(n,Xn);
title ('Inverse DFT Sequence');
xlabel('n')
ylabel('x[n]');
subplot(2,2,3)
stem(wk,Magxk);
title ('Magnitude Spectrum');
xlabel('k')
ylabel('Magnitude of X(k)');
subplot(2,2,4)
stem(wk,phasexk);
title ('Phase Spectrum');
xlabel('k')
ylabel('Phase of X(k)');
```

Figure 3

Applications of DFT and FFTs:

Some applications of the DFT in statistical signal processing are cross-correlation, matched filtering, system identification, power spectrum estimation and coherence function measurement.

Pursuing Bachelor's Degree in Electronics and Telecommunication Engineering from K. J. Somaiya Institute of Engineering and Information Technology, Mumbai University.

Recommended Posts

Counters using conditionally executed subsystems | Simulink Tutorial

16 Feb 2018 - Simulink, Tutorial