Page 455 - Numerical Methods for Chemical Engineering

444 9 Fourier analysis

Let us extract the even and odd f k as
(e) (o)
f f l = 1, 2,..., N/2 (9.57)
l = f k=2l l = f k=2l−1
such that (9.56) becomes
N/2 N/2
(e) (n−1)(2l−1) (o) (n−1)(2l−2)
F n = f l W + f l W (9.58)
l=1 l=1
Using the relations for the even and odd contributions respectively,
2 (n−1)(l−1)
2 (n−1)(l−1)
W (n−1)(2l−1) = W (n−1) (W ) W (n−1)(2l−2) = (W ) (9.59)
2
] = e
where W = [e −i( ω)( t) 2 −i( ω)(2 t) , (9.58) becomes
N/2 N/2
(e) 2 (n−1)(l−1) (o) 2 (n−1)(l−1)
(n−1)
F n = W f (W ) + f (W ) (9.60)
l l
l=1 l=1
Comparing (9.60) to (9.48), we see that the two summations contributing to F n themselves
are discrete Fourier transforms, but each over only half of the data sampled at an interval
κ
2 t.If N = 2 , then after this partition, we have two sums over 2 κ−1 terms. Performing a
similar partition on each of these, we have four sums, each over only one fourth of the data.
If we recursively perform this partition κ = log N times, we have “sums” of only one term.
2
The FFT algorithm applies this decimation approach to obtain the values of all F n after only
2
Nlog N « N operations. The computation savings offered by FFT are so significant that
2
many common applications of Fourier analysis would be prohibitively expensive if FFT
were not available.
While the decimation procedure may still be applied if N is not a power of 2, the additional
book-keeping is expensive. Therefore, it is common in this case to “pad” the data set with
κ
zeros until we obtain a total of 2 > N points. The only change in the Fourier transform
due to this padding is that the frequencies are now
κ
π (2 − N)( t)
ω n = (n − 1) ω ω = Q = (9.61)
P + Q 2
2Q is the time duration of the “padding” of the signal f (t) with zeros.

Special properties of the Fourier transform of a real function and the
power spectrum
∗
For a real function with f (t) = f (t), we have the property
+∞ ' +∞
1 1
'
∗ ∗ +i(−ω)t −iωt
[F(−ω)] = √ f (t)e dt = √ f (t)e dt = F(ω) (9.62)
2π 2π
−∞ −∞
This holds as well for the Fourier transform computed from sampled data:
[F(−ω n )] = F(ω n ) (9.63)
∗
Using F(ω m + l2ω max ) = F(ω m ), the discrete Fourier transform (9.48) satisfies
F ∗ (9.64)
N−m = F m