KIoT
SECE
Chapter Four
Fast Fourier Transform (FFT)/ DFT
Lecture # 4
Jemal H. ( Msc )
School of Electrical and Computer Engineering
jjemalassen@gmail.com
October, 2023
1
Chapter Contents
Discrete Fourier Transform( DFT)
Fast Fourier Transform ( FFT )
Introduction to Radix 2 FFT ‘s
Decimation in time FFT algorithm
Decimation in frequency FFT algorithm
Computing inverse DFT using FFT
2
Discrete Fourier Transform of Periodic Signal
• The DFT is used to convert finite discrete time sequence x (n) to an N – point
frequency domain sequence denoted by X (K).
• For a discrete time signal x(n) the DFT of the sequence x(n) is expressed by
for
Where = is called the twiddle factor
/
• The inverse discrete Fourier transform is given by
3
Cont….
DFT
Time Domain Frequency Domain
IDFT
If N= 4 we say it is 4-Point DFT. For N=4, the above equation can be written as
0 0 0 0
4 4 4 4
0 1 2 3
4 4 4 4
0 2 4 6
4 4 4 4
0 3 6 9
4 4 4 4 4
Cont….
• For N=4 samples
• For N-point DFT can be expressed in matrix for as
5
DFT Example
Given a sequence for , where
Evaluate its DFT,
6
Properties of Discrete Fourier Transform
• There are a number of important properties of the DFT that are useful in
signal processing applications which includes the following.
Linearity
• If (k) and (k) are the N-point DFTs of (n) and (n) and a, b are an
arbitrary constants either real or complex then
a (n)+b (n) (k)+ (k)
• The Fourier transform of a sum of discrete- time signals is the respective sum of transforms.
Time Reversal
If x(n) x(k) then x((-n))= x(N-n) x((-k))=x(N-k)
Or x(N-n) ) x(N-k)
When N-point sequence is reverse in time it is equivalent to reversing the DFT
values.
7
Properties Cont…
Circular time Shifting of a Sequence
• Let is a periodic sequence which is obtained by extending x(n)
periodically.
x(n) x(k) then x(n-m) x(k)
Periodicity
• If X (k) is N point DFT of a finite duration sequence x (n) then
x ( n + N) = x (n) for all n and X (K+N) = X (k) for all k
Parseval’s Theorem
• For complex valued sequences x(n) and y(n) in general if
x(n) x(k) y(n) y(k) then
∗ ∗
8
Fast Fourier Transform
Direct computation of DFT require large number of computations and
hence processor remain busy.
FFT is a very efficient and quick method and can reduce a very large amount
of computational complexity (multiplications) in DFT .
For a data length of N, the number of complex multiplications for DFT and
FFT, respectively, are determined by
Complex multiplications of DFT ; and------------for DFT
Complex multiplications of FFT= log ……for FFT
Consider a sequence with 1,024 data points;
Applying DFT will require 1,024 x 1,024 = 1, 048, 576 complex
multiplications;
However, applying FFT will require only log
complex multiplications.
9
Introduction to Radix-2 FFT’s
• In an N-point sequence if N is expressed as N= , then the sequence can be
decimated in to r-point sequences.
• The radix-2 FFT algorithms are used for data vectors of lengths N=
• They proceed by dividing the DFT into two DFTs of length N/2 each, and
iterating.
• From the result of 2-point DFTs, the 4-point DFTs can be computed and from
4-point DFTs, 8-point DFTs can be computed until we get N-point DFT.
• The Radix-2 FFT algorithms can be appear and computed in either of
(a) Decimation In Time (DIT), or
(b) Decimation In Frequency (DIF).
z=x+y x
x z=x - y z=wx
x
y w
y -1
Definitions of the graphical operations
10
Decimation in Time ( DIT ) FFT
N point sequence x(n) be splitted into two N/2 point data sequences x1(n)
and x2(n).
x1(n) contains even numbered samples of x(n) and x2(n) contains odd
numbered samples of x(n).
This splitted or decomposition to decimal operation is called decimation.
It is done on time domain sequence it is called ―Decimation in Time.
Basic butterfly flow graph and computation for DIT- FFT algorithm is
depicted below.
DIT-FFT algorithms are based upon decomposition of the input sequence
into smaller sub sequences.
In DIT-FFT input sequence x(n) is considered to be splitted.
11
Cont…
When we perform the DIT of FFF we follow the following basic steps
Step 1: Determine the length of FFT , i.e., N
Step 2 : Calculate twiddle factors
Step 3: Decimate the input sequence ( Bit reversal process)
Step 4: Plotting of flow graph for first stage
Step 5: Calculating first stage outputs
Step 6: Plotting of flow graph for second stage
Step 7: Calculating second stage outputs
Step 8: Summerize all FFTs
• The Bit reversal
process in FFT
looks like the table
here.
12
4- Point DIT FFT
Flow graph of a complete decimation in -frequency decomposition of a 4-point
DFT computation is shown in the figure below.
DIT-FFT algorithm for N=4 flow graph consists of 2 stages.
1st Stage 2nd Stage
13
8 Point DIT-FFT
Flow graph of a complete decimation in -time decomposition of an 8-point DFT
computation is shown in the figure below.
DIT-FFT algorithm for N=8 flow graph consists of 3 stages.
14 1st Stage 2nd Stage 3rd Stage
Decimation in Frequency (DIF) FFT
In Decimation-in-Frequency(DIF) algorithm: The sequence x(n) will be broken
up into two equal halves.
Flow graph of a complete decimation in -frequency decomposition of a 4-point
DFT computation is shown in the figure below.
DIF-FFT algorithm for N=4 flow graph consists of 2 stages as shown below.
1st Stage 2nd Stage
15
8 Point DIF-FFT
• DIF-FFT algorithms are based upon decomposition of the output sequence
into smaller sub sequences.
In DIF-FFT output sequence X(k) is considered to be splitted into even and
odd numbered samples.
Generally the output will now appear in bit reversed order.
16
Example
Given a sequence x(n) for 0 3, where
Evaluate its DFT using the 4 point decimation-in-time FFT method.
Solution
17
Inverse DFT using FFT
• The eight-point IFFT using decimation-in-time has done based on the following methods.
Example
Given the DFT sequence X(k) for 0 3 as of , 10, -2+2j , -2, -2-2j then Evaluate its
inverse DFT x(n) using the decimation-in-time FFT method.
18
End of Slide
19
