Digital Signal Processing Reference
In-Depth Information
10000
9000
8000
7000
6000
5000
4000
3000
2000
1000
0
0
10
20
30
40
50
60
70
80
90
100
parameter size (n)
Figure 6.4: Comparing Nlog
2
(N) (line) versus N
2
(asterisks).
analysis frequencies used by the FFT/DFT. This technique is called zero-padding.
We saw in Chapter 3, \Filters," that lters perform convolution. One can use
the FFT to compute convolution eciently. Other uses include analyzing the eect
that a lter has on a signal, and designing FIR lters (with the Inverse FFT). Any
time that a problem requires the DFT, the FFT can be used instead.
6.2
The Discrete Fourier Transform
This is the Discrete Fourier Transform (DFT)
N1
X
X[m] =
x[n](cos(2nm=N)j sin(2nm=N))
n=0
where m = 0::N1. We call this the \rectangular form" of the DFT, and there are
many variations of this transform. For example, one common way to express it uses
the e
j2nm=N
term instead of the sinusoids, which can make analysis by a human
easier.
N1
X
j2nm=N
X[m] =
x[n]e
n=0
