the transform of αa(n) + βb(n). Thus we can use the discrete
transforms to model linear systems.
(2) The DFT of a real time series (i.e., one for which f(n) =
f * (n)) has the symmetry
F(−k) = F(N − k) = F * (k).
(30)
Thus, as with the continuous transform, the values for the
negative frequencies are the conjugates of those for the positive
frequencies.
(3) Shifting a time series in time simply changes the phase of
the DFT: if the transform of f(n) is F(k), the DFT of f(n − j) is
W kj F(k). Similarly, shifting a Fourier transform in frequency
changes the phase of the IDFT: the inverse transform of
F(k − m) is W −mn f(n).
6.4.4 The fast Fourier transform (FFT)
For these concepts to be useful, the transforms and inverse
transforms must be evaluated on a computer. Moreover, it only
makes sense to carry out filtering using Fourier transforms if
the transform and inverse transform operations are relatively
quick. It turns out that an elegant algorithm known as the Fast
Fourier Transform (FFT) provides a fast way of carrying out
the DFT and IDFT.
The time a computer needs to carry out an algorithm
depends on how many arithmetic operations are needed. We
would expect that evaluating all N points in the DFT, each
of which is the sum of the N terms in the series, would require
approximately N 2 operations. The FFT algorithm, however,
requires a much smaller number of operations, approximately N log 2 N. The difference is substantial; for N = 4096,
N
2
= 16,777,216, but N log 2 N = 49,152 a about 340 times
fewer! As a consequence, the introduction of the FFT made
digital signal processing common in seismology and many
other disciplines.
Entire books have been written about the FFT, so we only
briefly sketch the approach here. The underlying idea is that a
simple method can be used to compute the transform of a series
of points by splitting it in half. We take a series with N points,
f(n) for n = 0, 1, . . . , N − 1
(31)
and form two subseries, one with the odd-numbered points and
one with the even-numbered points:
a(n) = (f(0), f (2), f (4), . . . ) = f (2n)
for n = 0, 1, . . . , N/2 − 1,
b(n) = ( f (1), f(3), f (5), . . . ) = f(2n +1).
(32)
The DFTs of the two subseries are
A(k) =
n
N
=
−
∑
0
2 1
/
a(n)e − 4πikn/N and
2
2
2
π
ω
π
π
∆
∆
/(
)
=
N t
= (N∆t) = T,
(23)
which is equal to the original record length. 2 This wraparound
phenomenon can be important, as we shall see when discussing
the use of DFTs to carry out convolutions.
6.4.3 Properties of DFTs
For simplicity, we write the DFT and the inverse DFT implicitly
assuming a unit sampling interval, ∆t = 1, and define
F(k) ≡ F(k∆ω) =
n
N
=
−
∑
0
1
f (n)e −2πikn/N
for k and n = 0, 1, . . . , N − 1
(24)
f(n) ≡ f(n∆t) =
1
0
1
N k
N
=
−
∑ F(k)e
2πikn/N
for k and n = 0, 1, . . . , N − 1.
(25)
The two equations are very similar in form and are easy to
evaluate a the forward and inverse transforms differ only
in the sign of the exponential and the 1/N normalization.
This is especially clear if we define the complex exponential as
W = e −2π i/N , so the definitions of the DFT and IDFT become
F(k) =
n
N
=
−
∑
0
1
f(n)W kn and f(n) =
1
0
1
N k
N
=
−
∑ F(k)W −kn .
(26)
The terms with the complex exponential are periodic in N,
W kn = W (N+k)n = W k(N+n) ,
(27)
so the DFT and IDFT can be defined for all integers k, n, j as
f(n) = f(jN + n), F(k) = F(jN + k).
(28)
A formal statement of the relation between the negative and
positive frequencies can also be given as
f(−n) = f(N − n), F(−k) = F(N − k).
(29)
We used this relation when we explained how the second half
of the DFT corresponds to negative frequencies (Fig. 6.4-4).
Using these definitions, we can show that the discrete transforms have properties that we discussed for the continuous
transforms in Section 6.2.4: 3
(1) The DFT and IDFT are linear: if A(k) and B(k) are the
transforms of time series a(n) and b(n), then αA(k) + βB(k) is
6.4 Discrete time series and transforms 389
2 Because of this periodicity, the record length is considered to be N∆t rather than
(N − 1) ∆t.
3 As for the continuous transforms, the proofs are left for the problems.
transforms to model linear systems.
(2) The DFT of a real time series (i.e., one for which f(n) =
f * (n)) has the symmetry
F(−k) = F(N − k) = F * (k).
(30)
Thus, as with the continuous transform, the values for the
negative frequencies are the conjugates of those for the positive
frequencies.
(3) Shifting a time series in time simply changes the phase of
the DFT: if the transform of f(n) is F(k), the DFT of f(n − j) is
W kj F(k). Similarly, shifting a Fourier transform in frequency
changes the phase of the IDFT: the inverse transform of
F(k − m) is W −mn f(n).
6.4.4 The fast Fourier transform (FFT)
For these concepts to be useful, the transforms and inverse
transforms must be evaluated on a computer. Moreover, it only
makes sense to carry out filtering using Fourier transforms if
the transform and inverse transform operations are relatively
quick. It turns out that an elegant algorithm known as the Fast
Fourier Transform (FFT) provides a fast way of carrying out
the DFT and IDFT.
The time a computer needs to carry out an algorithm
depends on how many arithmetic operations are needed. We
would expect that evaluating all N points in the DFT, each
of which is the sum of the N terms in the series, would require
approximately N 2 operations. The FFT algorithm, however,
requires a much smaller number of operations, approximately N log 2 N. The difference is substantial; for N = 4096,
N
2
= 16,777,216, but N log 2 N = 49,152 a about 340 times
fewer! As a consequence, the introduction of the FFT made
digital signal processing common in seismology and many
other disciplines.
Entire books have been written about the FFT, so we only
briefly sketch the approach here. The underlying idea is that a
simple method can be used to compute the transform of a series
of points by splitting it in half. We take a series with N points,
f(n) for n = 0, 1, . . . , N − 1
(31)
and form two subseries, one with the odd-numbered points and
one with the even-numbered points:
a(n) = (f(0), f (2), f (4), . . . ) = f (2n)
for n = 0, 1, . . . , N/2 − 1,
b(n) = ( f (1), f(3), f (5), . . . ) = f(2n +1).
(32)
The DFTs of the two subseries are
A(k) =
n
N
=
−
∑
0
2 1
/
a(n)e − 4πikn/N and
2
2
2
π
ω
π
π
∆
∆
/(
)
=
N t
= (N∆t) = T,
(23)
which is equal to the original record length. 2 This wraparound
phenomenon can be important, as we shall see when discussing
the use of DFTs to carry out convolutions.
6.4.3 Properties of DFTs
For simplicity, we write the DFT and the inverse DFT implicitly
assuming a unit sampling interval, ∆t = 1, and define
F(k) ≡ F(k∆ω) =
n
N
=
−
∑
0
1
f (n)e −2πikn/N
for k and n = 0, 1, . . . , N − 1
(24)
f(n) ≡ f(n∆t) =
1
0
1
N k
N
=
−
∑ F(k)e
2πikn/N
for k and n = 0, 1, . . . , N − 1.
(25)
The two equations are very similar in form and are easy to
evaluate a the forward and inverse transforms differ only
in the sign of the exponential and the 1/N normalization.
This is especially clear if we define the complex exponential as
W = e −2π i/N , so the definitions of the DFT and IDFT become
F(k) =
n
N
=
−
∑
0
1
f(n)W kn and f(n) =
1
0
1
N k
N
=
−
∑ F(k)W −kn .
(26)
The terms with the complex exponential are periodic in N,
W kn = W (N+k)n = W k(N+n) ,
(27)
so the DFT and IDFT can be defined for all integers k, n, j as
f(n) = f(jN + n), F(k) = F(jN + k).
(28)
A formal statement of the relation between the negative and
positive frequencies can also be given as
f(−n) = f(N − n), F(−k) = F(N − k).
(29)
We used this relation when we explained how the second half
of the DFT corresponds to negative frequencies (Fig. 6.4-4).
Using these definitions, we can show that the discrete transforms have properties that we discussed for the continuous
transforms in Section 6.2.4: 3
(1) The DFT and IDFT are linear: if A(k) and B(k) are the
transforms of time series a(n) and b(n), then αA(k) + βB(k) is
6.4 Discrete time series and transforms 389
2 Because of this periodicity, the record length is considered to be N∆t rather than
(N − 1) ∆t.
3 As for the continuous transforms, the proofs are left for the problems.