Geology Reference
In-Depth Information
a sequence of length
L
1. Since the z-transform of the convolution of two
sequences is the product of their z-transforms (see equation (2.14)), the z-transform
of the sequence
e
j
is
=
M
+
N
−
M
+
N
−
2
e
j
z
j
E
(
z
)
=G
(
z
)
·H
(
z
)
=
.
(2.164)
j
=
0
The DFT of the sequence
e
j
is then
1
Δ
E
=Δ
t
E
(
z
)
=Δ
t
G
(
z
)
·H
(
z
)
=
t
G
·H
k
,
(2.165)
k
k
e
−
i
2
L
k
. The sequence
with
z
=
Δ
t
·
e
j
can then be recovered from the inverse DFT,
M
+
N
−
k
=
0
G
2
k
e
i
2
L
kj
Δ
t
·
=Δ
f
·H
.
(2.166)
e
j
k
Thus, convolution can be accomplished by taking the inverse of the product of
the two DFTs.
2.3.3 The fast Fourier transform
Direct calculation of the DFT (2.150) and its inverse (2.149) requires
N
2
complex
multiplications in each case. A much faster method of doing these calculations
was originally described by Gauss as far back as 1805 (Heideman
et al.
, 1995),
although the algorithm remained relatively unknown. Claerbout (1985, p. 12) cites
the first machine computation he knows of as being due to Vern Herbert in 1962
at Chevron Standard in Calgary, Canada. It was rediscovered in 1965 and widely
publicized by Cooley and Tukey (1965) and has become known as the Cooley-
Tukey algorithm. The explosive growth of fast methods of computing DFTs since
1965 is indicated by the 3400 entries in a recent bibliography of e
cient algorithms
(Sorenson
et al.
, 1995).
The form (2.166) suggests that we absorb
Δ
t
into the time sequence, transform-
ing the DFT (2.150) to the sum
N
−
1
x
j
e
−
i
2
N
kj
G
k
=
.
(2.167)
j
=
0
The inverse transform (2.149) then becomes
k
=
0
G
N
−
1
1
N
k
e
i
2
N
kj
Δ
t
·
g
j
=
x
j
=
.
(2.168)
Search WWH ::
Custom Search