The Fourier Transform,
a First Look
Christian Zuniga, PhD
In 1822, Joseph Fourier published his book The Analytic Theory of Heat in which he showed many signals could be decomposed into sums of sines and cosines. Two hundred years later, Fourier’s ideas are used in many places in modern society, from cryptography, to radios and x-ray machines. As mentioned in the surprisingly entertaining book The World According to Wavelets, “The Fourier Transform is a mathematical prism, breaking up functions into the frequencies that compose it”[1]. The Fourier Transform expresses a signal x(t) as the superposition of sines and cosines, or more compactly in terms of complex exponentials. To obtain the transform, expressed as X(f), the signal is correlated against exponentials of all frequencies. It is a process analogous to tuning a radio where certain frequencies may be more dominant. No information is lost or gained in the conversion, however.
A few functions have analytic expressions but in general the transform must be computed numerically. A digital computer can only compute the transform at discrete values of x(t) and X(f). As most students of digital signal processing would attest, the details of the implementation may be tricky. A straightforward approximation of the integral above using trapezoidal integration would indicate the Fourier transform can be approximated by the Discrete Fourier Transform (DFT).
The DFT only includes the summation. To approximate the Fourier Transform, the DFT should be multiplied by ∆t. The signal has to be sampled both in time and in frequency, at intervals ∆t and ∆f, respectively. How are these intervals chosen? The details can be found in several references [2][3]. “The Fast Fourier Transform and its Applications” is a classic reference. It is important to know that sampling in one domain introduces periodicity in the other domain with the period being the inverse of the sampling interval. If x(t) is sampled with interval ∆t, the spectrum becomes periodic with period 1/∆t. Figure 1 shows a sample signal spectrum after sampling in time. If the signal is bandlimited with maximum frequency B, it is apparent that in order to avoid overlap of the copies, the sampling frequency Fs = 1/∆t should be greater than or equal to twice the maximum signal frequency B. If the signal is not bandlimited, there would be overlap among the copies, or aliasing. Typically the signal may be passed through a low pass filter to limit its frequency. This restriction sets the sampling interval in time to be.
Alternatively, if a signal is sampled at frequency Fs, the maximum frequency that can be resolved is Fs/2 (also called the Nyquist frequency).
Similarly sampling in frequency makes the time domain signal periodic with period 1/∆f. The time domain signal starts from 0 and is truncated to a duration T. In order to avoid time domain aliasing, the sampling interval in frequency is the inverse of the signal duration T.
The product ∆t∆f in the approximation of the Fourier integral is 1/N where N is the number of samples in the signal of duration T. Figure 2 shows the relations of the sampling intervals.
Everything seems to be ready to calculate the approximation so lets try it on a function with a known Fourier transform. The cosine is a very specific function having periodicity in time and being bandlimited in frequency. Although most signals will not have this property, it is still instructive to study this case. A cosine function with frequency f0, x(t) = cos(2πf0t), has Fourier transform 0.5(δ(f-f0)+ δ(f+f0)) or two delta functions as shown in Figure 3. Each has a value of 0.5, or more technically, integrates to ½.
The function should be sampled at at least 2xf0 or a minimum of two samples per period as indicated in Figure 3. Since the function is periodic, it is best to set the truncation interval T equal to an integer multiple of the period or T= N/f0. The DFT is most conveniently calculated with the Fast Fourier Transform (FFT) and can be done in many numerical packages. Calculating the DFT and plotting the magnitude gives the result in Figure 4. The cosine had a frequency f0 = 200 Hz. The sampling frequency was Fs=2f0 and T=10/f0. Anyone who first plots this result would most likely find this plot mysterious. How does it relate to the expected transform in Figure 3.
First it is important to remember what the indices represent. Each index k represents a frequency k ∆f. The frequency resolution ∆f is the inverse of T. Since 10 periods were used for T, ∆f = 20 Hz. Figure 4 shows there is only one non zero value at an index k=10. This represents frequency 10x20 = 200 Hz as expected.
What about the magnitude of the transform at k=10? The plot shows XD[10] = 20. Multiplying this value by ∆t=1/400 gives 1/20 which is not equal the actual value of 0.5. What went wrong with the approximation to the Fourier Transform?
Understanding where the discrepancy comes from involves understanding the convolution operation. Convolution gives the response y(t) of a linear, time invariant filter h(t) to an input series x(t). The Fourier Transform can simplify this operation since convolution in time becomes multiplication of the transforms or Y(f) = H(f)X(f). Similarly, multiplication in time involves convolution in the frequency domain.
Computing the DFT indirectly involves multiplication and convolution of the original signal by sampling functions. The signal x(t) is first truncated to a duration T by multiplying x(t) with a rectangular function to give x(t)rect(T). Figure 3 already shows the result of truncating the cosine, which is originally infinite in extent. Multiplication in time implies the corresponding transforms are convolved or X(f)⊗ sinc(f). The Fourier Transform of the rect function is a sinc as shown in Figure 5. The details of this transform can be found in the references. The key point is that the sinc function introduces a scaling by T of the original spectrum X(f).
Discretization of the signal involves a second multiplication by a train of delta functions d(t) as shown in Figure 6. The delta functions are separated by the sampling interval ∆t. The Fourier Transform of the train of delta functions turns out to also be a train of delta functions in frequency, but separated by 1/∆t. This result is what introduces periodicity in the frequency domain. The sampled signal is then the result of 2 multiplications or
xs[n] = x(t)rect(T)d(t).
This new insight explains the discrepancy in the result of the DFT with the continuous version. The DFT is actually computing the transform of xs[n], not x(t). For this case they are related by Xs(f) = (2T/∆t) X(f)= (2/N)X(f). The factor of 2 is obtained because for the chosen value of Fs, the two delta functions overlap exactly. For larger values of the sampling frequency Fs, there is no overlap and factor of 2 goes away.
To obtain the value of the Fourier Transform, the computed DFT is divided by N. In the previous example dividing the value by 2N or 40 gives 20/40 = ½ which now equals the actual value! Unfortunately, there is no general scaling relation for other types of signals. However the DFT still gives an approximation to the Fourier Transform.
References
[1] Hubbard “The World According to Wavelets” Second Edition, A K Peters Ltd, Copyright 1998
[2] Brigham “ The Fast Fourier Transform And Its Applications” Prentice Hall 1988
[3] Lyons “ Understanding Digital Signal Processing” Second Edition, Prentice Hall 2004
