EE 321 : Digital Signal Processing

Department of Electronics and Electrical Engineerng

Indian Institute of Technology, Guwahati
Monsoon 2025

Topic 10: FFT

Instruction and notes by : Manish

1 The fast Fourier transform (FFT)

The fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform
(DFT) of a sequence. This is pretty easy to compute with modern computational tools. In
MATLAB, we can simply use the command f f t.
The DFT of a sequence x[n] of length N is defined as:
N −1
2π
X
X[k] = x[n]e−j N kn , k = 0, 1, 2, . . . , N − 1.
n=0

The inverse DFT (IDFT) is given by:

N −1
1 X 2π
x[n] = X[k]ej N kn , n = 0, 1, 2, . . . , N − 1.
N k=0

Direct computation of the DFT requires O(N 2 ) operations. For large N , this becomes com-
putationally expensive. The FFT algorithm reduces the complexity to O(N log N ) operations
by exploiting symmetries in the exponential terms.

Basic Idea of FFT

The FFT is based on a divide-and-conquer approach:
1. Split the sequence x[n] into even and odd indexed elements.

2. Compute two smaller DFTs of size N/2.

3. Combine the results using symmetry properties of complex exponentials (twiddle factors).
This recursive decomposition leads to significant computational savings.

Mathematical Formulation
Let N be even. Then,
N −1
2π
X
X[k] = x[n]e−j N kn
n=0

can be written as
N/2−1 N/2−1
−j 2π 2π
X X
X[k] = x[2n]e N
(2n)k
+ x[2n + 1]e−j N (2n+1)k .
n=0 n=0

1
 This simplifies to
X[k] = E[k] + WNk O[k],
where
N/2−1 N/2−1
2π 2π
−j N/2
x[2n + 1]e−j N/2 kn ,
X kn
X
E[k] = x[2n]e , O[k] =
n=0 n=0

and
2π
WNk = e−j N k
is the twiddle factor.
These are the symmetries in twiddle factor:
k+ N
1. WN 2
= −WNk

2. WNk+N = WNk

3. WNk = WN/k

4. Roots of Unity: The set {WN0 , WN1 , . . . , WNN −1 } are the N -th roots of unity, evenly
spaced points on the unit circle in the complex plane.

Homework: Verify the above symmetries.

1.1 FFT Matlab algorithm

Check the fft MATLAB algorithm and its uses here:
https://in.mathworks.com/help/matlab/ref/fft.html

Y = f f t(X, n) returns the n-point DFT.

• If X is a vector and length(X) < n, then X is padded with trailing zeros.

• If X is a vector and length(X) > n, then X is truncated to length n.

• If X is a matrix, each column is transformed independently.

2
Example: Gaussian Pulse’s FFT
We now illustrate the FFT by converting a Gaussian pulse from the time domain to the
frequency domain.

Define Parameters and Plot in time domain

Fs = 44100; % Sampling frequency
T = 1/Fs; % Sampling period
t = -0.5:T:0.5; % Time vector
L = length(t); % Signal length

X = 1/(0.4*sqrt(2*pi))*(exp(-t.^2/(2*(0.1*1e-3)^2)));

plot(t,X)
title("Gaussian Pulse in Time Domain")
xlabel("Time (t)")
ylabel("X(t)")
axis([-1e-3 1e-3 0 1.1])

Optimize FFT Length

Since the signal length L = 44101 is a large prime number, direct FFT is inefficient. Use the
next power of 2 to improve performance:

n = 2^nextpow2(L); %%%% =2^16=65536;

Convert to Frequency Domain

Y = fft(X,n);

f = Fs*(0:(n/2))/n;
P = abs(Y/sqrt(n)).^2;

3
plot(f,P(1:n/2+1))
title("Gaussian Pulse in Frequency Domain")
xlabel("f (Hz)")
ylabel("|P(f)|")

2 FFT Algorithm setup

Q1: Derive the analytical formulae for 2-points and 4-points DFT.
Solution: For two points DFT: W2 = e−jπ = −1
N
X −1
X̃[k] = x[n]WNkn
n=0
X1
X̃[k] = x[n](−1)kn
n=0

X̃[k] = x[0] + (−1)k x[1]

this leads to
X̃[0] = x[0] + x[1]
X̃[1] = x[0] − x[1]

Similarly, for 4-points DFT: W4 = e−jπ/2 = −j Same analysis as above would lead to

X̃[0] = x[0] + x[1] + x[2] + x[3]

X̃[1] = x[0] − jx[1] − x[2] + jx[3]
X̃[2] = x[0] − x[1] + x[2] − x[3]
X̃[3] = x[0] + jx[1] − x[2] − jx[3]

4
3 Decimation in time and decimation in frequency algo-
rithms
The above algorithm is called decimation in time algorithm. To summarize, its progression
happens as per the below butterfly diagram:

Figure: Decimation in time : signal flow diagram

On the other hand, the decimation in frequency algorithm is very similar except that the
input values are naturally ordered here while output values are ordered in the binary bit-
reversed manner.

5
 Figure: Decimation in frequency : signal flow diagram

To understand the difference between the two algorithms, we can observe the following
figure:

Figure: Decimation in time vs decimation in frequency algorithms

Reference material
1. A. Oppenheim and R. W. Shafer, Discrete-Time Signal Processing, Pearson.

2. Richard G Lyons, Understanding Digital Signal Processing, Prentice Hall.

3. Prof. Stephen Roberts’ course on Signal Processing, University of Oxford.