Spectral Analysis of Geophysical Data - Advances in Data, Methods, Models and Their Applications in Geoscience - page 36

multiplication of the amplitude spectrum. Auto-correlation of two wavelets is equal to the
convolution of the first wavelet with the time-reverse of the second wavelet.

4.6 Fast Fourier transform
It is important to find the discrete forms of the continuous Fourier transform pair in
equations (12) and (13). These can be written as (Smith, 1999)

()=∑ ()

(16)

and

∑ ()

( ) =

(17)

Both G(n), the discrete amplitude spectrum and the digitized time domain signal, g(k) are
periodic as they repeat at every N points. The amplitude spectrum is symmetric while the
phase spectrum is antisymmetric.
For real applications, each of equations (16) and (17) will have to be decomposed into the
real and imaginary parts with trigonometric argument of = . Thus an N point time

domain signal is contained in arrays of N real parts and N imaginary parts for each
equation.
Calculating the discrete Fourier transform (DFT) equations takes a considerable time even
with high speed computers because of the cycles of computations that must be run. The raw
computations of DFT can either be done by use of simultaneous equations (very inefficient
for practical use) or by correlation method in which signals can be decomposed into
orthogonal basis functions using correlation (not too useful a method). The third and the
most efficient method for calculating the DFT is by Fast Fourier Transform (FFT). This is an
ingenious algorithm that decomposes a DFT with N points into N DFTs each with a single
point. The FFT is typically hundreds of times faster than the other methods. In actual
practice, correlation is the preferred techniques if the DFT has less than 32 points, otherwise
the FFT is used.
Cooley & Tukey (1965) have the credit for bringing the FFT to the scientific world. The FFT,
a complicated algorithm is based on the complex DFT; a more sophisticated version of the
real DFT and operates by first decomposing an N - point time-domain signal into N time
domain signals, each composed of a single point. The second step is to calculate the N
frequency spectra corresponding to these N time domain signals. Lastly, the N spectra are
synthesized into a single frequency spectrum.
An interlaced decomposition is used each time a signal is broken into two, that is, the signal
is separated into its even and odd numbered samples. There will be Log 2 N stages required
in the decomposition and Nlog 2 N multiplications instead of NxN multiplications without
the FFT use. For instance, a 16-point signal (2 4 ) requires 4 stages, 512-point signal (2 7 )
requires 7 stages, a 4096-point signal (2 12 ) requires 12 stages of signal decomposition and so
on. The FFT algorithm works on a data length of 2 M , where M is a positive integer (≥5). If the
data length is not up to the requirement for FFT operation, then “zeros” are sufficiently
added. The decomposition is nothing more than a reordering of the samples in the signal.
After the decomposition, the FFT algorithm finds the frequency spectra of a 1-point time
domain signal (easy!) and then combine the N frequency spectra in the exact reverse order
that the time domain decomposition took place.