Digital Analysis of Geophysical Signals and Waves

3.5 Discrete Fourier Transform

Digital versions of the Fourier transform pair (equations 3.1.1 and 3.1.2 ) are required for digital Fourier analysis. To motivate this development, it is very instructive to review the steps taken in earlier sections in both time (or space) and frequency domains. However, the representations in the two domains require a concept not yet discussed, namely convolution. This is an immensely important aspect of digital analysis and will be described in Sections 4.1 – 4.4. The discussion below requires only that you accept the Fourier transform pairs as given, just as you have previously in Figure 3.6. We ask you to trust us again. Our experience with most students convinces us that you will enjoy learning what convolution is all about. For now we seek digital, truncated versions of the continuous Fourier transform pair that will permit computer computation.

In Section 2 on Digital Recording we described how a continuous geophysical signal, s(t) or s(x) is modified in several ways during digital recording. After amplitude sampling, there’s time (or space) domain sampling, and then the signal is truncated (or windowed) leading to frequency domain sampling. Let’s now assume that we have a time domain signal, s(t) and review the operations that produce time domain, sampled, finite-length (i.e., truncated) data. We will explore what these operations are in the frequency domain after discrete Fourier transform. To make everything “perfectly clear” we’ll graphically illustrate the whole works with an example of the complete sequence. For simplicity, we will use a real, even function in the time domain which, of course, has a real, even Fourier transform in the frequency domain.

With sampling interval Δt, the sampled data are “cleanly expressed” in Section 2.3 as the multiplication of the continuous data, s(t) by a Dirac comb, II(t). This is shown by the sequence in panels a, b, and c on the left side of Figure 3.8. The operation was expressed by equation 2.3.6 repeated here as

The sampled data (left panel of Figure 3.8c) are then truncated by multiplying with a rectangle function (box-car window), II (t) of length T as described in Section 2.4. This is shown diagrammatically in sequence c to e in the left, time domain column of Figure 3.8 using the rectangle function, as in equation 2.4.1 before, i.e.,

 

Time domain sampling and truncation (the two multiplication operations shown vertically on the left side of Figure 3.8a through e) can be combined and expressed as

 

Here, we assume that the length of the data, T is divided into N equally spaced delta functions so that T = NΔt.

The continuous and discrete Fourier transform results keyed to the time domain and frequency domain columns in Figure 3.8 are:

1. First, the Fourier transform of the continuous, unsampled signal, s(t) yields a continuous, frequency domain result, S(f). This is illustrated by the horizontal panels of Figure 3.8a separated by the double-headed arrow which, of course, means a Fourier transform pair. S(f) represents the proper Fourier transform, unaffected by sampling and truncation.

2. Next, the Fourier transform of the Dirac comb, III(t) becomes another Dirac comb in the frequency domain, III(f). This is shown in Figure 3.8b. As plotted earlier by the Dirac comb Fourier transform pair in Figure 3.6, when the teeth of the Dirac comb are Δt apart in the time domain, they are 1/Δt apart in the frequency domain.

3. The Fourier transform of the sampled version of s(t) in Figure 3.8c is from equation 3.1.2 continuous since S(f) is continuous, but an unexpected result is that S(f) is periodic as is illustrated in the sketch in Figure 3.8c. It is literally composed of an infinite number of periodic replicas. We ask you to accept this as fact for now; it will be easy to understand later in Section 4.4 when we invoke the Convolution Theorem. This will also allow us to appreciate the meaning of the asterisk symbol, * between the right hand panels of a and b in Figure 3.8. This indicates a convolution which yields the periodic result S(f)*III(f). Convolution is also the key to understanding aliasing (Appendix A) which is depicted by the dashed overlaps of the periodicities about the Nyquist frequency, + 1/2Δt in the right panel of Figure 3.8c. It is tempting to discuss convolution now but we’ll save this for later.

4. In the d portion of Figure 3.8 we see another result shown earlier in Figure 3.6, namely that the Fourier transform of the rectangle function (boxcar function) is the sinc function. The first zero crossings of the sinc function which separates the positive, centered, main lobe from the side-lobes are always at one over the total length of the boxcar, +1/T.

