Information Technology Reference
In-Depth Information
6.7.3 Fast Fourier Transform
The
fast Fourier transform algorithm
is a consequence of the following observation: when
n
is even, the polynomial
p
(
x
)
in equation (
6.21
) can be decomposed as
p
(
x
)=
a
0
+
a
1
x
+
a
2
x
2
+
+
a
n−
1
x
n−
1
···
=(
a
0
+
a
2
x
2
+
+
a
n−
2
x
n−
2
)
+
x
(
a
1
+
a
3
x
2
+
···
+
a
n−
1
x
n−
2
)
···
=
p
e
(
x
2
)+
xp
o
(
x
2
)
(6.26)
Here
p
e
(
y
)
and
p
o
(
y
)
are polynomials of degree
(
n/
2
)
−
1.
Let
n
be a power of 2, that is,
n
=
2
d
. As stated above, the
n
-point DFT of
a
is
obtained by evaluating
p
(
x
)
at the
n
th roots of unity. Because of the decomposition of
p
(
x
)
, it suffices to evaluate
p
e
(
y
)
and
p
o
(
y
)
at
y
=(
ω
0
)
2
,
(
ω
1
)
2
,
(
ω
2
)
2
,
...
,
(
ω
n−
1
)
2
=
(
ω
2
)
0
,
(
ω
2
)
1
,
(
ω
2
)
2
,
...
,
(
ω
2
)
n−
1
and combine their values with one multiplication and one
addition for each of the
n
roots of unity. However, because
ω
2
is a
(
n/
2
)
th principal root
of unity (see Problem
6.25
),
(
ω
2
)
(
n/
2
)+
r
=(
ω
2
)
r
and the
n
powers of
ω
2
collapse to
n/
2
distinct powers of
ω
2
,namely,the
(
n/
2
)
th roots of unity. Thus,
p
(
x
)
at the
n
th roots of unity
can be evaluated by evaluating
p
e
(
y
)
and
p
o
(
y
)
at the
(
n/
2
)
th roots of unity and combining
their values with one addition and multiplication for each of the
n
th roots of unity. In other
words, the
n
-point DFT of
a
canbedonebyperformingthe
(
n/
2
)
-point DFT of its even
and odd subsequences and combining the results with
O
(
n
)
additional steps. This is the fast
Fourier transform (FFT) algorithm.
We denot e by
F
(
d
)
the directed acyclic graph associated with the straight-line program
resulting from this realization of the FFT on
n
=
2
d
inputs. A circuit for the 16-point FFT
algorithm inputs,
F
(
4
)
,isshowninFig.
6.7
. It is computed from the eight-point FFT on
the even and odd components of
a
, as shown in the boxed regions. These components are
permuted because each of these smaller FFTs is computed recursively in turn. (The index of
f
0
f
1
f
2
f
3
f
4
f
5
f
6
f
7
f
8
f
9
f
10
f
11
f
12
f
13
f
14
f
15
p
e
(
x
)
p
o
(
x
)
a
0
a
8
a
4
a
12
a
2
a
10
a
6
a
14
a
1
a
9
a
5
a
13
a
3
a
11
a
7
a
15
Figure 6.7
A circuit
F
(
4
)
for the FFT algorithm on 16 inputs.
Search WWH ::
Custom Search