Geology Reference
In-Depth Information
In its most elementary form, the fast Fourier transform (FFT) algorithm takes the
data length to be an integral power of two, so that
N
2
m
, where
m
is an integer.
=
The DFT (2.167) may be expressed as
N
−
1
x
j
W
kj
G
=
,
(2.169)
k
j
=
0
with
W
=
e
−
i
2
N
. The sequence
x
j
is then divided into two new sequences
y
=
x
2
and
z
=
x
2
+
1
, with
=
0,1,...,
N
/2
−
1. Each of the new sequences,
y
=
(
x
1
,
x
3
,...,
x
N
−
1
), is half as long and may be regarded
as having double the sample interval of the original sequence, with DFTs
(
x
0
,
x
2
,...,
x
N
−
2
)and
z
=
N
/2
−
1
N
/2
−
1
0
y
W
2
k
and
C
k
z
W
2
k
,
k
B
k
=
=
=
0,1,...,
N
/2
−
1. (2.170)
=
=
0
Expression (2.169) may then be rewritten as
N
/2
−
1
y
W
2
k
z
W
k
(2
+
1)
G
=
+
(2.171)
k
=
0
or
W
k
C
k
,
k
G
k
=
B
k
+
=
0,1,...,
N
/2
−
1.
(2.172)
This provides the first half of the desired DFT. To obtain the second half, we sub-
stitute
k
+
N
/2for
k
in (2.170) to get
=
0
y
W
2(
k
+
N
/2)
=
0
y
W
2
k
N
/2
−
1
N
/2
−
1
B
k
+
N
/2
=
=
=
B
k
,
(2.173)
N
/2
−
1
N
/2
−
1
z
W
2(
k
+
N
/2)
z
W
2
k
C
k
+
N
/2
=
=
=
C
k
.
(2.174)
=
0
=
0
Thus, again substituting
k
+
N
/2for
k
in (2.172), we find that
W
k
+
N
/2
C
k
+
N
/2
W
k
C
k
,
k
G
k
+
N
/2
=
B
k
+
N
/2
+
=
B
k
−
=
0,1,...,
N
/2
−
1, (2.175)
giving the second half of the DFT.
The DFT of the full sequence
x
j
is then found from the DFTs of the two half-
length sequences
x
j
andy
j
. The decimation to half-length sequences can be contin-
ued until we have only two-length sequences to transform. For
N
2
m
,
m
=
=
log
2
N
,
m
successive DFTs are required, each involving 2
m
2log
2
N
complex multiplic-
ations for each frequency index of which there are
N
, for a total of 2
N
log
2
N
.
Direct calculation takes
N
2
complex multiplications for a relative speed ratio of
N
/2
m
. Even for moderately long sequences with
N
=
=
1024, direct calculation is
1024/20
=
51.2 times slower.
Search WWH ::
Custom Search