5. The Fourier transform of the sampled, truncated signal, s(t) x III(t) x II(t) (left side of Figure 3.8e) is the continuous, periodic frequency domain result shown on the right side of Figure 3.8e. Why it has the “ripples” riding on it compared to the smooth appearance of the result two panels above (Figure 3.8c) is also because of convolution. This so-called “leakage” is well-understood when there is convolution of any function by a sinc function as explained in Appendix C.

6. At this point in the sequence presented in Figure 3.8 we must reiterate that for actual computer evaluation of the DFT, we must evaluate S(f) at discrete frequencies. These are at N values sampled equally over one period of the transform of S (f) in equation 3.5.4, i.e.,

or

The process of discretizing the periodic spectrum is shown in the lower right corner of Figure 3.8 as the multiplication of S(f) * III(f) * II(f) by a Dirac comb in the frequency domain with ”teeth” separated by Δf =1/T (right side of Figure 3.8f). Its inverse Fourier transform is, of course, another Dirac comb in the time domain with teeth separated by T as shown on the left side of Figure 3.8f.

7. Finally, at the very bottom of Figure 3.8 (panels g) we have the overall result of time sampling, truncation, and discretized frequency. Namely, a digitized, periodic representation of the true Fourier transform pair shown at the top of Figure 3.8 (panels a). The N samples indicated in each domain represent one single period of the infinite, periodic sequence.

 

There are many, many important concepts illustrated in Figure 3.8. One that really stands out is that sampling (digitizing) in one domain always produces periodicity in the other domain. That is, time domain sampling produces a periodic function in the frequency domain (Figure 3.8c) and sampling in the frequency domain results in a periodic function in the time domain (Figure 3.8g). The N time(NΔt), and N frequency (NΔf) samples marked in the bottom g panels of Figure 3.8 represent a single period of the respective periodic, discrete time and frequency domain results. Therefore, we must realize that these are only one period of a periodic function, i.e., the discrete Fourier transform pair is not truly truncated to zero values outside of these single periods. This has important practical implications.

The final N results discussed above and presented at the bottom of Figure 3.8 illustrate the discrete Fourier transform pair. To express the discrete Fourier transform (DFT) of the sampled results mathematically we must replace the Fourier transform in equation 3.1.2 by a summation. The discrete values in the frequency domain are

 

After substituting equation 3.5.5 into equation 3.5.6 and applying the trapezoidal rule we have for the DFT,

 

and for the inverse discrete Fourier transform (IDFT),

 

All computer routines that evaluate the DFT set Δt equal to 1 and the formulas are often written with the shorthand notation

 

and

for the DFT and IDFT, respectively. The true values of the DFT and IDFT, therefore, require the multiplication of equation 3.5.9 by Δt and equation 3.5.10 by 1/Δt.

For geophysical data that are always real, the DFT produces N complex values that must have the symmetry properties from Section 3.3. Namely, the real part is an even function and the imaginary part is an odd function of frequency. Consequently, only N/2 complex frequency domain values contain unique, independent results. For example, the N/2 positive frequency values of the transform can be used uniquely to determine the negative frequency values. Finally, we add that one can generate the infinite, periodic sequence as indicated at the bottom of Figure 3.8 by periodic repetition of the sequences of N points defined by the DFT and IDFT in equations 3.5.7 to 3.5.10. In other words, the DFT and IDFT yield one period of the infinite sequences.

The extent to which the single period of the DFT approximates the true, continuous Fourier transform depends on the degree of aliasing and leakage (as shown in the frequency domain columns in Figure 3.8c and e, respectively). Therefore, any differences between the discrete and continuous Fourier transform arise because we must digitize (sample) and truncate (window) the time (or space) domain signals.

Figure 3.9 is an example from harris (1977) illustrating the sequence discussed in Figure 3.8 above when the real time domain signal, s(t) is not an even function, therefore, its Fourier transform has both real and imaginary parts. Can you can follow the steps that result in the true (original) Fourier transform, which is composed of a pair of real and imaginary delta functions (right hand column of Figure 3.9a), becoming the discrete Fourier transform sketched at the bottom, right of Figure 3.9g? The frequency domain delta functions have become an infinite, periodic sequence of digitized real and imaginary sinc functions in the frequency domain after truncation and sampling. This is an example where the difference between the discrete and continuous Fourier transforms is very significant.