This module describes FFT, convolution, filtering, LTI systems,
digital filters and circular convolution.
Important application of the fft
How many complex multiplies and adds are required to
convolve two
N -pt
sequences?
y
n
m
0
N
1
x
m
h
n
m
There are
2
N
1 non-zero output points and each will be computed
using
N complex mults and
N
1 complex adds. Therefore,
Total Cost
2
N
1
N
N
1
O
N
2
Got questions? Get instant answers now!
Zero-pad these two sequences to length
2
N
1 , take DFTs using the FFT algorithm
x
n
X
k
h
n
H
k The cost is
O
2
N
1
2
N
1
O
N
N
Multiply DFTs
X
k
H
k The cost is
O
2
N
1
O
N
Inverse DFT using FFT
X
k
H
k
y
n The cost is
O
2
N
1
2
N
1
O
N
N
So the total cost for direct convolution of two
N -point sequences is
O
N
2 . Total cost for convolution using FFT algorithm is
O
N
N . That is a
huge savings (
).
Summary of dft
x
n is an
N -point signal
(
).
X
k
n
0
N
1
x
n
2
N
k
n
n
0
N
1
x
n
W
N
k
n where
W
N
2
N is a "twiddle factor" and the first part is the basic DFT.
What is the dft
X
k
X
F
k
N
n
0
N
1
x
n
2
F
n where
X
F
k
N is the DTFT of
x
n and
n
0
N
1
x
n
2
F
n is the DTFT of
x
n at digital frequency
F . This is a sample of the
DTFT. We can do frequency domain analysis on a computer!
Inverse dft (idft)
x
n
1
N
n
0
N
1
X
k
2
N
k
n
Build
x
n using
Simple complex
sinusoidal
building block signals
Amplitude of each complex sinusoidal building block in
x
n is
1
N
X
k
Circular convolution
Regular convolution from circular convolution
Zero pad
x
n and
h
n to
length
length
x
length
h
1
Zero padding increases frequency resolution in DFT
domain (
)
8-pt DFT of 8-pt signal
16-pt DFT of same signal padded with 8 additional zeros
Efficient computational algorithm for calculating the
DFT
"Divide and conquer"
Break signal into even and odd samples keep taking
shorter and shorter DFTs, then build
N -pt DFT by cleverly
combining shorter DFTs
N -pt DFT:
O
N
2
O
N
2 logbase -->
N
Fast convolution
Use FFT's to compute circular convolution of zero-padded
signals
Much faster than regular convolution if signal lengths
are long
O
N
2
O
N
2 logbase -->
N
See
.