Digital Signal Processing Reference
In-Depth Information
Please note this also requires taking a longer input sample
stream x
i,
equal to N. This, in turn, will require a much greater
number of operations to compute.
12.2 Fast Fourier Transform
At some point, some smart people searched for a way to
compute the DFT in a more efficient way. The result is the FFT, or
Fast Fourier Transform. Rather than requiring N
2
complex
multiplies and additions, the FFT requires N
log
2
N complex
multiplies and additions. This may not sound like a big deal, but
look at the comparison in
Table 12.3
below.
So by using the FFT algorithm on a 1024 point (or sample)
input, we are able to reduce the computational requirements to
less than 1%, or by two orders of magnitude.
The FFT achieves this by reusing previously calculated interim
products. We can see this through a simple example.
Let's start with the calculation of the simplest DFT: N
¼
2 DFT.
Generic DFT equation for N
¼
2
X
k
¼
P
i
¼
0
x
i
e
j2
p
ki
=
2
:
X
0
¼
x
0
e
j2
p
0
=
2
þ
x
1
e
j2
p
0
=
2
X
1
¼
x
0
e
j2
p
0
=
2
þ
x
1
e
j2
p
1
=
2
As e
0
¼
1, we can simplify to find:
X
0
¼
x
0
þ
x
1
X
1
¼
x
0
þ
x
1
e
j
p
¼
x
0
x
1
Next, we will do the four point (N
¼
4) DFT.
Generic DFT equation for N
¼
4
X
k
¼
P
i
¼
0
x
i
e
j2
p
ki
=
4
:
Table 12.3
Fft
Log
2
n
Complex Multiplies &
Additions
L
N
3
N
2
Complex
Multiplies & Additions
Dft
L
Computational Effort
Of Fft Compared To Dft
N
8
64
24
37.50%
32
1024
160
15.62%
256
65,536
2048
3.12%
1024
1,048,576
10,240
0.98%
4096
16,777,216
49,152
0.29%
